⚡C++ STL 与迭代器

迭代器分类与失效规则

面试回答

常见问法

迭代器有哪些分类？它们的能力有什么区别？
为什么不同容器的迭代器失效规则不一样？
vector、deque、list、map、unordered_map 的失效规则怎么记？
为什么有些算法能用于 vector，却不能直接用于 list？
遍历时删除元素，为什么推荐接住 erase 的返回值？

回答

迭代器本质上是“泛化指针”，它把算法和容器解耦。迭代器分类描述的是：这个迭代器能做什么操作；迭代器失效规则描述的是：容器修改后，之前拿到的位置还能不能继续用。

从能力上看，迭代器通常从弱到强可以分为：

输入迭代器：可读，单遍扫描
输出迭代器：可写，单遍写入
前向迭代器：可多遍扫描，只能前进
双向迭代器：可前进、后退
随机访问迭代器：支持 it + n、it[n]、比较距离，典型是 vector
连续迭代器：在随机访问基础上还保证物理连续，典型是 vector、array、string

面试里更重要的是第二部分：迭代器为什么失效。根本原因通常就两类：

底层存储搬家了 比如 vector 扩容，会重新分配更大的连续内存，原来的迭代器、引用、指针都指向旧地址，全部失效。
节点本身被删了或结构重建了 比如 list::erase(it)，被删节点的迭代器失效，但其他节点位置没变，通常还能继续用。再比如 unordered_map 的 rehash，桶数组重建，迭代器普遍失效。

所以判断失效规则，核心不是死记，而是看容器底层实现：

连续存储容器：一旦扩容或移动元素，容易大面积失效
节点式容器：插入通常稳定，删除通常只影响被删节点
哈希容器：rehash 是高风险点

例如：

std::vector<int> v{1, 2, 3};
auto it = v.begin();

v.push_back(4); // 若触发扩容，it 失效
// 再使用 *it、++it，都是未定义行为

遍历删除时，最稳妥的写法是接住 erase 返回值，因为它通常会返回“删除位置之后的下一个有效迭代器”：

for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it);
    } else {
        ++it;
    }
}

再往下追问时，我会把它和算法要求联系起来： 算法并不依赖具体容器，而是依赖迭代器能力。 比如 std::sort 要求随机访问迭代器，所以不能直接对 list 用；list 应该用自己的成员函数 list::sort()。

追问

为什么 list 插入元素通常不让其他迭代器失效？
vector::push_back 为什么有时失效、有时不失效？
erase 返回值为什么重要？
end() 会不会失效？
为什么 unordered_map 插入也可能让迭代器失效？
std::sort 为什么不能用于 list？
引用、指针、迭代器失效是同一回事吗？

原理展开

1. 迭代器分类：不只是“能遍历”，而是“能力等级”

迭代器分类回答的是：算法最少需要你提供什么能力。

输入迭代器（Input Iterator）

只保证读取
单遍扫描
适合流式读取、一次性消费的数据源

std::istream_iterator<int> in(std::cin);

输出迭代器（Output Iterator）

只保证写入
单遍写入
适合算法输出目标位置

std::vector<int> v;
std::back_insert_iterator<std::vector<int>> out(v);

前向迭代器（Forward Iterator）

可读可写
支持多遍扫描
只能向前移动

典型：forward_list

双向迭代器（Bidirectional Iterator）

在前向基础上支持 --it
典型：list、set、map

随机访问迭代器（Random Access Iterator）

支持跳跃访问：it + n、it - n、it[n]
支持常数时间距离计算
典型：vector、deque、array

连续迭代器（Contiguous Iterator，C++20 概念）

在随机访问基础上，还保证元素在内存中连续
可以安全地把迭代器视作接近裸指针的连续区间
典型：vector、array、basic_string

面试里常见说法还是前五类；如果提到 C++20，可以补一句： “现代标准里还强调 contiguous_iterator，它比随机访问更强，表示物理内存连续。”

2. 为什么算法能脱离容器工作

STL 的核心思想是：容器提供数据结构，迭代器提供访问方式，算法只依赖访问能力。

