std::sort(lst.begin(), lst.end())编译不过，for (int x : v) { if (...) v.erase(...); }跑起来会崩 —— 这两个问题的根子是同一件事：迭代器不是一种东西，而是分等级的，而且会在容器改动时失效。这篇文章把「迭代器五分类」和「失效规则」两块拼成一张可查的表，以后遇到迭代器相关的报错直接对表。

1. 引子：sort 为什么拒绝 list

给一个std::list<int>排序，最直观的写法是照抄vector的套路：

// 反例，不要这么写：list 的迭代器不满足 sort 的要求，编译就过不去// std::list<int> lst{3, 1, 2};// std::sort(lst.begin(), lst.end());

线上编译器 gcc 13 会给出「没有匹配的 sort 重载」加一串模板推导失败的注解，一句话概括是：std::sort的模板参数被约束成「随机访问迭代器」，而std::list的迭代器是「双向迭代器」，差了一级。list 只能改成：

// 正确写法：list 自带一个成员函数 sort// std::list<int> lst{3, 1, 2};// lst.sort();

这不是标准库在挑刺，而是算法和容器之间的一份性能契约：std::sort内部是快速排序/内省排序，它需要「跳到第 n 个元素」「求两个迭代器的距离」「按下标二分」，这些操作只有随机访问迭代器才提供 O(1) 版本。list 的节点散落在堆上，it + n只能靠一步步走，真放进去会退化成 O(n) 的随机访问，sort 的复杂度保证当场作废 —— 所以标准干脆在类型层面拒绝它，让list::sort用更适合链表的自底向上归并排序来做。

官方文档：std::sort（明确写着要求 LegacyRandomAccessIterator）、std::list::sort（成员函数版本，稳定性有保证）

2. 五类迭代器：能力是层层递进的

标准库把迭代器按「能做什么」分成五类（iterator category）。类别之间是包含关系：高类别的迭代器自动满足低类别的一切要求。

输入迭代器 前向迭代器 双向迭代器 随机访问迭代器 input iterator forward bidirectional random access ────────────── ──────── ───────────── ────────────── 只能读一次 能多趟遍历 能后退 -- 能 +n / -n / it[n] 只能 ++ 只能 ++ ++ / -- 能比大小 < <= > >= 能 O(1) 求距离 典型来源 典型来源 典型来源 典型来源 istream_iterator forward_list list / map / set vector / deque / array （读文件、读 stdin） unordered_map （双向链表 / 红黑树） 原生指针 / string 能力包含关系（箭头向右，能力只增不减）： 输入 ──► 前向 ──► 双向 ──► 随机访问 输出 ──► 前向 ──► 双向 ──► 随机访问 ← 输出迭代器单独成一条线 记住一句话：**算法声明要求哪一类，就等于声明它能用哪些操作。** 给 std::sort（要求随机访问）传双向迭代器 = 缺了 +n 和 <，编译期就会被挡住。

把「能不能做」列成矩阵看得更清楚：

「输入迭代器只能读一次」这条最反直觉：std::cin消费的是字符流，读过去的字节回不来，所以保存一个istream_iterator然后想再走一遍是不成立的。

官方文档：迭代器库总览 — cppreference、std::iterator_traits

C++20 把这一整套重写成了概念（concept）：std::input_iterator、std::random_access_iterator等，还新增了一档std::contiguous_iterator（连续迭代器，表示底层元素内存连续，vector/array/string属于这一档）。分类思想没变，只是从「tag 继承」变成了「概念约束」，报错信息也因此友好得多。本文按 C++17 的 tag 体系讲，这是当前工作环境的口径。

3. 容器 ↔ 迭代器类别对照

这张表有个实用推论：「我想反向遍历」这件事在unordered_*上做不到。因为它是前向迭代器，没有rbegin()/rend()。要反序输出只能先收集到vector再std::reverse。

4. 算法的最低迭代器要求速查

标准库算法在文档里都会标注所需的迭代器类别，这张表决定了「这个算法能不能用在这个容器上」：

官方文档：算法库总览 — cppreference（每个算法页面都标了 LegacyIterator 要求）

5. advance / next / distance 与 const_iterator

std::advance/std::next/std::prev/std::distance是四个「按迭代器类别自动选实现」的工具，也是观察类别的窗口。

