迭代器失效（Iterator Invalidation）大全

这是 STL 面试必考核心之一。核心记忆点：每种容器、哪些操作、会使哪些迭代器失效。

一、前置概念

• 迭代器是对象，指向容器（或其元素）；失效指指向的内存位置可能已变/已释放/位置语义改变，解引用或 ++ 是未定义行为。
• 分为「全失效」（所有迭代器都不再有效，如 vector 扩容）与「局部失效」（只有被删元素 / 特定位置失效）。

二、各容器失效规则速查表

vector / string（连续存储）

操作	哪些迭代器/引用失败
扩容（push_back 触发 reserve/realloc）	所有迭代器、引用、指针失效
插入中间（insert）	插入点及之后全部失效（因后移 + 可能扩容）
erase 中间	erase 位置及之后全部失效
pop_back（尾部删除）	仅指向被删元素的迭代器；end() 变化
reserve 若容量增加	全部失效
resize 扩大	全部失效；缩小则失效被删部分之后的
clear	全部失效
swap / shrink_to_fit 改变 capacity	swap 后各自指向对方的元素；shrink 若缩容则全失效

关键：连续容器任何「重分配或元素搬移」（扩容、中间增删）都会使受影响范围迭代器失效——因为它们内部是指针，重分配后地址变了。

string 的额外注意

在 C++11 之前标准较宽松；C++11 起 string 也保证 operator[]/data() 连续，扩容失效规则同 vector。

deque

操作	失效范围
中间插入/删除	全部迭代器失效
头/尾插入（push_front/back）	迭代器可能失效（中控器 map 扩容时）；引用不失效
头/尾删除（pop_front/back）	仅被删元素的迭代器失效

list / forward_list（链表）

操作	失效范围
任何位置 insert	不使任何其它迭代器失效
erase	仅被删除元素的迭代器/引用失效
splice	移动出去的节点的迭代器保留（仍指向该节点，只是容器变了）

map / set / multimap / multiset（红黑树）

操作	失效范围
insert	不影响任何已有迭代器
erase	仅被删除的迭代器失效
rehash（unordered_* 系列才涉及）	见下

注意：标准关联容器（有序版）insert/erase 都不影响其它迭代器，这是它们相比连续容器的优势。

unordered_map / unordered_set（哈希表）

操作	失效范围
insert（可能 rehash）	触发 rehash 则全部失效；未触发则不影响
erase	仅被删元素迭代器失效；不影响其它 bucket 的引用
rehash / reserve	全部失效

三、经典安全删除/遍历模式

场景 1：遍历中删除元素

// vector / deque —— erase 返回下一个迭代器
for (auto it = v.begin(); it != v.end(); ) {
    if (条件) it = v.erase(it);  // erase 返回被删元素后一位置 ✅
    else ++it;
}

// map / set —— erase(iterator) 返回 void(C++11前)/下一个(C++11起返回下一个)
for (auto it = m.begin(); it != m.end(); ) {
    if (条件) it = m.erase(it);   // C++11 起返回下一个 ✅
    else ++it;
}
// 或 C++03 兼容写法（先保存下一个再删）
for (auto it = m.begin(); it != m.end(); ) {
    if (条件) { m.erase(it++); }  // 先递增再删，it 指向的节点删除不影响已保存的下一个
    else ++it;
}

场景 2：遍历中插入

• vector/list 中间插入后记得更新迭代器（insert 返回插入位置迭代器）。
• list/map 插入不影响其它迭代器，安全。

场景 3：内部持有容器迭代器/引用的坑

std::vector<int> v(10);
int& r = v[3];          // 引用绑定元素地址
v.push_back(100);       // 可能触发扩容 → r 悬空 💥

规避：需要长期保存元素的地址/引用时，优先 list、map（节点稳定），或在操作前 reserve 预留足够容量。

四、为什么 vector 扩容会导致引用/指针也失效而 list/map 不会？

因为 vector 扩容是整个把数据搬去新地址，老地址释放，任何指向老地址的迭代器、引用、裸指针全部悬空；而 list/map 的元素对象创建后地址固定（只改节点的前后指针），引用/指针始终有效——这是容器「节点稳定性（node stability）」的区别，面试高频追问点。

五、记忆口诀

• 连续容器（vector/string/deque 中间）：搬元素 ⇒ 局部甚至全部失效。
• 链表/树（list/map/set）：只改指针 ⇒ 只删谁谁失效。
• 哈希表（unordered_*）：平时稳定，一 rehash 全玩完（所以先 reserve 预分配）。
• 删除遍历：用 erase 返回的下一个迭代器，别用已失效的旧迭代器。