所以你要会两层判断：

第一层：这个算法至少需要什么迭代器？

std::find：输入迭代器即可
std::reverse：双向迭代器
std::sort：随机访问迭代器
std::lower_bound：前向迭代器即可，但随机访问更高效

第二层：这个容器提供的迭代器够不够？

vector：随机访问，绝大多数泛型算法都能直接用
list：双向，不满足 std::sort 要求，所以不能直接排
forward_list：前向，能力更弱

例如：

std::list<int> lst{3, 1, 2};
// std::sort(lst.begin(), lst.end()); // 错，list 不是随机访问迭代器
lst.sort();                           // 对，应使用成员函数

这类回答比只背“list 不能 sort”更像真正理解 STL。

3. 迭代器失效的本质：地址变了，或者节点没了

失效规则不是零散知识点，底层上看就三种情况：

3.1 连续存储重分配

典型是 vector / string。

如果插入导致容量不足，就会重新申请一块更大的连续内存，把原元素搬过去。那么旧地址全部废掉，所以：

旧迭代器失效
旧引用失效
旧指针失效

std::vector<int> v;
v.reserve(2);
v.push_back(1);
v.push_back(2);

auto it = v.begin();
v.push_back(3); // 触发扩容，it 失效

工程实践里，如果你预估数据量，先 reserve() 能明显减少扩容导致的失效和拷贝成本。

3.2 元素移动但未重分配

即使没扩容，也不代表一定安全。例如 vector 中间插入、删除，会导致后续元素整体挪动，所以插入点及其后的迭代器、引用、指针可能失效。

std::vector<int> v{1, 2, 3, 4};
auto it = v.begin() + 2; // 指向 3

v.erase(v.begin());      // 后面元素前移
// it 失效，不能再用

所以 vector 的风险不只是扩容，还有中间位置改动带来的批量搬移。

3.3 节点删除或结构重建

典型是 list、map、set、unordered_map。

节点式容器

像 list、map、set 这类通常每个元素是独立节点：

插入一个节点，不需要移动已有节点
删除一个节点，只影响这个节点本身

所以：

插入通常不影响其他迭代器
删除通常只让被删节点的迭代器失效

哈希容器

unordered_map / unordered_set 还有一个额外风险：rehash

当元素过多、负载因子过高时，桶数组可能重建。一旦 rehash，原有迭代器一般会失效。

std::unordered_map<int, int> mp;
auto it = mp.begin();
mp.reserve(1000); // 可能触发 rehash，旧迭代器失效

4. 常见容器的失效规则，面试最容易考这一段

`vector`

push_back / emplace_back
- 触发扩容：全部迭代器、引用、指针失效
- 未触发扩容：通常已有元素仍有效，但 end() 失效
中间 insert / erase
- 插入点或删除点之后的元素发生移动
- 该位置及其后的迭代器、引用、指针通常失效

`deque`

支持随机访问，但底层不是单块连续内存，而是分段连续
头尾插删不等于 vector 头尾插删，规则更复杂
迭代器失效规则比 vector 更难记，面试中不建议硬背细枝末节，抓住两点：
1. deque 不是单块连续内存
2. 头尾操作相对高效，但迭代器稳定性不如 list

`list` / `forward_list`

插入通常不影响已有迭代器
删除只影响被删节点
适合“边遍历边删除”
但随机访问差，缓存局部性差，工程中并不一定比 vector 快

`set` / `map` / `multiset` / `multimap`

基于平衡树的节点式容器
插入通常不影响已有迭代器
删除只影响被删节点
但元素是有序的，迭代顺序稳定为有序遍历

`unordered_set` / `unordered_map`

不 rehash 时，插入通常不影响已有元素引用
一旦 rehash，迭代器普遍失效
删除只影响被删元素

安全说法： “哈希容器的主要失效风险在 rehash，所以如果想减少这种风险，可以提前 reserve()。”

5. 为什么 `erase` 常返回下一个有效迭代器

因为当前迭代器指向的元素已经被删除了，原位置不能再安全使用。容器返回“后继位置”，就是为了让你继续遍历，不必自己重新找。