// iterator_utils.cpp — 编译: g++ -std=c++17 -Wall -O2 iterator_utils.cpp -o demo#include<cstddef>#include<cstdio>#include<iterator>#include<list>#include<vector>intmain(){conststd::vector<int>v{10,20,30,40,50};conststd::list<int>l{10,20,30,40,50};// distance：随机访问迭代器走「直接相减」O(1)，其余类别只能一步步 ++ 到 O(n)std::printf("vector 距离 = %td（O(1)：直接相减）\n",std::distance(v.begin(),v.end()));std::printf("list 距离 = %td（O(n)：逐个 ++）\n",std::distance(l.begin(),l.end()));// next / prev：返回一个新迭代器，不修改入参constautovit=std::next(v.begin(),2);constautolit=std::next(l.begin(),2);std::printf("next(vector::begin, 2) = %d\n",*vit);std::printf("next(list::begin, 2) = %d\n",*lit);std::printf("prev(next(v.begin, 2)) = %d\n",*std::prev(vit));// advance：就地移动，没有返回值autoait=l.begin();std::advance(ait,3);std::printf("advance(list::begin, 3) = %d\n",*ait);// cbegin / cend：强制得到 const_iterator，从类型上禁止误改元素constautocit=v.cbegin();std::printf("cbegin = %d\n",*cit);}

vector 距离 = 5（O(1)：直接相减） list 距离 = 5（O(n)：逐个 ++） next(vector::begin, 2) = 30 next(list::begin, 2) = 30 prev(next(v.begin, 2)) = 20 advance(list::begin, 3) = 40 cbegin = 10

两个实用结论：

• 别在循环里对非随机访问容器调std::distance。每次调用是 O(n)，套在循环里就变成 O(n²)。对list求长度用l.size()（C++11 起是 O(1)）。
• cbegin()/cend()是「只读」的编译期保证，begin()在const对象上才返回const_iterator。函数参数故意写成const auto&或者显式用cbegin()，能让「本意只读」这件事被编译器守住。

官方文档：std::distance、std::advance、std::next

6. 迭代器失效大表（全篇最该收藏的一节）

「迭代器失效（iterator invalidation）」指的是：容器做了某个操作后，之前拿到的迭代器不能再用了，继续解引用或自增就是未定义行为（undefined behavior，UB）。标准对每个容器的每种操作都有明确规定，汇总如下。

三个最容易记混的点，拎出来单独说：

1. vector的「部分失效」有条件。只有capacity够、不发生重新分配时，才是「插入点之后的失效」；一旦扩容，整块缓冲区搬家，所有迭代器、指针、引用全废。第 7 节会把这个搬家过程画出来。
2. deque是「迭代器比引用脆」的典型。push_front/push_back会让所有迭代器失效，但已经存在的元素不会搬家，所以指向元素的引用和指针仍然有效。这个区别在有外部缓存引用时很关键。
3. list/map/set是「节点式容器」，失效面最小。插入不搬任何已有节点，所以除end()外全部迭代器保持有效；删除也只影响被删的那个。想让「指向元素的指针/引用长期稳定」，就得选节点式容器。

另外，C++11 起insert和erase都有返回值，这一点是修正失效问题的基础：

• erase(it)返回被删元素之后的下一个有效迭代器。
• insert(...)返回指向新插入元素的迭代器。

官方文档：容器库 —— 迭代器失效规则汇总、std::vector 的失效说明、std::unordered_map 的失效说明

7. vector 扩容：迭代器失效的物理原因

前面反复提到「扩容导致全部失效」，跑一遍把这个过程看看清楚：

① v.reserve(2) 后 push_back 两个元素，capacity 用满 v 的控制块 {begin, end, cap_end} │ ▼ ┌─────┬─────┐ │ 1 │ 2 │ 堆上的缓冲区（capacity = 2） └─────┴─────┘ ▲ │ 某个迭代器 it 也指向这里 ② v.push_back(3) —— capacity 不够，必须「另开一块更大的 + 把元素搬过去 + 释放旧的」 新缓冲区（capacity = 4） ┌─────┬─────┬─────┬─────┐ │ 1 │ 2 │ 3 │ — │ └─────┴─────┴─────┴─────┘ ▲ │ v.begin() 现在指这里 ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ 1 │ 2 │ （旧缓冲区已释放） └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ▲ │ it 还指向这块已经失效的内存 → 悬垂迭代器（dangling iterator） 再用它解引用或 ++，就是 UB

