STL mapをvalueでソートする方法

Question

mapをvalueでソートする方法を探しています。

 

例えば、

 map<long, long>

  100,  1

  200,  3

  300,  2

というデータがあった場合に、valueで昇順ソートして

  100,  1

  300,  2

  200,  3

の順番で取得したいのですが、どうしてよいのか困っています。

自分なりに調べて、ソートする内容を定義できる

temlpate<class RandomAccessIterator, class Compare>
  void
    sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

が使えるのではないかと思ったのですが、これをどう使っていいのか分かりませんでした・・・。

 

どなたか、mapをvalueでソートする方法をご存知の方はいらっしゃいませんか？

また、参考となるURLを教えていただけると幸いです。

 

よろしくお願い致します。

Answer 1

map は必ず key でソートされるものです。

 

以下、例です。

typedef map<int, int> INTMAP;

INTMAP myMap;

 

myMap.insert(INTMAP::value_type(300, 2));

myMap.insert(INTMAP::value_type(200, 3));

myMap.insert(INTMAP::value_type(100, 5));

myMap.insert(INTMAP::value_type(400, 4));

myMap.insert(INTMAP::value_type(500, 1));

 

INTMAP::const_iterator it;

for (it = myMap.begin(); it != myMap.end(); it++)

{

  cout << "(" << (*it).first << ", " << (*it).second << ")" << endl;

}

 

 

出力：

(100, 5)

(200, 3)

(300, 2)

(400, 4)

(500, 1)

つまり、map を使って value でソートはできません。

 

EggRoll さんの例をみると、key と value を入れ替えれば簡単だと思いますが。

（key の重複はできませんけど）

 

あとは、vector とか list を使って pair を管理するしかないのでは。

Answer 2

# 出番か? ^^;

> mapをvalueでソートする方法を探しています。

 

まず、mapに入れたままでsortするのは無理です。
そんなことしたらmapの要素管理がぐだぐだになっちまいます。
なので一旦外に取り出すことになります。
あるいは、ハナっからmapなんか使わず、vectorにでもぶっこんどいて
テキトーにsortするか。

 

mapから取り出してvalueでsortする試み:

 

Code Snippet

#include <iostream>
#include <map>
#include <queue>
#include <string>

typedef std::map<int,std::string> container;
typedef std::pair<int,std::string> value_type;

struct second_order {
  bool operator()(const value_type& x, const value_type& y) const {
    return x.second > y.second;
  }
};

int main() {
  container src;
  src[0] = "zero";
  src[1] = "one";
  src[2] = "two";
  src[3] = "three";
  src[4] = "four";
  src[5] = "five";
  src[6] = "six";
  src[7] = "seven";
  src[8] = "eight";
  src[9] = "nine";
  std::priority_queue<value_type, std::vector<value_type>, second_order> que;
  for ( container::iterator iter = src.begin(); iter != src.end(); ++iter ) {
    que.push(*iter);
  }
  while ( !que.empty() ) {
    value_type item = que.top();
    std::cout << item.first << '/' << item.second << std::endl;
    que.pop();
  }
}