Sorting std::map using value

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

Even though correct answers have already been posted, I thought I'd add a demo of how you can do this cleanly:

template<typename A, typename B>
std::pair<B,A> flip_pair(const std::pair<A,B> &p)
{
    return std::pair<B,A>(p.second, p.first);
}

template<typename A, typename B>
std::multimap<B,A> flip_map(const std::map<A,B> &src)
{
    std::multimap<B,A> dst;
    std::transform(src.begin(), src.end(), std::inserter(dst, dst.begin()), 
                   flip_pair<A,B>);
    return dst;
}

int main(void)
{
    std::map<int, double> src;

    ...    

    std::multimap<double, int> dst = flip_map(src);
    // dst is now sorted by what used to be the value in src!
}

---

Generic Associative Source (requires C++11)

If you're using an alternate to std::map for the source associative container (such as std::unordered_map), you could code a separate overload, but in the end the action is still the same, so a generalized associative container using variadic templates can be used for either mapping construct:

// flips an associative container of A,B pairs to B,A pairs
template<typename A, typename B, template<class,class,class...> class M, class... Args>
std::multimap<B,A> flip_map(const M<A,B,Args...> &src)
{
    std::multimap<B,A> dst;
    std::transform(src.begin(), src.end(),
                   std::inserter(dst, dst.begin()),
                   flip_pair<A,B>);
    return dst;
}

This will work for both std::map and std::unordered_map as the source of the flip.

Answer 4

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

Answer 5

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.

Answer 6

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.