c++ - マップ値でソートされたマップキーのベクトルを取得する最速の方法は?

Question

私は持っていmap<int int>ます。最初の int (キー) のベクトルを取得する必要がありますが、2 番目の int の順序 (値) で並べ替えます。これを行うための最速の方法は何ですか?

Answer 1

使用しているハードウェア/C++の実装などがわからないため、「最速」の方法があると言う人は誰でも嘘つきです。

これが1つの方法です：

typedef pair<int,int> item;

vector<item> mytmp(mymap.begin(), mymap.end());
sort(mytmp.begin(), mytmp.end(), [](item lhs, item rhs) { return lhs.second < rhs.second; });

vector<int> myvec;
myvec.reserve(mytmp.size());
transform(
    mytmp.begin(), mytmp.end(),
    back_inserter(myvec);
    [](item i) { return i.first; }
);

Answer 2

<key,value>ペアを に交換する 2 番目のマップを作成できます<value,key>。ただし、値が重複していると問題が発生します。

実際に必要なのは双方向マップです。たとえば、http://www.boost.org/doc/libs/1_47_0/libs/bimap/doc/html/index.html を参照してください。

Answer 3

それをaに入れてからstd::vector<std::pair<int, int> >、2番目の値でソートする述語を書くことができます。次に、ペアの最初の値を介してキーにアクセスします。

std::map<int, int>         the_map;
typedef std::pair<int,int> pair_type;

the_map[1] = 2;
the_map[2] = 1;
the_map[3] = 8;
the_map[4] = 8;
the_map[5] = 3;

struct Pred {
    bool operator()(pair_type const& a, pair_type const& b) const {
        return (a.second < b.second);
    }   
};  
struct Tran {
    int operator()(pair_type const& a) const {
        return a.first;
    }   
};  

std::vector<pair_type>     vec(the_map.begin(), the_map.end());
std::sort(vec.begin(), vec.end(), Pred());

std::vector<int>           result;
transform(vec.begin(), vec.end(),  std::back_inserter(result), Tran());

BOOST_FOREACH(int const& r, result) {
    cout << r << endl;
}