如何对C++ std::unordered_map进行稳定排序——保留相等元素插入顺序

我之前也碰到过类似的需求，std::unordered_map本身是哈希表实现的，完全不保留插入顺序，而且默认没有排序能力。要实现按值（单词出现次数）排序，同时保证值相等时插入更早的元素排在前面，核心是要手动记录每个单词的插入顺序，然后在排序时把「出现次数」作为第一关键字，「插入顺序」作为第二关键字。

步骤1：扩展存储结构 #

我们需要把unordered_map的value从单纯的int（出现次数），改成包含「出现次数」和「插入序号」的结构。比如定义一个可读性更好的结构体：

struct WordStats {
    int occurrence;     // 单词出现次数
    size_t insert_seq;  // 插入顺序标记，数值越小表示插入时间越早
};

对应的哈希表类型就变成std::unordered_map<std::string, WordStats>。

步骤2：插入元素时记录插入顺序 #

需要维护一个计数器，每次插入新单词时分配当前计数器值，然后计数器自增；如果是已存在的单词，只更新出现次数，不改动插入顺序：

std::unordered_map<std::string, WordStats> word_counter;
size_t order_tracker = 0;

// 插入或更新单词的工具函数
void update_word(const std::string& word) {
    auto iter = word_counter.find(word);
    if (iter != word_counter.end()) {
        // 单词已存在，仅增加出现次数
        iter->second.occurrence++;
    } else {
        // 新单词，记录插入顺序
        word_counter[word] = {1, order_tracker++};
    }
}

步骤3：转存为vector并执行排序 #

unordered_map无法直接排序，我们需要把它的键值对转存到std::vector中，再用自定义比较器排序：

// 将哈希表元素转存到vector
std::vector<std::pair<std::string, WordStats>> sorted_list(word_counter.begin(), word_counter.end());

// 自定义排序规则：先按出现次数排序（这里用降序，按需调整），次数相同时按插入顺序升序
std::sort(sorted_list.begin(), sorted_list.end(),
    [](const auto& lhs, const auto& rhs) {
        if (lhs.second.occurrence != rhs.second.occurrence) {
            return lhs.second.occurrence > rhs.second.occurrence;
        } else {
            // 次数相等时，插入顺序更早的元素排在前面
            return lhs.second.insert_seq < rhs.second.insert_seq;
        }
    });

效果验证 #

比如依次插入："apple"、"banana"、"apple"、"cherry"、"banana"，最终排序结果会是：

• "apple"（次数2，插入序0）排在最前
• 然后是"banana"（次数2，插入序1）
• 最后是"cherry"（次数1，插入序2）
  完全符合「值相等时插入早的元素优先」的稳定性要求。

简化方案（可选） #

如果不想定义结构体，也可以用std::pair<int, size_t>作为value，第一个元素存出现次数，第二个存插入顺序，逻辑完全一致，只是可读性稍弱。另外这里不需要用std::stable_sort——因为我们的比较器已经把插入顺序作为第二关键字，普通的std::sort就能保证值相等时的顺序。

内容的提问来源于stack exchange，提问作者A. Sarid