// vector_realloc.cpp — 编译: g++ -std=c++17 -Wall -O2 vector_realloc.cpp -o demo#include<cstdio>#include<vector>intmain(){std::vector<int>v;v.reserve(2);// 预分配 2 个位置v.push_back(1);v.push_back(2);constint*buffer_before=v.data();// 记录缓冲区首地址，只用来比较「有没有搬家」std::printf("填满 capacity 后: size=%zu capacity=%zu\n",v.size(),v.capacity());v.push_back(3);// 超出 capacity → 重新分配 + 搬迁std::printf("再插一个之后 : size=%zu capacity=%zu\n",v.size(),v.capacity());std::printf("缓冲区搬家了吗: %s\n",v.data()==buffer_before?"没有（迭代器仍有效）":"搬了（旧迭代器全部失效）");}

填满 capacity 后: size=2 capacity=2 再插一个之后 : size=3 capacity=4 缓冲区搬家了吗: 搬了（旧迭代器全部失效）

所以「提前reserve(n)」不只是性能优化（少几次分配和拷贝），它还是避免迭代器失效的手段 —— 容量一次给够，后面就不会因为扩容而整块搬家。这也是为什么《vector 扩容策略与迭代器失效全解》里反复强调「知道元素数量就reserve」。

官方文档：std::vector::reserve、C++ Core Guidelines — SL.con.2 默认选 vector

8. 遍历中删除元素：两种必崩的写法

这是迭代器失效在真实代码里最高频的翻车现场。

// 反例 1，不要这么写：erase 后 it 已经失效，下一轮 ++it 是 UB// for (auto it = v.begin(); it != v.end(); ++it) {// if (*it % 2 == 0) {// v.erase(it); // it 失效；紧接着 for 的自增 ++it 踩在失效迭代器上// }// }// 反例 2，不要这么写：范围 for 的隐藏迭代器改不了，删元素必然踩空// for (int x : v) {// if (x % 2 == 0) {// v.erase(v.begin()); // 隐藏迭代器不知道这回事，下一次自增就是 UB// }// }

范围 for 会被展开成auto&& __range = v; auto __it = begin(__range); ... ++__it，其中__it是编译器的隐藏变量，你拿不到也改不了。既然没法把它更新成erase的返回值，范围 for 里就不能删元素 —— 这是硬结论，不是风格问题。

正确写法只有一个模式：手动写循环、把erase的返回值接回来。

// erase_pattern.cpp — 编译: g++ -std=c++17 -Wall -O2 erase_pattern.cpp -o demo#include<cstdio>#include<iterator>#include<list>#include<map>#include<vector>intmain(){// ① vector：erase 返回下一个有效迭代器，必须用它续上std::vector<int>v{1,2,3,4,5,6};for(autoit=v.begin();it!=v.end();){if(*it%2==0){it=v.erase(it);// 关键：用返回值续上，不要 ++it}else{++it;// 不删才前进}}std::printf("vector 删偶数后: ");for(intx:v){std::printf("%d ",x);}std::printf("\n");// ② map：同一个模式，而且 erase 只让被删元素失效，其他迭代器不受影响std::map<int,int>m{{1,10},{2,20},{3,30},{4,40}};for(autoit=m.begin();it!=m.end();){if(it->first%2==0){it=m.erase(it);}else{++it;}}std::printf("map 删偶数 key 后大小 = %zu\n",m.size());// ③ list：还是同一个模式（list 是双向迭代器，没有 +n，用 std::next 前进）std::list<int>lst{1,2,3,4,5,6};for(autoit=lst.begin();it!=lst.end();){if(*it%2==0){it=lst.erase(it);}else{it=std::next(it);}}std::printf("list 删偶数后大小 = %zu\n",lst.size());}

vector 删偶数后: 1 3 5 map 删偶数 key 后大小 = 2 list 删偶数后大小 = 3

模式只有三行，记住它的形状就行：

