如何首先按值然后按键对std :: map排序? [英] How can I sort a std::map first by value, then by key?

问题描述

我需要按值，然后按键对std::map进行排序.该地图包含如下数据:

I need to sort a std::map by value, then by key. The map contains data like the following:

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

我需要按顺序获取值，但最重要的是，在按顺序排列值之后，键必须按字母顺序排列.我该怎么办?

I need to get the values in order, but the kicker is that the keys need to be in alphabetical order after the values are in order. How can I do this?

推荐答案

std::map将按keys对其元素进行排序.排序时不关心values.

std::map will sort its elements by keys. It doesn't care about the values when sorting.

您可以使用std::vector<std::pair<K,V>>，然后使用std::sort和std::stable_sort对其进行排序:

You can use std::vector<std::pair<K,V>> then sort it using std::sort followed by 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.

The first sort should use std::sort since it is nlog(n), and then use std::stable_sort which is n(log(n))^2 in the worst case.

请注意，出于性能原因选择了std::sort时，需要使用std::stable_sort进行正确的排序，因为您希望保留按值排序.

Note that while std::sort is chosen for performance reason, std::stable_sort is needed for correct ordering, as you want the order-by-value to be preserved.

@gsf，如果选择首先比较values的比较器，并且如果它们相等，则可以使用 std::sort.keys.

@gsf noted in the comment, you could use only std::sort if you choose a comparer which compares values first, and IF they're equal, sort the 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:

But wait, there is a better approach: store std::pair<V,K> instead of std::pair<K,V> and then you don't need any comparer at all — the standard comparer for std::pair would be enough, as it compares first (which is V) first then second which is K:

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

应该很好.

这篇关于如何首先按值然后按键对std :: map排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！