std :: map,如何按值排序,然后按键排序

Question

我需要按值排序地图,然后按键排序.我有一张包含这样内容的地图......

  1  realistically
  8         really
  4         reason
  3     reasonable
  1     reasonably
  1     reassemble
  1    reassembled
  2      recognize
 92         record
 48        records
  7           recs

我需要按顺序获取值,但是关键是在值按顺序后键需要按字母顺序排列.最好的方法是什么？

Answer 1

std::map将按其排序元素keys.它不关心values何时排序.

您可以使用std::vector<std::pair<K,V>>然后使用std::sort后跟std::stable_sort:

std::vector<std::pair<K,V>> items;

//fill items

//sort by value using std::sort
std::sort(items.begin(), items.end(), value_comparer);

//sort by key using std::stable_sort
std::stable_sort(items.begin(), items.end(), key_comparer);

第一次排序应该使用std::sort,因为它nlog(n),然后用std::stable_sort这是n(log(n))^2最坏的情况.

请注意,虽然std::sort是出于性能原因而选择,但std::stable_sort正确排序需要,因为您希望保留按值排序.

@gsf在注释中注明,只有 std::sort在选择values首先进行比较的比较器时,才可以使用,如果它们相等,则排序keys.

auto cmp = [](std::pair<K,V> const & a, std::pair<K,V> const & b) 
{ 
     return a.second != b.second?  a.second < b.second : a.first < b.first;
};
std::sort(items.begin(), items.end(), cmp);

这应该是有效的.

但是等等,有一个更好的方法:存储std::pair<V,K>代替,std::pair<K,V>然后你根本不需要任何比较器 - 标准比较器std::pair就足够了,因为它先比较first(这是V)然后second是K:

std::vector<std::pair<V,K>> items;
//...
std::sort(items.begin(), items.end());

这应该很有效.

Answer 2

你可以用std::set而不是std::map.

您可以存储键和值std::pair,容器的类型将如下所示:

std::set< std::pair<int, std::string> > items;

std::set将通过原始键和存储的值对它的值进行排序std::map.