출력하기 전에 값으로 std :: map 정렬하기 및 파기

Question

지도가 정렬 될 준비가되어 있지 않으며 신속하고 무작위적인 키 액세스를 위해 많이 최적화되어 있습니다. 실제로 std :: sort를 지원하지 않습니다.

내 현재의 문제는 난 그냥 값 (int)를 위해 10 쌍을 추출하고 그것을 파괴 할 필요가, 내가 더 이상 사용하지 않을거야

map<std::string,int> 

전체

을 가지고있다.

가능한 경우 가장 좋은 방법은 제자리에서 정렬 한 다음 10 번 반복하는 것이지만 분명히 해결책은 아닙니다.

(중복 키를 허용하기 위해) 여러 가지 방법을 시도하고 있지만 가능한 경우 stl 알고리즘을 사용하는 좀 더 세련된 솔루션이 있는지 알고 싶습니다.

편집 : 나는지도로 필요로하는 시간의 99 %를, 빠른 키 조회 값을 증가시키기 때문에지도를 사용하고

. 더 이상지도가 필요하지 않을 때 가치있는 순서로 나중에 추출하는 좋은 방법이 필요합니다.

현재 접근 방식이 될 whould :

• 표준 : : 벡터 (쌍 (표준 : : 문자열, INT))
• 정렬 벡터에지도 (표준 : : 문자열, int)를 복사
내부적 균형 비나을 사용하기 때문에
• 은지도 반복자를 사용하여 반복하는 경우
• 벡터를 파괴하고

Answer 1

지도는 키 순서로 정렬 된 트리 형태로 저장됩니다. 10 개의 가장 작은 (또는 가장 큰) 정수 값과 그 키를 원하십니까?

그런 경우지도를 반복하고 모든 키 - 값 쌍을 쌍 벡터 (std::vector<std::pair<std::string, int> >))에 넣으십시오.이 경우 두 개의 iterator-arg 생성자를 사용할 수 있습니다. std::partial_sort을 벡터에 추가합니다. 부분 문자열을 비교하는 비교기를 지정합니다.이 비교기는 값 int를 비교하여 쌍을 비교하고 키 문자열을 무시한 다음 벡터의 시작에서 원하는 10 쌍을 가지며 나머지 벡터에는 나머지 쌍을 불특정 순서로 사용한다.

코드 (안된) :

typedef std::pair<std::string, int> mypair; 

struct IntCmp { 
    bool operator()(const mypair &lhs, const mypair &rhs) { 
     return lhs.second < rhs.second; 
    } 
}; 


void print10(const std::map<std::string,int> &mymap) { 
    std::vector<mypair> myvec(mymap.begin(), mymap.end()); 
    assert(myvec.size() >= 10); 
    std::partial_sort(myvec.begin(), myvec.begin() + 10, myvec.end(), IntCmp()); 

    for (int i = 0; i < 10; ++i) { 
     std::cout << i << ": " << myvec[i].first 
      << "-> " << myvec[i].second << "\n"; 
    } 
} 

주 당신이 얻을 것을 그때가 지정되지 않은 것 같은 값을 여러 문자열 (10)의 제한의 양쪽,이있는 경우. 정수가 같은 경우에는 비교기가 문자열을 봐서 제어 할 수 있습니다.

Answer 2

지도 처음 10 값, 당신은 항목이 키에 분류 얻을 것이다 얻을 값을 저장하는 트리. 따라서 반복자를 사용하여 10 개의 값을 추출 할 수 있습니다. 그것은 당신이 원하는 것이거나 다른 것을하고 싶습니까? 명확히하십시오.

편집 : 벡터 및 정렬 대신에 직접 세트를 사용하고 비교 함수를 전달할 수 있습니다. 그런 다음 상위 10 개 요소를 추출 할 수 있습니다. 이것은 내 테스트 코드입니다 :

typedef std::pair<std::string, int> MyPair; 


struct MyTestCompare 
{ 

    bool operator()(const MyPair& firstPair, const MyPair& secondPair) const 
    { 
     return firstPair.second < secondPair.second; 
    } 
}; 

int main() 
{ 
    std::map<std::string, int> m; 
    m[std::string("1")] = 10; 
m[std::string("2")] = 40; 
m[std::string("3")] = 30; 
m[std::string("4")] = 20; 



    std::set<MyPair,MyTestCompare> s; 
    std::map<std::string, int>::iterator iter = m.begin(); 
    std::map<std::string, int>::iterator endIter = m.end(); 
    for(; iter != endIter; ++iter) 
    { 
     s.insert(*iter); 
    } 

} 

