std :: map의 마지막 n 요소에서 std :: vector를 만드는 관용적 C++

Question

std :: map의 마지막 n 요소에서 std :: vector를 만드는 C++ 관용적 방법은 무엇입니까?

벡터에서 순서를 유지하는 데 관심이 없습니다.

std::map< double, MyType > m; 
    size_t n = 3; 
    std::vector<MyType> v; 
    std::map< double, MyType >::iterator it = m.end(); 
    while (n--) { // assuming m.size() >= n 
     it--; 
     v.push_back(it->second); 
    } 

을하지만, 다른 방법이 더 관용적, 그것을 할 :

나는이 같은 요소를 복사 할 수 있습니까?

Answer 1

std::copy 유형을 변경하지 않고 복사하려는 경우 적합합니다. 그러나 std::map<T,U>::iterator_type::value_type은 U (복사 할 유형)이 아니지만 std::pair<T,U>입니다. 즉, 맵 반복기를 역 참조하면 키와 값 유형 쌍이 생성되므로 원시 사본이 작동하지 않습니다.

그래서 우리는 요소를 복사하여 그 길을 따라 변형을 수행해야합니다. 그것은 std::transform을위한 것입니다.

편의상 컴파일러에서 C++ 11 람다 식을 지원하고 auto 키워드를 지원한다고 가정합니다. 그렇지 않다면, 그것은 상당히 사소하게 functor로 재 작성 될 수 있습니다.

std::transform(map_first, map_last, std::back_inserter(vec), [](std::pair<double,MyType> p) { return p.second; }); 

이제 우리는 바로이 개 첫 번째 매개 변수를 입력해야합니다 :하지만 우리는 대략 이런 식으로 뭔가를 찾고

auto map_first = std::next(map.end(), -n); 
auto map_last = map.end(); 

여기에 유일한 까다로운 부분은지도 반복자는 양방향 있다는 것입니다 만, 랜덤 액세스가 아니기 때문에 우리는 단순히 map.end() - n이라고 말할 수는 없습니다. - 연산자가 정의되지 않았습니다. 대신 std::next을 사용해야합니다 (양방향 연산자의 경우 일정 시간이 아닌 선형 시간이 소요되지만 그 방법은 없습니다).

(나는이 코드를 컴파일 시도하지 않은, 참고, 그래서 조정이의 작은 비트가 필요할 수 있습니다)

Answer 2

그 일을하는 한 가지 방법은 for_each 간단한 사용

: 당신이 벡터를 채울 것인지, 또한

map<int,double> m; 
    vector<double> v; 
    //Fill map 
    for_each(prev(m.end(), 3), m.end(), 
        [&](pair<int,double> p) { v.push_back(p.second); }); 

: 심지어 간단한 방법이 std::prev 사용

map<int,double> m; 
    vector<double> v; 
    //Fill map 
    auto siter = m.end(); 
    advance(siter, -3); 
    for_each(siter, m.end(), [&](pair<int,double> p) { v.push_back(p.second); }); 

편집 for_each과를 역순으로 사용할 수 있습니다 :

for_each(m.rbegin(), next(m.rbegin(), 3), 
     [&](pair<int,double> p) { v.push_back(p.second); }); 

Answer 3

거꾸로 그것을 수행

assert(n <= m.size()); 
std::copy(m.rbegin(), m.rbegin()+n, std::back_inserter(v)); 

양방향 반복자를 FTW.

---

OK, 분명히 아직 깨어나지 않았으며, 그것은 희망적인 생각이었습니다. 나는 여전히 작업 버전은 다음과 같다,하지만 마지막 N을 얻기 위해 뒤로 걷기를 선호 :

#include <map> 
#include <vector> 
#include <algorithm> 
#include <iterator> 

using namespace std; 

// I'm assuming it's ok to copy min(m.size(), n) 
template <typename Iter> 
Iter safe_advance(Iter begin, Iter const &end, int distance) 
{ 
    while(distance-- > 0 && begin != end) 
     ++begin; 
    return begin; 
} 

void copy_last_n(map<double,int> const &m, 
       vector<int> &v, int n) 
{ 
    transform(m.rbegin(), safe_advance(m.rbegin(), m.rend(), n), 
       back_inserter(v), 
       [](map<double,int>::value_type const &val) 
       { 
       return val.second; 
       } 
      ); 
} 

제임스 간제는 이미 Second 펑터를 썼다 - 사용 당신은 람다에 대한 액세스 권한이없는 경우 그.

Answer 4

std::transform 가장 관용적 인 방법이 될 것입니다. 당신은 기능 객체가 필요합니다

template<typename PairType> 
struct Second 
{ 
    typename PairType::second_type operator()(PairType const& obj) const 
    { 
     return obj.second; 
    } 
} 

