迭代器失效规则不用背：从绑定关系一句话推完五种容器

团团虾声明：本文基于一份可编译运行的容器失效规则审计代码整理推演，所有断言均实测通过（g++ 5.4+/C++17）。

每个写过 C++ 的人都背过这张表。背完还是忘，忘完还是被咬——push_back 之后迭代器莫名其妙成了野指针，core dump 定位半小时，回头翻书，书上说”插入可能导致迭代器失效”。

“可能”两个字最要命。到底什么时候失效？失效的到底是迭代器还是引用？为什么 deque 两端插入引用还能活着？

大部分资料的做法是给一张更大的表，让你背得更全。这张表本身就是问题的根源：失效规则从来不是独立记忆点，它们全是同一个物理事实的推论。 从第一性原理往下推，五种容器一张纸就能写完。

迭代器的物理本质

先拆掉神秘感：对 vector 来说，迭代器大概率就是个裸指针，或者包了一层指针的类。它存的是内存地址，仅此而已。

那”失效”是什么？标准从没宣布过谁死亡——失效的物理含义只有一个：它指向的内存或结构，没了。

所以问题只剩一个：什么时候内存/结构会没了？往下拆一层，看迭代器到底绑定的是什么。

两种绑定，两种死法

迭代器和引用的绑定对象完全不同：

• 迭代器绑定在”组织结构”上——连续内存的布局、分段数组的控制块、桶数组的遍历顺序；
• 引用/指针绑定在”元素本体”上——那块存着值的内存。

推论一句话：

结构变了，迭代器死；本体搬了，引用才死。

就这一句。用它逐个推容器，你会发现自己根本不需要背。

vector：一块铁板

单块连续内存，所有元素挤在一起。

• 扩容（reallocate）：整块内存 free 掉换新的。本体搬家，迭代器引用一起死。
• 未扩容插入：本体没搬，插入点之前的照旧存活；插入点之后被挤着后移——本体位置变了，死。
• erase(pos)：pos 及之后整体前移，搬家，死；之前的没动，活。

deque：铁板拼图

分段数组 + 中央控制数组（map 数组）。组织结构比 vector 复杂得多，但有个精妙特例：

• 两端插入：头尾一般预留了空槽位，元素本体根本不搬家 → 引用活。但迭代器封装的是”在组织结构里的位置”，头尾一插，中央控制块可能重排、所有元素的相对位置逻辑全变 → 迭代器死。
• 中间插入：后半段元素本体要搬 → 全死。
• 两端删除：只有被删的那个元素本体销毁了 → 只死被删的。

这里有个关键语义：引用绑定的是元素本体，不是”头部/尾部”这个逻辑位置。back_ref 拿到的是老元素 3，push_back(4) 之后它依然是 3——它才懒得管新的 back() 是谁。

list / map：节点式容器

插入 = 新分配一个节点挂进去。老节点本体一个字节都没动，结构变化也不影响既有节点的绑定 → 什么都不失效。

erase = 只销毁那一个节点 → 只死被删的元素。

红黑树的 rebalance 只是改指针指向，节点内存原地不动。这就是为什么 map 的 insert 比 vector 温柔得多。

unordered_map：最反直觉的一个

rehash 重建的是桶数组（组织结构），节点本体原地不动。于是出现了最诡异的现象：迭代器全死，引用全活。

std::unordered_map<int, std::string> um;
um.emplace(7, "seven");
std::string& uref = um.at(7);
for (int i = 0; i < 500; ++i)
    if (i != 7) um.emplace(i, "v" + std::to_string(i));
// 触发 rehash 后：
// uref == "seven"  —— 引用活着
// begin() 之类的迭代器 —— 全部作废

要是只背过”扩容会失效”，在这里就会把 uref 也当成悬空引用不敢用了。

两张表

先给机理表——四种死法对应四种物理原因：

再给结果总表——就是那张背了又忘的表，现在每行都能从机理推出来：

其实这两张表是同一张表的两种投影：机理表是因，结果表是果。忘哪个都行，忘掉”两种绑定”才是真的麻烦。