Answer 3

boost::multi_index을 사용하여 값을 반복 할 수 있습니다. 그것은 다음과 같은 것 같습니다

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/member.hpp> 
#include <boost/multi_index/ordered_index.hpp> 
#include <boost/multi_index/hashed_index.hpp> 
using namespace boost::multi_index; 

struct X { 
    X(std::string val_str, int val_int) : val_str(val_str), val_int(val_int) {}; 
    std::string val_str; 
    int   val_int; 
}; 

typedef multi_index_container< 
    X, 
    indexed_by< 
     hashed_unique< member<X, std::string, &X::val_str> >, 
     ordered_non_unique< member<X, int, &X::val_int> > 
    > 
> X_map; 

void func() 
{ 
    X_map data; 
    data.insert(X("test", 1)); 
    // ... 

    // search by val_str 
    // complexity is equal to O(1) for hashed index (worst cast O(n)), 
    // and O(log n) for ordered index 
    X_map::const_iterator it = data.find("test"); 
    // ... 

    // iterate in order of val_int 
    size_t N = 0; 
    for (X_map::nth_index<1>::type::const_iterator it = data.get<1>().begin(); N < 10 && it != data.get<1>().end(); ++it, ++N) { 
    // copy elements somewhere 
    } 
} 

당신은 반복 (val_str 또는 val_int)에 대한 모든 인덱스를 사용할 수 있습니다.

Answer 4

는 가장 우아한 방법으로되지 않을 수 있습니다,하지만 당신은 같은 세트의 값을 통해 그들을 정렬 할 수 있습니다

 
#include <map> 
#include <set> 
#include <iostream> 
#include <string> 

using namespace std; 

struct sortPairSecond 
{ 
    bool operator()(const pair<string, int> &lhs, const pair<string, int> &rhs) 
    { 
     return lhs.second < rhs.second; 
    } 
}; 


int main (int argc, char *argv[]) 
{ 
    cout << "Started...\n"; 
    map<string, int> myMap; 
    myMap["One"] = 1; 
    myMap["Ten"] = 10; 
    myMap["Five"] = 5; 
    myMap["Zero"] = 0; 
    myMap["Eight"] = 8; 


    cout << "Map Order:\n---------------\n"; 
    set<pair<string,int>, sortPairSecond > mySet; 
    for(map<string, int>::const_iterator it = myMap.begin(); it != myMap.end(); ++it) 
    { 
     cout << it->first << " = " << it->second << "\n"; 
     mySet.insert(*it); 
    } 

    cout << "\nSet Order:\n--------------\n"; 
    for(set<pair<string, int> >::const_iterator it = mySet.begin(); it != mySet.end(); ++it) 
    { 
     cout << it->first << " = " << it->second << "\n"; 
    } 

    return 1; 
} 

Answer 5

또 다른 가능성은 역지도를 구축하는 것입니다. 당신을 위해 std::map<int, std::string> 일 것입니다. 역방향지도의 항목은 값에 따라 정렬됩니다.

template< typename TK, typename TV, class TP, class TA, typename T1, typename T2 > 
inline void asserted_insert(std::map<TK,TV,TP,TA>& m, const T1& k, const T2& v) 
{ 
    typedef std::map<TK,TV,TP,TA>     map_type; 
    typedef typename map_type::value_type   value_type; 
    assert(m.insert(value_type(k,v)).second); 
} 

template< class TMap > struct reverse_map; 
template< typename T1, typename T2 > struct reverse_map< std::map<T1,T2> > { 
    typedef std::map<T2,T1>       result_t; 
}; 

template< typename T1, typename T2, class TP1, class TA1, class TP2, class TA2 > 
inline void build_reverse_map(const std::map<T1,T2,TP1,TA1>& map, std::map<T2,T1,TP2,TA2>& reverse_map) 
{ 
    typedef std::map<T1,T2,TP1,TA1>     map_type; 

    for(typename map_type::const_iterator it=map.begin(), 
             end=map.end(); it!=end; ++it) { 
    asserted_insert(reverse_map, it->second, it->first); 
    } 
} 

이 코드는 값이 너무 독특하다고 가정 (과 주장을 던졌습니다, 그렇지 않은 경우) :

다음

내가 그런 경우 내 도구 상자에있는 것입니다. 이 문제가 귀하의 문제에 해당되지 않으면 쉽게 멀티 맵을 사용하도록 코드를 변경할 수 있습니다.