C / C++ / 系统课时
rehash 为什么会影响迭代器
rehash 为什么会影响迭代器
unordered_map 和 unordered_set 的元素由哈希值分配到桶中。桶数量一旦因扩容或显式调用发生变化,元素需要重新决定所属桶,因此旧迭代器保存的遍历位置不再可靠。本篇通过可运行示例观察这一变化,并给出安全写法。
学习目标
- 理解
rehash与桶数量、负载因子的关系 - 判断哪些操作可能让已有迭代器失效
- 在可能扩容的代码中正确保存和重新获取元素
什么时候会发生 rehash
unordered 容器用 bucket_count() 表示当前桶数量,用 load_factor() 表示元素数量与桶数量之比。插入元素后如果负载因子需要超过 max_load_factor(),实现通常会增加桶数量并重新建立桶结构;显式调用 rehash() 或 reserve() 也可能触发同样的过程。
rehash(n) 的目标是让桶数量至少满足参数和当前元素数量的要求,而 reserve(n) 更适合表达“准备容纳大约 n 个元素”。具体采用多少个桶由标准库实现决定,因此不要把某个固定桶数量写进业务逻辑。

为什么旧迭代器会失效
迭代器不仅代表“这个元素是谁”,还参与容器的遍历结构。rehash 后桶数组改变,元素所在桶以及桶之间的遍历关系都可能变化,所以标准规定 rehash 会使该容器的全部迭代器失效。此后继续解引用旧迭代器属于未定义行为。
但 rehash 不会移动或销毁元素本身,因此指向元素的引用和指针仍然有效。这个区别很重要:如果只需要持续访问某个值,可以保存引用或指针;如果后续还要继续使用迭代器操作容器,应在 rehash 后通过 find() 等接口重新获取。
用代码观察桶数量变化
下面的程序先取得一个迭代器和一个指向元素值的指针,再持续插入元素,直到检测到 bucket_count() 改变。发生 rehash 后,程序不再访问旧迭代器,而是重新执行 find()。
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> users{
{1, "alice"},
{2, "bob"}
};
users.max_load_factor(0.7f);
auto it = users.find(1);
std::string* valuePtr = &it->second;
const std::size_t oldBucketCount = users.bucket_count();
int key = 100;
while (users.bucket_count() == oldBucketCount) {
users.emplace(key++, "temp");
}
const std::size_t newBucketCount = users.bucket_count();
auto freshIt = users.find(1);
std::cout << std::boolalpha;
std::cout << "rehash happened: "
<< (newBucketCount != oldBucketCount) << '\n';
std::cout << "saved pointer value: " << *valuePtr << '\n';
std::cout << "fresh iterator value: " << freshIt->second << '\n';
}预期输出
rehash happened: true
saved pointer value: alice
fresh iterator value: alice实际的旧桶数量、新桶数量以及触发扩容前插入了多少元素会因标准库实现而不同,因此示例只验证“桶数量发生变化”这一稳定事实。
怎样避免意外失效
如果能提前估算元素规模,可以在获取长期使用的迭代器之前调用 reserve(),减少后续插入触发 rehash 的机会。例如先执行 users.reserve(1000),再进行一批不超过预估规模的插入,比在循环中一边持有迭代器一边任由容器扩容更稳妥。
不过 reserve() 本身也可能立即 rehash,所以应把它放在创建需要保留的迭代器之前。不能确定后续是否会扩容时,最安全的做法是只保存键,在结构变化后重新 find()。
需要记住的失效边界
普通插入如果 没有 触发 rehash,已有迭代器仍可继续使用;一旦插入导致 rehash,全部迭代器都会失效。删除元素时,通常只有指向被删除元素的迭代器失效。无论哪种情况,都不要用已经失效的迭代器做比较、递增或解引用。
因此,判断迭代器能否继续使用时,不要只看调用的是 insert() 还是 emplace(),而要继续追问:这次操作有没有改变桶结构。