How to Efficiently Sort a std::map by Value?

How to Sort std::map by Value

Sorting an std::map by value instead of key can be challenging. One common solution is to create a temporary multimap that flips the key-value pairs and sort that instead. However, there are alternative techniques that can provide a cleaner and more versatile approach.

Flipping the Pairs

The following code snippet demonstrates how to flip the key-value pairs in an std::map to create a new multimap sorted by value:

template<typename A, typename B>
std::pair<B,A> flip_pair(const std::pair<A,B> &amp;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> &amp;src)
{
    std::multimap<B,A> dst;
    std::transform(src.begin(), src.end(), std::inserter(dst, dst.begin()), 
                   flip_pair<A,B>);
    return dst;
}

By calling flip_map on the original std::map, you can obtain a multimap sorted by value.

Generic Associative Source

This approach can be generalized to flip associative containers of any type using variadic templates:

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

This generic overload works with any associative container that supports the std::transform algorithm, including std::map and std::unordered_map.

The above is the detailed content of How to Efficiently Sort a std::map by Value?. For more information, please follow other related articles on the PHP Chinese website!