这是 STL 风格中非常经典的接口设计。

for (auto it = lst.begin(); it != lst.end(); ) {
    if (*it < 0) {
        it = lst.erase(it);
    } else {
        ++it;
    }
}

这也是面试里很加分的一点： 你不仅知道会失效，还知道怎么写出安全代码。

6. 工程实践里怎么选容器，不能只看“迭代器稳不稳”

很多人一看到“list 插入删除稳定”，就以为工程上应该优先用 list，这是误区。

实际选择通常按下面判断：

优先选 `vector` 的场景

读多写少
需要随机访问
追求缓存友好和整体性能
与泛型算法配合频繁

考虑 `list` 的场景

已经拿到了大量稳定迭代器，需要频繁按位置删除
中间插删极多，且不依赖随机访问
需要 splice 这类链表特有能力

考虑 `unordered_map` 的场景

关注平均 O(1) 查找
不需要有序遍历
能接受 rehash 带来的迭代器风险

考虑 `map` / `set` 的场景

需要有序
需要区间查询、上下界查找
希望迭代器更稳定

工程上的默认原则通常是： 先用 vector，除非你有明确理由不用它。 因为它通常拥有最好的局部性、最成熟的算法支持和最可预测的性能。

对比总结

1. 迭代器类别对比

类别	能力	是否多遍扫描	典型操作	典型容器/场景	优点	局限
输入迭代器	只读	否	`*it`, `++it`	输入流、一次性读取	抽象最弱，适配流式数据	单遍，不能回头
输出迭代器	只写	否	`*it = x`, `++it`	`back_inserter`	适合算法输出	不能读，单遍
前向迭代器	可读可写，只能前进	是	`*it`, `++it`	`forward_list`	能多遍扫描	不支持后退和跳跃
双向迭代器	可前进后退	是	`--it`	`list`、`map`、`set`	适合双向遍历	不支持随机跳跃
随机访问迭代器	常数时间跳跃	是	`it+n`, `it[n]`, `it-it2`	`vector`、`deque`、`array`	算法适配最广	不代表物理连续
连续迭代器	随机访问 + 内存连续	是	可接近裸指针语义	`vector`、`array`、`string`	局部性好，适合底层优化	只有少数容器满足

2. 常见容器的迭代器失效规则对比

容器	底层结构	插入时失效	删除时失效	典型适用场景	主要优点	主要风险
`vector`	连续内存	扩容时全部失效；中间插入会让插入点后的迭代器/引用/指针失效	删除点及其后通常失效	随机访问、读多写少	局部性好、性能高	扩容和元素搬移
`deque`	分段连续	规则较复杂，头尾操作不等于 `vector`	规则较复杂	头尾插删 + 随机访问	两端插删高效	失效规则难记，不连续
`list`	双向链表	通常不影响其他迭代器	仅被删节点失效	频繁中间插删	迭代器稳定	局部性差，随机访问差
`forward_list`	单向链表	通常不影响其他迭代器	仅被删节点失效	简单单向链表场景	开销更小	只能单向遍历
`map/set`	平衡树	通常不影响其他迭代器	仅被删节点失效	有序存储、范围查询	有序且稳定	随机访问不存在
`unordered_map/set`	哈希表	`rehash` 时迭代器普遍失效	仅被删元素失效	快速查找	平均 O(1)	`rehash` 风险、无序

3. 相近概念对比：迭代器失效 vs 引用失效 vs 指针失效

概念	本质	常见失效原因	是否总是一起失效
迭代器失效	“位置对象”不再合法	容器重分配、节点删除、结构调整	不一定
引用失效	绑定对象不存在或位置变化	元素被删、重分配、元素搬移	不一定
指针失效	指向地址不再有效	内存释放、对象迁移	不一定

面试里不要说成一回事。最稳妥的表达是： “要区分容器文档对 iterator / reference / pointer 分别怎么保证。”

4. 相近容器怎么选

