C++ 如何首先按值对 std::map 排序，然后按键排序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19842035/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can I sort a std::map first by value, then by key?
提问by Trevor Hutto
I need to sort a std::mapby value, then by key. The map contains data like the following:
我需要std::map按值排序，然后按键排序。该地图包含如下数据：
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?
我需要按顺序获取值，但关键是在值按顺序排列后，键需要按字母顺序排列。我怎样才能做到这一点？
回答by Nawaz
std::mapwill sort its elements by keys. It doesn't care about the valueswhen sorting.
std::map将按 对其元素进行排序keys。它不关心values何时排序。
You can use std::vector<std::pair<K,V>>then sort it using std::sortfollowed by std::stable_sort:
您可以使用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);
The first sort should use std::sortsince it is nlog(n), and then use std::stable_sortwhich is n(log(n))^2in the worst case.
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_sortwhich n(log(n))^2。
Note that while std::sortis chosen for performance reason, std::stable_sortis needed for correct ordering, as you want the order-by-value to be preserved.
请注意，whilestd::sort是出于性能原因选择的，std::stable_sort正确排序需要它，因为您希望保留按值排序。
@gsf noted in the comment, you could use onlystd::sortif you choose a comparer which compares valuesfirst, and IF they're equal, sort the keys.
@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);
That should be efficient.
那应该是有效率的。
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::pairwould be enough, as it compares first(which is V) first then secondwhich is K:
但是等等，有一个更好的方法：存储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());
That should work great.
那应该很好用。
回答by ks1322
You can use std::setinstead of std::map.
您可以使用std::set代替std::map.
You can store both key and value in std::pairand the type of container will look like this:
您可以同时存储键和值std::pair，容器的类型将如下所示：
std::set< std::pair<int, std::string> > items;
std::setwill sort it's values both by original keys and values that were stored in std::map.
std::set将按原始键和存储在std::map.
回答by honk
As explained in Nawaz'sanswer, you cannot sort your map by itself as you need it, because std::mapsorts its elements based on the keys only. So, you need a different container, but if you have to stick to your map, then you can still copy its content (temporarily) into another data structure.
正如Nawaz 的回答中所解释的，您不能根据需要自行对地图进行排序，因为std::map仅根据键对其元素进行排序。所以，你需要一个不同的容器，但如果你必须坚持你的地图，那么你仍然可以将其内容（临时）复制到另一个数据结构中。
I think, the best solution is to use a std::setstoring flipped key-value pairs as presented in ks1322'sanswer.
The std::setis sorted by default and the order of the pairsis exactly as you need it:
我认为，最好的解决方案是使用std::set存储翻转的键值对，如ks1322's answer 中所示。在std::set默认情况下，排序，并在对顺序是完全一样的，你需要它：
3) If
lhs.first<rhs.first, returnstrue. Otherwise, ifrhs.first<lhs.first, returnsfalse. Otherwise, iflhs.second<rhs.second, returnstrue. Otherwise, returnsfalse.
3) 如果
lhs.first<rhs.first，则返回true。否则，如果rhs.first<lhs.first，则返回false。否则，如果lhs.second<rhs.second，则返回true。否则，返回false。
This way you don't need an additional sorting step and the resulting code is quite short:
这样你就不需要额外的排序步骤，结果代码很短：
std::map<std::string, int> m; // Your original map.
m["realistically"] = 1;
m["really"] = 8;
m["reason"] = 4;
m["reasonable"] = 3;
m["reasonably"] = 1;
m["reassemble"] = 1;
m["reassembled"] = 1;
m["recognize"] = 2;
m["record"] = 92;
m["records"] = 48;
m["recs"] = 7;
std::set<std::pair<int, std::string>> s; // The new (temporary) container.
for (auto const &kv : m)
s.emplace(kv.second, kv.first); // Flip the pairs.
for (auto const &vk : s)
std::cout << std::setw(3) << vk.first << std::setw(15) << vk.second << std::endl;
Output:
输出：
1 realistically
1 reasonably
1 reassemble
1 reassembled
2 recognize
3 reasonable
4 reason
7 recs
8 really
48 records
92 record
Note: Since C++17you can use range-based for loopstogether with structured bindingsfor iterating over a map. As a result, the code for copying your map becomes even shorter and more readable:
注意：从C++17 开始，您可以使用基于范围的 for 循环和结构化绑定来迭代映射。因此，用于复制地图的代码变得更短且更具可读性：
for (auto const &[k, v] : m)
s.emplace(v, k); // Flip the pairs.
回答by rerun
std::mapalready sorts the values using a predicate you define or std::lessif you don't provide one. std::setwill also store items in order of the of a define comparator. However neither set nor map allow you to have multiple keys. I would suggest defining a std::map<int,std::set<string>if you want to accomplish this using your data structure alone. You should also realize that std::lessfor string will sort lexicographically not alphabetically.
std::map已经使用您定义的谓词对值进行排序，或者std::less如果您不提供谓词。 std::set还将按定义比较器的顺序存储项目。但是无论是 set 还是 map 都不允许你有多个键。std::map<int,std::set<string>如果你想单独使用你的数据结构来完成这个，我建议定义一个。您还应该意识到std::lessfor string 将按字典顺序而不是按字母顺序排序。
回答by Matt
EDIT: The other two answers make a good point. I'm assuming that you want to order them into some other structure, or in order to print them out.
编辑：另外两个答案是一个很好的观点。我假设您想将它们排序为其他结构，或者为了将它们打印出来。
"Best" can mean a number of different things. Do you mean "easiest," "fastest," "most efficient," "least code," "most readable?"
“最佳”可能意味着许多不同的东西。您的意思是“最简单”、“最快”、“最高效”、“最少代码”、“最易读”吗？
The most obvious approach is to loop through twice. On the first pass, order the values:
最明显的方法是循环两次。在第一遍中，对值进行排序：
if(current_value > examined_value)
{
current_value = examined_value
(and then swap them, however you like)
}
Then on the second pass, alphabetize the words, but only if their values match.
然后在第二遍，按字母顺序排列单词，但前提是它们的值匹配。
if(current_value == examined_value)
{
(alphabetize the two)
}
Strictly speaking, this is a "bubble sort" which is slow because every time you make a swap, you have to start over. One "pass" is finished when you get through the whole list without making any swaps.
严格来说，这是一种缓慢的“冒泡排序”，因为每次进行交换时，都必须重新开始。当您通过整个列表而不进行任何交换时，一个“通过”就完成了。
There are other sorting algorithms, but the principle would be the same: order by value, then alphabetize.
还有其他排序算法，但原理是相同的：按值排序，然后按字母顺序排序。
