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

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

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

• sorting map using value
• std::map how to sort by value, then by key
• C++ how to copy a map to a vector

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

样例输入为 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;

}

此时输出为

1 : 1 4 : 1 5 : 2 2 : 2 3 : 2

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

要想使用自定义的比较方法排序,一种方法为将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 = { 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;

}

此时输出为

2 : 2 3 : 2 5 : 2 1 : 1 4 : 1

满足条件