C++ 中 unordered_map 遍历删除元素时的迭代器失效问题及解决方案

创智夏令营机考时没能解决的一个小问题，导致一道简单题爆0

在 C++ 编程中，使用关联容器（如 unordered_map）进行遍历并删除元素时，迭代器失效是一个常见且容易被忽视的问题。本文将通过具体案例分析迭代器失效的原理，并提供正确的解决方案，帮助开发者避免此类陷阱。

一、问题场景：遍历 unordered_map 并删除元素

假设我们需要实现一个简单的频率统计功能，当容器中的元素数量超过阈值时，对所有元素的计数减 1，并删除计数为 0 的元素。以下是一段看似合理但存在隐患的代码：

#include <unordered_map>

void process(unordered_map<int, int>& cnt) {
    for (auto it = cnt.begin(); it != cnt.end(); it++) { // 隐患在此处
        it->second--;
        if (it->second == 0) {
            cnt.erase(it); // 迭代器失效！
        }
    }
}

问题分析：

• 迭代器失效原理：在 unordered_map 中，当调用 erase 删除元素时，指向被删除元素的迭代器会立即失效，且其他迭代器的有效性不确定（标准未保证）。
• 后果：上述代码中，erase(it) 会导致 it 失效，后续的 it++ 会引发未定义行为（程序可能崩溃或产生错误结果）。

二、迭代器失效的分类与规则

C++ 标准库中，不同容器的迭代器失效规则不同。对于 unordered_map（属于无序关联容器），关键规则如下：

1. 单个元素删除：
   • 删除单个元素时，指向该元素的迭代器失效。
   • 其他迭代器的有效性未被保证（可能有效，也可能无效，取决于具体实现）。
2. 范围删除或清空容器：
   • 所有迭代器均失效。

对比有序关联容器（如 map）：

• 删除单个元素时，指向该元素的迭代器失效，其他迭代器保持有效。

三、解决方案：正确处理迭代器失效

为了在遍历 unordered_map 时安全地删除元素，需确保每次删除后迭代器指向有效位置。

使用后置自增运算符获取下一个迭代器

在 erase 函数调用时，利用其返回值（指向下一个元素的迭代器）更新当前迭代器：

for (auto it = cnt.begin(); it != cnt.end();) { // 注意：不使用 it++
    it->second--;
    if (it->second == 0) {
        it = cnt.erase(it); // erase 返回下一个有效迭代器
    } else {
        it++; // 未删除时手动递增迭代器
    }
}

关键点：

• erase 的返回值：unordered_map::erase 返回一个迭代器，指向删除元素之后的下一个元素（若删除的是最后一个元素，则指向 end()）。
• 条件分支：根据是否删除元素，决定是更新迭代器（it = cnt.erase(it)）还是手动递增（it++）。