は、出力の前に値でのstd ::マップのソート＆破壊

Question

私はマップがそのが頻繁にはstd ::並べ替えをサポートしていません実際に。高速でランダムキーのアクセスのために最適化され、かつ、ソートする準備ができていないことを承知しています。

私の現在の問題は、私はちょうど値（int型）の順序で10ペアを抽出し、それを破壊する必要があり、私はもう使用するつもりはない

map<std::string,int> 

フル

を持っていることです。

ことが可能であった場合の最もよい事は場所でそれをソートし、それを10回繰り返すことであろうが、それは明らかに解決策ではありません。

私は（重複キーを許可する）マルチマップを経由するなど、さまざまなソリューションをしようとしているが、私はとりうる限りSTLアルゴリズムを使用して、よりエレガントな解決策があるかどうかを知りたいのです。

編集：私はマップとしてそれを必要とする時間の99％を、高速のキールックアップが値を増加するので、私はマップを使用してい

。ただ、私はもうマップを必要としないとき、後に値順に抽出するのに良い方法が必要です。

現在のアプローチがあることwhould：

• のstd ::ベクトル（ペア（のstd ::文字列、int型））
• ソートベクトルにマップ（のstd ::文字列、int）をコピーし
• は、マップのイテレータを使用して反復した場合、それは内部的にバランスの取れたBINAを使用すると、あなたはアイテムがキーでソートされます最初の10個の値
• がベクトルを破壊し、

Answer 1

マップがキー順にソートツリーとして保存されます。最小値（または最大値）の10個の値とそのキーが必要ですか？

この場合、マップを繰り返し、すべてのキーと値のペアをペアのベクトル（std::vector<std::pair<std::string, int> >)）に入れてください。これにはstd :: vectorの2つのiterator-argコンストラクタを使用できます。 std::partial_sortをベクトルに置きます。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

をマップ取得しますryツリーに値を格納します。したがって、イテレータを使用して10個の値を抽出できます。それはあなたが欲しいものか、他に何かしたいのですか？どうか明らかにしてください。 EDIT

： 代わりにベクトルを使用して並べ替えの、あなたが直接設定し、比較関数を渡すことができます。次に、上位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); 
    } 
} 

このコードは、あまりにも、値が一意であることを前提とし（とそうでない場合、アサーションをスローします）。これが問題に該当しない場合は、マルチマップを使用するようにコードを簡単に変更することができます。