[c++] Sorting std::map using value

I need to sort an std::map by value rather than by key. Is there an easy way to do it?

I got one solution from the follwing thread:
std::map sort by data?
Is there a better solution?

map<long, double> testMap;
// some code to generate the values in the map.

sort(testMap.begin(), testMap.end());  // is there any function like this to sort the map?

In the following sample code, I wrote an simple way to output top words in an word_map map where key is string (word) and value is unsigned int (word occurrence).

The idea is simple, find the current top word and delete it from the map. It's not optimized, but it works well when the map is not large and we only need to output the top N words, instead of sorting the whole map.

const int NUMBER_OF_TOP_WORDS = 300;
for (int i = 1; i <= NUMBER_OF_TOP_WORDS; i++) {
  if (word_map.empty())
    break;
  // Go through the map and find the max item.
  int max_value = 0;
  string max_word = "";
  for (const auto& kv : word_map) {
    if (kv.second > max_value) {
      max_value = kv.second;
      max_word = kv.first;
    }
  }
  // Erase this entry and print.
  word_map.erase(max_word);
  cout << "Top:" << i << " Count:" << max_value << " Word:<" << max_word << ">" <<     endl;
}

In this context, we should convert map to multimap. I think convert map to set is not good because we will lose many information in case of there is many duplicate values in the original map. Here is my solution, I defined the less than comparator that sort by value (cmp function). We can customize the cmp function as our demand.

std::map<int, double> testMap = { {1,9.1}, {2, 8.0}, {3, 7.0}, {4,10.5} };
auto cmp = [](const double &lhs,
              const double &rhs)->bool
{
    return lhs < rhs;
};
std::multimap<double, int, decltype(cmp)> mmap(cmp);
for (auto item : testMap)
    mmap.insert(make_pair(item.second, item.first));

I needed something similar, but the flipped map wouldn't work for me. I just copied out my map (freq below) into a vector of pairs, then sorted the pairs however I wanted.

std::vector<std::pair<int, int>> pairs;
for (auto itr = freq.begin(); itr != freq.end(); ++itr)
    pairs.push_back(*itr);

sort(pairs.begin(), pairs.end(), [=](std::pair<int, int>& a, std::pair<int, int>& b)
{
    return a.second < b.second;
}
);

To build on Oli's solution (https://stackoverflow.com/a/5056797/2472351) using multimaps, you can replace the two template functions he used with the following:

template <typename A, typename B>
multimap<B, A> flip_map(map<A,B> & src) {

    multimap<B,A> dst;

    for(map<A, B>::const_iterator it = src.begin(); it != src.end(); ++it)
        dst.insert(pair<B, A>(it -> second, it -> first));

    return dst;
}

Here is an example program that shows all the key-value pairs being preserved after performing the flip.

#include <iostream>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

template <typename A, typename B>
multimap<B, A> flip_map(map<A,B> & src) {

    multimap<B,A> dst;

    for(typename map<A, B>::const_iterator it = src.begin(); it != src.end(); ++it)
        dst.insert(pair<B, A>(it -> second, it -> first));

    return dst;
}

int main() {

    map<string, int> test;
    test["word"] = 1;
    test["spark"] = 15;
    test["the"] = 2;
    test["mail"] = 3;
    test["info"] = 3;
    test["sandwich"] = 15;

    cout << "Contents of original map:\n" << endl;
    for(map<string, int>::const_iterator it = test.begin(); it != test.end(); ++it)
        cout << it -> first << " " << it -> second << endl; 

    multimap<int, string> reverseTest = flip_map(test);

    cout << "\nContents of flipped map in descending order:\n" << endl;
    for(multimap<int, string>::const_reverse_iterator it = reverseTest.rbegin(); it != reverseTest.rend(); ++it)
        cout << it -> first << " " << it -> second << endl; 

    cout << endl;
}

Result:

You can't sort a std::map this way, because a the entries in the map are sorted by the key. If you want to sort by value, you need to create a new std::map with swapped key and value.

map<long, double> testMap;
map<double, long> testMap2;

// Insert values from testMap to testMap2
// The values in testMap2 are sorted by the double value

Remember that the double keys need to be unique in testMap2 or use std::multimap.

A std::map sorted by it's value is in essence a std::set. By far the easiest way is to copy all entries in the map to a set (taken and adapted from here)

template <typename M, typename S> 
void MapToSet( const  M & m, S & s )
{
    typename M::const_iterator end = m.end();
    for( typename M::const_iterator it = m.begin(); it != end ; ++it )
    {
        s.insert( it->second );
    }
}

One caveat: if the map contains different keys with the same value, they will not be inserted into the set and be lost.

Another solution would be the usage of std::make_move_iterator to build a new vector (C++11 )

    int main(){

      std::map<std::string, int> map;
       //Populate map

      std::vector<std::pair<std::string, int>> v {std::make_move_iterator(begin(map)),
                                      std::make_move_iterator(end(map))};
       // Create a vector with the map parameters

       sort(begin(v), end(v),
             [](auto p1, auto p2){return p1.second > p2.second;});
       // Using sort + lambda function to return an ordered vector 
       // in respect to the int value that is now the 2nd parameter 
       // of our newly created vector v
  }

I like the the answer from Oli (flipping a map), but seems it has a problem: the container map does not allow two elements with the same key.

A solution is to make dst the type multimap. Another one is to dump src into a vector and sort the vector. The former requires minor modifications to Oli's answer, and the latter can be implemented using STL copy concisely

#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  map<int, int> m;
  m[11] = 1;
  m[22] = 2;
  m[33] = 3;

  vector<pair<int, int> > v;
  copy(m.begin(),
       m.end(),
       back_inserter<vector<pair<int, int> > >(v));

  for (size_t i = 0; i < v.size(); ++i) {
    cout << v[i].first << " , " << v[i].second << "\n";
  }

  return 0;
};

Flipped structure might no longer be a map but rather a multimap, thus in the flip_map example above not all elements from B will necessarily appear in the resulting data structure.

If you want to present the values in a map in sorted order, then copy the values from the map to vector and sort the vector.

U can consider using boost::bimap that might gave you a feeling that map is sorted by key and by values simultaneously (this is not what really happens, though)