How can i sort a map by its .second parameter

Question

If i have a stl map from string to int and i want to print all the int values sorted - how can i do that?

Answer 1

You cannot sort a map, it's an associative container, not a sequential, and associated containers are sorted by some internal order.

If you want to only print the int values, you could put them into a std::vector, sort the vector, and print the values.

Answer 2

You cannot sort a map by its values due to the implementation of the map.

If you want to emit the elements in the map in such a sorted order then you have to first dump the map contents into a vector (say) and sort that vector:

template <typename T1, typename T2>
struct less_second {
    typedef pair<T1, T2> type;
    bool operator ()(type const& a, type const& b) const {
        return a.second < b.second;
    }
};

map<string, int> mymap;
// …

vector<pair<string, int> > mapcopy(mymap.begin(), mymap.end());
sort(mapcopy.begin(), mapcopy.end(), less_second<string, int>());

Or alternatively, just copy the values from the map, leaving the keys, and sort the resulting vector directly.

Answer 3

You cannot do this automatically. std::map uses first value (nomen omen 'key') to sort content.

Instead, you can use boost::multi_index_container.

Answer 4

If you need to do this multiple times, it might be more efficient to keep two separate containers, e.g. your map and a sorted container like set or multiset for storing the sorted ints, rather than having to create a container and sort it on the fly. But then you have to keep them synchronized, which could get mucky. You could encapsulate that by wrapping them in a class, or better yet use a boost::multi_index_container.

Answer 5

Instead of using a vector, I'd rather just copy them to a set<int>:

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

using namespace std;

set<int> map2set(map<string, int> const& m) {
 set<int> r;
 for (map<string, int>::const_iterator b = m.begin(), e = m.end(); b != e; ++b)
   r.insert(b->second);
 return r;
}

int main() {
 map<string, int> m;
 m.insert(make_pair("hello", 42));
 m.insert(make_pair("world", 24));
 set<int> s = map2set(m);
 copy(s.begin(), s.end(), ostream_iterator<int>(cout, "\n"));
}

Answer 6

You can copy all the values into vector and sort it.

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

int get_second( pair<string, int> i ){ return i.second; }

int main(int argc, char* argv){
  map<string, int> m;
  map["tt"] = 2;
  map["rr"] = 1;
  map["ee"] = 3;

  vector<int> v( m.size() );
  transform( m.begin(), m.end(), v.begin(), get_second );
  sort( v.begin(), v.end() );
  for (int i=0; i<v.size(); i++) cout << v[i] << endl;
}