How can I sort an STL map by value?

Question

How can I implement STL map sorting by value?

For example, I have a map m:

map<int, int> m;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1;

I'd like to sort that map by m's value. So, if I print the map, I'd like to get the result as follows:

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

How can I sort the map in this way? Is there any way that I can deal with the key and value with sorted values?

Answer 1

You should use Boost.Bimap for this sort of thing.

Answer 2

I've just done a similar question in my c++ book. The answer I came up with might not be very efficient though:

int main()
{
    string s;
    map<string, int> counters;

    while(cin >> s)
        ++counters[s];

    //Get the largest and smallest values from map
    int beginPos = smallest_map_value(counters);
    int endPos = largest_map_value(counters);

    //Increment through smallest value to largest values found
    for(int i = beginPos; i <= endPos; ++i)
    {
        //For each increment, go through the map...
        for(map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it)
        {
            //...and print out any pairs with matching values
            if(it->second == i)
            {
                cout << it->first << "\t" << it->second << endl;
            }
        }
    }
    return 0;
}

//Find the smallest value for a map<string, int>
int smallest_map_value(const map<string, int>& m)
{
    map<string, int>::const_iterator it = m.begin();
    int lowest = it->second;
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
    {
        if(it->second < lowest)
            lowest = it->second;
    }
    return lowest;
}

//Find the largest value for a map<string, int>
int largest_map_value(const map<string, int>& m)
{
    map<string, int>::const_iterator it = m.begin();
    int highest = it->second;
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
    {
        if(it->second > highest)
            highest = it->second;
    }
    return highest;
}

Answer 3

Create another map, provide a less() function based on the value not key, AND the function should return true if the value1 <= value2 (not strictly < ). In this case, elements with non-distinct values can be sorted as well.

Answer 4

I wonder how can I implement the STL map sorting by value.

You can’t, by definition. A map is a data structure that sorts its element by key.

Answer 5

Based on @swegi's idea, I implemented a solution in c++11 using a multimap:

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
multimap<int, int> mm;

for(auto const &kv : m)
    mm.insert(make_pair(kv.second, kv.first));  // Flip the pairs.

for(auto const &kv : mm)
    cout << "m[" << kv.second << "] = " << kv.first << endl;  // Flip the pairs again.

Code on Ideone

I also implemented a C++11 solution based on @Chris' idea using a vector of pairs. For correct sorting, I provide a lambda expression as comparison functor:

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
using mypair = pair<int, int>;

vector<mypair> v(begin(m), end(m));

sort(begin(v), end(v), [](const mypair& a, const mypair& b) { return a.second < b.second; });

for(auto const &p : v)
    cout << "m[" << p.first << "] = " << p.second << endl;

Code on Ideone

The first solution is more compact, but both solutions should have roughly the same performance. Inserting into a multimap is of O(log n), but this has to be done for n entries, resulting in O(n log n). Sorting the vector in the second solution also results in O(n log n).

I also gave a try to @Chris' idea on using a set of pairs. However, it won't work if the values aren't all distinct. Using a functor that compares only the pair's second element doesn't help. If you first insert make_pair(1, 1) into the set and then try to insert make_pair(2, 1), then the second pair won't be inserted, because both pairs are seen as identical by that set. You can see that effect here on Ideone.

Answer 6

You can build a second map, with the first map's values as keys and the first map's keys as values.

This works only if all values are distinct. If you cannot assume this, then you need to build a multimap instead of a map.