如何将std::map的Compare模板参数用于值比较？

首先要明确一个核心点：std::map的Compare模板参数从设计上就是用来比较键（Key）的，而不是值（T）——这是C++标准规定的行为，不是GNU实现的特例。你传入的std::greater<T>（也就是std::greater<std::size_t>）被错误地用来比较char类型的键，这就是输出不符合预期的原因：char会被隐式转换为size_t（ASCII码），'C'(67) > 'B'(66) > 'A'(65)，所以输出顺序是C、B、A。

如果你想要实现基于值排序的键值对容器，有几种可行的方案：

方案1：用std::set存储反转的键值对 #

既然std::set的比较器作用于存储的元素本身，我们可以把值作为pair的第一个元素，键作为第二个元素，这样std::greater<T>就会直接比较值的大小：

#include <set>
#include <iostream>
#include <functional>

namespace nonstd {
    template <class Key, class T, class Compare = std::greater<T>, class Allocator = std::allocator<std::pair<T, Key>> >
    using value_sorted_map = std::set<std::pair<T, Key>, Compare, Allocator>;
}

int main() {
    // 注意这里存储的是 {值, 键}
    nonstd::value_sorted_map<char, std::size_t> values = { {3, 'A'}, {2, 'B'}, {5, 'C'} };
    for (auto const& value : values) {
        std::clog << value.second << " : " << value.first << std::endl;
    }
}

这段代码会输出你预期的结果：

C : 5
A : 3
B : 2

⚠️ 注意：如果存在相同的值，std::pair会自动比较第二个元素（键）来保证唯一性，这和std::map的行为一致。

方案2：封装自定义容器（兼顾键访问和值排序） #

如果你需要保留std::map的键访问特性（比如用[]或find()快速查找键），同时还要按值排序，可以封装一个自定义容器，内部同时维护std::map和排序后的std::vector：

#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>

template <class Key, class T, class Compare = std::greater<T>>
class ValueSortedMap {
private:
    std::map<Key, T> m_map;
    std::vector<std::pair<Key, T>> m_sorted_values;
    Compare m_comp;

    void sync_sorted() {
        m_sorted_values.clear();
        for (const auto& pair : m_map) {
            m_sorted_values.push_back(pair);
        }
        // 按值排序，使用传入的比较器
        std::sort(m_sorted_values.begin(), m_sorted_values.end(),
            [this](const std::pair<Key, T>& a, const std::pair<Key, T>& b) {
                return m_comp(a.second, b.second);
            });
    }

public:
    void insert(const std::pair<Key, T>& pair) {
        m_map.insert(pair);
        sync_sorted();
    }

    // 提供类似map的访问接口
    T& operator[](const Key& key) {
        auto& res = m_map[key];
        sync_sorted();
        return res;
    }

    // 提供遍历排序后元素的接口
    auto begin() const { return m_sorted_values.begin(); }
    auto end() const { return m_sorted_values.end(); }
};

int main() {
    ValueSortedMap<char, std::size_t> values;
    values.insert({'A', 3});
    values.insert({'B', 2});
    values.insert({'C', 5});

    for (const auto& value : values) {
        std::clog << value.first << " : " << value.second << std::endl;
    }
}

这个方案的优点是既可以快速按键查找，又能按值排序输出，缺点是每次修改容器都需要重新排序，性能上会有额外开销。

方案3：使用Boost.MultiIndex（进阶） #

如果你的项目已经在使用Boost库，boost::multi_index_container是更专业的选择——它支持为容器添加多个索引，比如一个按键索引（用于快速查找），一个按值排序的索引（用于遍历）。这种方案性能更优，也更灵活，适合复杂场景。

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