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 不会移动或销毁元素本身,因此指向元素的引用和指针仍然有效。这个区别很重要:如果只需要持续访问某个值,可以保存引用或指针;如果后续还要继续使用迭代器操作容器,应在 rehash 后通过 find() 等接口重新获取。

用代码观察桶数量变化

下面的程序先取得一个迭代器和一个指向元素值的指针,再持续插入元素,直到检测到 bucket_count() 改变。发生 rehash 后,程序不再访问旧迭代器,而是重新执行 find()。

cpp
#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';
}

预期输出

text
rehash happened: true
saved pointer value: alice
fresh iterator value: alice

实际的旧桶数量、新桶数量以及触发扩容前插入了多少元素会因标准库实现而不同,因此示例只验证“桶数量发生变化”这一稳定事实。

怎样避免意外失效

如果能提前估算元素规模,可以在获取长期使用的迭代器之前调用 reserve(),减少后续插入触发 rehash 的机会。例如先执行 users.reserve(1000),再进行一批不超过预估规模的插入,比在循环中一边持有迭代器一边任由容器扩容更稳妥。

不过 reserve() 本身也可能立即 rehash,所以应把它放在创建需要保留的迭代器之前。不能确定后续是否会扩容时,最安全的做法是只保存键,在结构变化后重新 find()。

需要记住的失效边界

普通插入如果 没有 触发 rehash,已有迭代器仍可继续使用;一旦插入导致 rehash,全部迭代器都会失效。删除元素时,通常只有指向被删除元素的迭代器失效。无论哪种情况,都不要用已经失效的迭代器做比较、递增或解引用。

因此,判断迭代器能否继续使用时,不要只看调用的是 insert() 还是 emplace(),而要继续追问:这次操作有没有改变桶结构。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

rehash 为什么会影响迭代器

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通