을 (. 당신이 std::map 또는 std::pair를 사용하는 다른 것들로 많은 일을하는 경우, 당신은 당신의 도구 상자이있을 것이다) 그 후

를, 그것은 약간의 너는 오직 마지막 n만을 원하기 때문에 어색해.

std::vector<MyType> 
extractLastN(std::map<double, MyType> const& source, size_t n) 
{ 
    std::vector<MyType> results; 
    std::transform(source.begin(), source.end(), 
        std::back_inserter(results), 
        Second<std::map<double, MyType>::value_type>()); 
    if (results.size() > n) { 
     results.erase(results.begin(), results.end() - n); 
    } 
    return results; 
} 

:지도에 반복자는 임의 접근 반복자하지 않습니다, 그리고 당신이 를 추가하거나 임의의 값을 뺄 수 없기 때문에, 가장 간단한 솔루션은 모든 다음 원하지 않는 것들을 제거를 복사하는 것입니다

이것은 가장 효율적이지는 않지만 n에 따라 다르며 이 사용 된 경우 충분할 수 있습니다. 당신이 여분의 복사, 등 (n지도의 크기보다 일반적으로 더 작은 경우에만 아마 가치)를 피하려는 경우, 당신은해야 할 것이다 애호가 뭔가 :

std::vector<MyType> 
extractLastN(std::map<double, MyType> const& source, ptrdiff_t n) 
{ 
    std::map<double, MyType>::const_iterator start 
      = source.size() <= n 
       ? source.begin() 
       : std::prev(source.end(), n); 
    std::vector<MyType> results; 
    std::transform(start, source.end(), 
        std::back_inserter(results), 
        Second<std::map<double, MyType>::value_type>()); 
    return results; 
} 

(있는 경우 당신이 C++ (11)에 대한 액세스 권한이없는, std::prev는 단순히 :

template<typename IteratorType> 
IteratorType 
prev(IteratorType start, ptrdiff_t n) 
{ 
    std::advance(start, -n); 
    return start; 
} 

다시 말하지만, 당신이 표준 라이브러리와 함께 많은 일을하는 경우, 당신은 아마 이미 툴킷에 그것을 가지고)

Answer 5

.

다음은 간단한 Boost입니다. 범위 버전 :

#include <boost/range/iterator_range_core.hpp> 
#include <boost/range/adaptor/map.hpp> 
//#include <boost/range/adaptor/reversed.hpp> // comment in for 'reversed' 
#include <map> 
#include <vector> 

struct X{}; 

int main(){ 
    std::map<int, X> m; 
    unsigned n = 0; 
    auto vec(boost::copy_range<std::vector<X>>(
    boost::make_iterator_range(m, m.size()-n, 0) 
    | boost::adaptors::map_values 
    //| boost::adaptors::reversed // comment in to copy in reverse order 
)); 
} 

Answer 6

먼저 무엇을 작성하여 관용어로 작성하고 싶습니까? 나는 제안한다 :

std::vector<Mytype> v; 
v.reserve(n); 
std::transform(
    limited(n, m.rbegin()), 
    limited_end(m.rend()), 
    std::back_inserter(v), 
    values_from(m) 
); 

이제 우리는 그 코드를 유효하게 만들어야한다.

우리는 (m을 필요로하지 않는) 람다와 values_from(m)를 교체하거나 (경우 m 유형 공제가있는) 제임스 칸 세이의 클래스 Second 사용하여 구현할 수 있습니다

template <typename Map> 
Second<Map::value_type> values_from(const Map &) { 
    return Second<Map::value_type>(); 
} 

이 limited 구현입니다 약간의 고통. iterator를 반환하는 템플릿 함수입니다. 반환하는 iterator 유형은 다른 반복자 유형을 랩핑하는 템플리트이며, n을 추적하는 것을 제외하고 모든 반복자 유형을 전달하는 템플리트이며, n 번 고급 될 때 end 반복자처럼 작동합니다. limited_end 동일한 유형의 단부 반복기를 반환하므로 어느 기본 반복자 같으면 , 또는 반복자 하나 limited_end로 생성하고, 다른 하나는 제로까지 n 실행할 경우 동등 비교한다.

이 코드는 유용하지 않지만 기본적으로 이 아닌 모든 표준 알고리즘에 해당하는 코드는 _n입니다.이 경우 transform_n을 원하지만 하나도 없습니다.

transform의 대안은 m.rbegin()으로 감싸는 boost::transform_iterator으로 을 사용하는 것입니다. 내가 항상 transform_iterator을 사용하기 위해 문서를 점검해야하기 때문에 여기에서도 그렇게하지 않을 것이다.