問(wèn)題描述
我需要先按值對(duì) std::map 進(jìn)行排序，然后再按鍵排序.該地圖包含如下數(shù)據(jù):
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
我需要按順序獲取值，但關(guān)鍵是在值按順序排列后，鍵需要按字母順序排列.我該怎么做?
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 對(duì)其元素進(jìn)行排序.排序時(shí)它不關(guān)心 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 對(duì)其進(jìn)行排序:
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);
第一個(gè)排序應(yīng)該使用std::sort，因?yàn)樗?code>nlog(n)，然后使用std::stable_sortn(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.
請(qǐng)注意，雖然選擇 std::sort 是出于性能原因，但需要 std::stable_sort 才能正確排序，因?yàn)槟Ｍ粗蹬判虮槐４?
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 在評(píng)論中指出，如果您選擇首先比較 values 的比較器，則可以使用 only std::sort，并且如果它們相等，則對(duì) keys 進(jìn)行排序.
@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);
那應(yīng)該是有效的.
但是等等，有一個(gè)更好的方法:存儲(chǔ) std::pair 而不是 std::pair 然后你根本不需要任何比較器—std::pair 的標(biāo)準(zhǔn)比較器就足夠了，因?yàn)樗紫缺容^ 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());
那應(yīng)該很好用.
這篇關(guān)于如何首先按值對(duì) std::map 排序，然后按鍵排序?的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！