场景	更推荐	原因	不优先选谁
默认动态数组场景	`vector`	性能稳定、算法支持最好	`list`
需要频繁中间插删且持有稳定位置	`list`	节点稳定	`vector`
需要有序查找、上下界	`map/set`	有序树结构	`unordered_map/set`
需要尽量快的查找	`unordered_map/set`	平均 O(1)	`map/set`
需要头尾插删 + 随机访问	`deque`	双端高效	`vector` / `list`

易错点

把“修改容器”简单等同于“一定全部失效”。这太粗糙，面试官通常会继续追问具体到哪一段失效。
把迭代器失效、引用失效、指针失效混为一谈。
只记住 vector 扩容会失效，却忘了中间插入/删除也会导致后续元素位置变化。

遍历删除时写成：

for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        v.erase(it); // 错：it 可能已经失效，循环还会 ++it
    }
}

以为 list 迭代器稳定，就认为 list 一定比 vector 更适合工程实践。很多情况下恰恰相反。
不知道算法有迭代器能力要求，只会死记某个容器能不能用某算法。
认为 unordered_map 插入永远安全，忽略了 rehash。
忽略 end() 也可能失效，尤其是 vector 扩容后。

记忆技巧

先看结构，再猜规则：连续存储看“会不会搬家”，节点容器看“是不是摘节点”，哈希容器看“会不会 rehash”。
一句话记 vector：扩容全失效，不扩容看位置；中间改动，后半段高危。
一句话记节点式容器：插入通常稳定，删除通常只伤自己。
一句话记哈希容器：平时像节点，rehash 像地震。
算法选型口诀： find 要得少，reverse 要后退，sort 要随机访问。
工程选型口诀：默认先想 vector，有序想树，快查想哈希，稳定删改再想链表。

面试速答版

迭代器是容器和算法之间的桥梁，分类本质上表示“能做哪些操作”。常见从弱到强是输入、输出、前向、双向、随机访问，C++20 还强调连续迭代器。比如 std::sort 要求随机访问迭代器，所以不能直接用于 list。

迭代器失效的根本原因主要有两类：一类是底层存储搬家，比如 vector 扩容会让原有迭代器、引用、指针全部失效；另一类是节点被删除或结构重建，比如 list::erase 只让被删节点失效，unordered_map 在 rehash 时迭代器会普遍失效。判断规则时不要死记，要看容器底层是连续存储、节点式，还是哈希结构。遍历删除时最稳妥的写法是接住 erase 返回的下一个有效迭代器。

面试加分版

我一般把这个问题分两部分回答：迭代器分类和失效规则。

先说分类。迭代器本质上是泛化指针，分类表示的是访问能力。输入/输出迭代器是单遍的，前向迭代器可以多遍扫描，双向迭代器支持前后移动，随机访问迭代器支持跳跃访问，像 it + n、it[n]，而 C++20 进一步强调连续迭代器，除了随机访问，还要求物理内存连续。这个分类很重要，因为 STL 算法依赖的是迭代器能力，不依赖具体容器类型，所以像 std::sort 需要随机访问迭代器，list 只能用自己的 list::sort()。

再说失效规则。根本上看就三种情况。第一，连续内存重分配，比如 vector 扩容，旧地址全部失效，所以迭代器、引用、指针都会失效。第二，元素搬移，即使 vector 不扩容，中间插入或删除也会让后续元素整体移动，所以该位置及其后的迭代器通常失效。第三，节点删除或结构重建，比如 list、map、set 这类节点式容器，插入通常不影响其他迭代器，删除通常只影响被删节点；而 unordered_map 的关键风险点是 rehash，一旦重建桶数组，迭代器普遍失效。

如果面试官继续追问工程实践，我会补一句：不要因为 list 迭代器稳定就优先选它，工程上通常还是优先 vector，因为它缓存友好、随机访问强、算法支持最好。只有在你确实需要大量稳定迭代器、频繁中间插删，或者需要链表特有操作时，才考虑 list。另外，写安全代码时，遍历删除一定要接住 erase 返回值；如果用 vector 或 unordered_map，可以通过 reserve() 减少扩容和 rehash 带来的失效风险。