for (auto it = c.begin(); it != c.end(); ) ← 注意 for 的第三格是空的 { if (要删的条件) it = c.erase(it); ← 接住返回值，迭代器自己前进 else ++it; ← 不删才手动前进 } 口诀：**删了就接返回值，没删就手动 ++；绝不同时做两件事。**

C++20 还给了更省事的写法：std::erase_if(container, pred)，一行搞定，内部就是上面这个循环。

// verify: std=c++20// 需要 C++20：std::erase_if 统一了「按条件删除」的写法// std::erase_if(v, [](int x) { return x % 2 == 0; });// std::erase_if(m, [](const auto& kv) { return kv.first % 2 == 0; });

9. 完整示例：靠迭代器类别做编译期分派

最后把「类别」这件事用起来。标准库自己就是这么干的（std::distance内部按类别分派），我们也能用std::iterator_traits+if constexpr写一个「随机访问就 O(1) 求长度，否则老老实实数」的版本：

// category_dispatch.cpp — 编译: g++ -std=c++17 -Wall -O2 category_dispatch.cpp -o demo#include<cstddef>#include<cstdio>#include<forward_list>#include<iterator>#include<list>#include<map>#include<type_traits>#include<vector>namespace{// 按迭代器类别在编译期选实现：随机访问直接相减，其余类别逐个 ++template<typenameIt>std::size_tcountElems(It first,It last){usingCategory=typenamestd::iterator_traits<It>::iterator_category;ifconstexpr(std::is_base_of_v<std::random_access_iterator_tag,Category>){returnstatic_cast<std::size_t>(last-first);// O(1)}else{std::size_t n=0;for(;first!=last;++first){// O(n)++n;}returnn;}}}// namespaceintmain(){conststd::vector<int>v{1,2,3,4,5};conststd::list<int>l{1,2,3};conststd::forward_list<int>f{1,2,3,4};conststd::map<int,int>m{{1,10},{2,20}};std::printf("vector 个数 = %zu（随机访问，O(1) 相减）\n",countElems(v.begin(),v.end()));std::printf("list 个数 = %zu（双向，O(n) 逐走）\n",countElems(l.begin(),l.end()));std::printf("forward_list 个数 = %zu（前向，O(n) 逐走）\n",countElems(f.begin(),f.end()));std::printf("map 个数 = %zu（双向，O(n) 逐走）\n",countElems(m.begin(),m.end()));}

vector 个数 = 5（随机访问，O(1) 相减） list 个数 = 3（双向，O(n) 逐走） forward_list 个数 = 4（前向，O(n) 逐走） map 个数 = 2（双向，O(n) 逐走）

这段代码正好收束了全篇的主线：

• std::iterator_traits<It>::iterator_category是「问编译器这个迭代器属于哪一类」的标准入口。
• if constexpr（C++17）让分支在编译期就被丢弃——last - first这段代码对list根本不会被实例化，所以即使双向迭代器没有operator-，编译也不会报错。这是泛型代码里处理「能力差异」的标准手法。
• std::is_base_of_v之所以能用来判断类别，正因为五类迭代器的 tag 之间是继承关系（random_access_iterator_tag继承自bidirectional_iterator_tag，一路到input_iterator_tag），这也是第 2 节那张包含关系图的类型层面体现。

官方文档：std::iterator_traits、std::random_access_iterator_tag、if constexpr（C++17）

10. 延伸阅读

• 迭代器库 — cppreference：五类 tag、iterator_traits、工具函数的总入口，最该先读的一页
• 容器库 — cppreference：每个容器页面下方的「Iterator invalidation」小节是失效规则的唯一权威来源，本文那张大表就是从这儿逐条抄下来的
• 算法库 — cppreference：每个算法都标了最低迭代器要求，看一眼就知道能不能用在list上
• std::vector — cppreference：重点关注 capacity 与 reallocation 的说明，理解它才能理解失效
• C++ Core Guidelines — SL.con.2：默认用vector，需要稳定引用/迭代器时再换节点的选型思路

11. 一句话总结

迭代器的类别决定了「能对容器做什么」，容器的失效规则决定了「拿到手的迭代器还能活多久」——算法挑类别（sort要随机访问，list不满足）、代码避失效（vector扩容全废、节点容器最稳）、遍历中删除一律走「it = c.erase(it)或++it，二选一」这一个模式。三件事记牢，迭代器相关的 UB 基本就绝迹了。