审计代码

空口推演不算数。九个断言，全部落在标准担保”存活”的一侧（死亡一侧是 UB，碰都不能碰），实测 g++ -std=c++17 -Wall -Wextra 编译零警告、运行 PASS：

#include <cassert>
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    // ==================== 1. vector ====================
    {
        std::vector<int> v;
        v.reserve(16);
        for (int i = 0; i < 5; ++i) v.push_back(i * 10);

        int& ref2 = v[2];
        int* ptr2 = &v[2];
        int& ref0 = v[0];

        v.push_back(50);  // capacity 足够，无 reallocation

        // 无 reallocation ⇒ 既有元素的引用/指针良定义存活
        assert(ref2 == 20);
        assert(*ptr2 == 20);

        v.erase(v.begin() + 1);  // 位置 1 及之后全死

        // 删除点【之前】的引用存活——良定义
        assert(ref0 == 0);
        assert(v.size() == 5u);
    }

    // ==================== 2. deque ====================
    {
        std::deque<int> d = {1, 2, 3};
        int& front_ref = d.front();
        int& back_ref = d.back();

        d.push_back(4);
        d.push_front(0);

        // 双端插入：迭代器死，引用/指针存活。
        // back_ref 是老元素 3，不是新的 back()（4）。
        assert(front_ref == 1);
        assert(back_ref == 3);
        assert(d.back() == 4);
    }

    // ==================== 3. list ====================
    {
        std::list<std::string> lst = {"a", "target", "b", "c"};
        auto tit = std::next(lst.begin());  // 指向 "target"

        lst.push_front("head");
        lst.insert(lst.end(), "tail");
        lst.erase(std::next(lst.begin()));  // 删掉 "a"

        // 只杀被删节点，其余迭代器/引用全部存活
        assert(*tit == "target");
        assert(lst.size() == 5u);
    }

    // ==================== 4. map ====================
    {
        std::map<int, std::string> m = {{1, "one"}, {7, "seven"}, {9, "nine"}};
        auto mit = m.find(7);
        m.emplace(2, "two");
        m.emplace(5, "five");
        m.erase(1);  // 只杀 key=1
        assert(mit->first == 7);
        assert(mit->second == "seven");
    }

    // ==================== 5. unordered_map ====================
    {
        std::unordered_map<int, std::string> um;
        um.emplace(7, "seven");

        std::string& uref = um.at(7);
        std::size_t buckets_before = um.bucket_count();
        for (int i = 0; i < 500; ++i) {
            if (i != 7) um.emplace(i, "v" + std::to_string(i));
        }
        assert(um.bucket_count() != buckets_before && "rehash 必须真的发生");
        assert(uref == "seven" && "rehash 后引用存活（迭代器已死）");
    }

    std::cout << "PASS\n";
    return 0;
}

编译运行：

g++ -std=c++17 -Wall -Wextra invalidation_master.cpp -o ex06 && ./ex06
# PASS

两个坑

第一，别把实现细节当成标准担保。 比如上面 unordered_map 的例子：rehash 之后引用存活，这个结论是对的，但它依赖”rehash 只重排桶数组、不搬节点”这一实现惯例。标准原文的措辞是担保迭代器失效、引用保持有效，而不是担保”节点不搬家”。对着某一个具体实现的状态做断言，迟早翻车。

第二，警惕二手表格的转录漂移。 网上流传的失效表里，vector 的 insert 一栏常被写成”插入必失效”——少了”未扩容时插入点之前存活”这个分支，也从不区分迭代器和引用。抄表的人不知道原文的条件，每转一手丢一点，最后就成了一个既错误又难背的表。源头在 cppreference 各容器的 Invalidation 小节¹，要看就看一手。

收尾

说到底就一句话：迭代器绑定在组织结构上，引用绑定在元素本体上。结构变了迭代器死，本体搬了引用才死。

背表是吃别人嚼过的饭。从绑定关系推一遍，五种容器十分钟，比什么口诀都牢。