[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?

This question is related to c++ dictionary std

The answer is


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:

enter image description here


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.


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;
}
);

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;
}

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.


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.


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;
};

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
  }

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)


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.


Examples related to c++

Method Call Chaining; returning a pointer vs a reference? How can I tell if an algorithm is efficient? Difference between opening a file in binary vs text How can compare-and-swap be used for a wait-free mutual exclusion for any shared data structure? Install Qt on Ubuntu #include errors detected in vscode Cannot open include file: 'stdio.h' - Visual Studio Community 2017 - C++ Error How to fix the error "Windows SDK version 8.1" was not found? Visual Studio 2017 errors on standard headers How do I check if a Key is pressed on C++

Examples related to dictionary

JS map return object python JSON object must be str, bytes or bytearray, not 'dict Python update a key in dict if it doesn't exist How to update the value of a key in a dictionary in Python? How to map an array of objects in React C# Dictionary get item by index Are dictionaries ordered in Python 3.6+? Split / Explode a column of dictionaries into separate columns with pandas Writing a dictionary to a text file? enumerate() for dictionary in python

Examples related to std

Converting std::__cxx11::string to std::string What is the use of "using namespace std"? How to get error message when ifstream open fails How to declare std::unique_ptr and what is the use of it? declaring a priority_queue in c++ with a custom comparator cc1plus: error: unrecognized command line option "-std=c++11" with g++ How to convert std::chrono::time_point to calendar datetime string with fractional seconds? string in namespace std does not name a type cout is not a member of std printf with std::string?