C++ 以vualue排序一个map

为了找工作重新拾起 C++.才发现,被 Python 宠坏后,再回头使用 c++,一下子无法适应如此复杂的情况.

回到正题,C++ 中如何排序一个 map.

我们都知道无法使用 std::sort 来排序 map,只有通过间接的方法.参考 stackoverflow 上的几个答案.

我们假设输入为一组数字,输出为数字和其出现次数,以出现次数从大到小排序,若出现次数相同,则数字小的先输出.

样例输入为 1 2 3 3 4 5 5 2
以下代码均来自(或改自) stackoverflow.

第一种方法为将map中的key和value对换,装入multimap中,multimap输出时有序.

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

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, int> num_count;
    std::map<int, int>::iterator map_it;
    int num;
    while(std::cin >> num)
        num_count[num]++;
    
    for (const auto & n : num_count)
        std::cout << n.first <<  :  << n.second << std::endl;

    std::cout << std::endl;
    
    std::multimap<int, int> dst_map = flip_map(num_count);
    for (const auto & n : dst_map)
        std::cout << n.second <<  :  << n.first << std::endl;
        return 0;
}

此时输出为

虽然是按出现次数排序,但并未满足第二条件.

要想使用自定义的比较方法排序,一种方法为将map输入到一个vector中,在自定义cmp方法,使用algorith库中sort方法来排序

#include <map>
#include <algorithm>
#include <iostream>
#include <vector>
int main (void)
{
    std::map<int, int> num_count;
    std::map<int, int>::iterator map_it;
    int num;
    while(std::cin >> num)
        num_count[num]++;
    std::vector<std::pair<int, int> > dst_vec;
    std::copy(num_count.begin(), num_count.end(),
              std::back_inserter(dst_vec));
    auto cmp = [](std::pair<int, int> const & a,std::pair<int, int> const & b)
        {
            return a.second != b.second ? a.second > b.second : a.first < b.first;
        };
    
    std::sort(dst_vec.begin(),dst_vec.end(), cmp);
    
    for(const auto & n : dst_vec)
        std::cout << n.first <<  :  << n.second << std::endl;
    return 0;
}

此时输出为

满足条件