如何使用比较器对C++ multimap排序并让修改作用于原容器

• multimap属于有序关联容器，底层为红黑树结构，内部排序规则由容器声明时的比较器模板参数决定，默认仅按照key升序排列，该规则容器初始化后无法修改。
• std::sort仅支持传入随机访问迭代器，multimap的迭代器是双向迭代器，无法直接用std::sort排序。
• 你示例中原multimap<string, int>类型的容器，天生只能按string类型的key排序，不可能将内部排序规则修改为按value排序，遍历输出永远会按key的字典序排列。

可行替代方案 #

如果你需要得到按value排序的关联存储结构，可以选用以下两种方案：

方案1：使用自定义比较器的multiset存储排序后的元素 #

multiset支持自定义比较器对整个元素做排序，可以直接保留原键值对结构，按指定规则排序：

#include <bits/stdc++.h>
using namespace std;

// 自定义比较器：先按value升序，value相同再按key升序，避免值相同的元素被判定为重复
struct CmpByValue {
    bool operator()(const pair<string, int>& a, const pair<string, int>& b) const {
        return a.second != b.second ? a.second < b.second : a.first < b.first;
    }
};

int main()
{
    multimap<string, int> M = { { "GfG", 3 }, { "To", 2 }, { "Welcome", 1 } };
    
    // 直接用原multimap的元素构造按value排序的multiset
    multiset<pair<string, int>, CmpByValue> sorted_cont(M.begin(), M.end());
    
    // 遍历结果就是按value升序排列
    for (auto& item : sorted_cont) {
        cout << item.first << " " << item.second << endl;
    }

    return 0;
}

方案2：构造value作为key的multimap #

如果要继续使用multimap容器，可以将原键值对反转，把原value作为新multimap的key，原key作为新value，multimap默认就会按新key（原value）排序：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    multimap<string, int> M = { { "GfG", 3 }, { "To", 2 }, { "Welcome", 1 } };
    
    multimap<int, string> sorted_mmap;
    for (auto& item : M) {
        sorted_mmap.insert({item.second, item.first});
    }
    
    // 遍历输出时反转键值对即可得到原结构的排序结果
    for (auto& item : sorted_mmap) {
        cout << item.second << " " << item.first << endl;
    }

    return 0;
}

上述两种方案的输出结果均为：

Welcome 1
To 2
GfG 3

内容的提问来源于stack exchange，提问作者Zero