C++中对map的value进行排序的方法总结

在C++中，std::map默认基于键（Key）排序，若需按值（Value）排序，需借助间接方法。

一、Vector转换法（最通用）

原理：将map的键值对拷贝到vector中，利用std::sort结合Lambda表达式按值排序。
步骤：

将map转为vector<pair<Key, Value>>
使用自定义比较器对vector排序
遍历排序后的vector获取结果

代码示例：

std::map<std::string, int> myMap = {{"apple", 5}, {"banana", 3}};
std::vector<std::pair<std::string, int>> vec(myMap.begin(), myMap.end());

// 按值降序排序
std::sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
    return a.second > b.second;
});

// 按值升序排序
std::sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
    return a.second < b.second;
});

特点：

灵活性：支持升序/降序、多条件排序（如值相同则按键排序）
适用场景：临时排序、输出结果
时间复杂度：O(n log n)

二、构造新容器法

原理：通过交换键值对构造新容器（如std::multimap），利用其自动排序特性。
步骤：

创建临时容器，将原map的value作为新容器的key
插入键值对时交换key和value

代码示例：

std::map<std::string, int> originalMap = {{"apple", 5}, {"banana", 3}};
std::multimap<int, std::string, std::greater<int>> sortedMap; // 降序

for (const auto& pair : originalMap) {
    sortedMap.emplace(pair.second, pair.first); // 交换key-value
}

特点：

数据唯一性：若值可能重复，需用multimap而非map
适用场景：需要持久化按值排序的结构
限制：需额外空间，且无法保留原键值对的完整结构

三、优先队列法

原理：使用std::priority_queue动态维护极值。
步骤：

定义优先队列，自定义比较器
插入所有键值对
弹出元素获取排序结果

代码示例：

auto comp = [](const std::pair<std::string, int>& a, 
               const std::pair<std::string, int>& b) {
    return a.second < b.second; // 大顶堆（降序）
};
std::priority_queue<std::pair<std::string, int>, 
                    std::vector<std::pair<std::string, int>>, 
                    decltype(comp)> pq(comp);

for (const auto& pair : myMap) pq.push(pair);

特点：

动态维护：适合实时插入数据并获取Top K结果
时间复杂度：插入O(log n)，弹出O(1)

四、自定义比较器法

原理：通过自定义函数对象（Functor）或Lambda定义排序规则。
适用场景：结合std::multimap时，需基于值字段排序。

代码示例：

struct ValueComparator {
    bool operator()(const Account* a1, const Account* a2) const {
        return a1->money > a2->money; // 按金额降序
    }
};

std::multimap<ID_CARD, Account*, ValueComparator> sortedAccounts;

特点：

复杂排序：支持按对象内部字段排序
底层依赖：需理解红黑树排序机制

五、性能与场景对比

方法	时间复杂度	空间复杂度	适用场景
Vector转换法	O(n log n)	O(n)	通用、临时排序
构造新容器法	O(n log n)	O(n)	需要持久化排序的结构
优先队列法	O(n log k)	O(k)	动态维护Top K（如高频词）
自定义比较器法	O(n log n)	O(n)	复杂对象的多条件排序