std::sort(lst.begin(), lst.end())编译不过for (int x : v) { if (...) v.erase(...); }跑起来会崩 —— 这两个问题的根子是同一件事迭代器不是一种东西而是分等级的而且会在容器改动时失效。这篇文章把「迭代器五分类」和「失效规则」两块拼成一张可查的表以后遇到迭代器相关的报错直接对表。1. 引子sort 为什么拒绝 list给一个std::listint排序最直观的写法是照抄vector的套路// 反例不要这么写list 的迭代器不满足 sort 的要求编译就过不去// std::listint lst{3, 1, 2};// std::sort(lst.begin(), lst.end());线上编译器 gcc 13 会给出「没有匹配的 sort 重载」加一串模板推导失败的注解一句话概括是std::sort的模板参数被约束成「随机访问迭代器」而std::list的迭代器是「双向迭代器」差了一级。list 只能改成// 正确写法list 自带一个成员函数 sort// std::listint 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 和 编译期就会被挡住。把「能不能做」列成矩阵看得更清楚操作输入输出前向双向随机访问读取*it可以只能读一次不可以可以可以可以写入*it v不可以可以可以元素可写时可以可以it前进可以可以可以可以可以保存it后再走一遍多趟遍历不行不行可以可以可以--it后退不行不行不行可以可以it n/it - n不行不行不行不行可以it[n]随机下标不行不行不行不行可以it1 it2比位置前后不行不行不行不行可以it2 - it1求距离不行不行不行不行可以O(1)代表的操作istream_iteratorback_inserterforward_listlist/mapvector「输入迭代器只能读一次」这条最反直觉std::cin消费的是字符流读过去的字节回不来所以保存一个istream_iterator然后想再走一遍是不成立的。官方文档迭代器库总览 — cppreference、std::iterator_traitsC20 把这一整套重写成了概念conceptstd::input_iterator、std::random_access_iterator等还新增了一档std::contiguous_iterator连续迭代器表示底层元素内存连续vector/array/string属于这一档。分类思想没变只是从「tag 继承」变成了「概念约束」报错信息也因此友好得多。本文按 C17 的 tag 体系讲这是当前工作环境的口径。3. 容器 ↔ 迭代器类别对照容器 / 来源迭代器类别由此带来的限制std::vector/std::array/std::string随机访问能用sort但插入/扩容极易失效std::deque随机访问能用sort插入时几乎全部迭代器失效std::list双向不能用std::sort要用list::sort没有比较std::forward_list前向只能单向走删除要拿到「前一个位置」std::map/std::set/ 多重版本双向不能用std::sort但本身就按 key 有序std::unordered_map/std::unordered_set前向反向遍历和--it都没有rehash 后全失效std::istream_iterator/std::istreambuf_iterator输入单趟读完就没了std::ostream_iterator/std::back_insert_iterator输出只能写不能读也不能比位置原生指针T*随机访问C20 起为连续迭代器数组不够长就是越界 UB这张表有个实用推论「我想反向遍历」这件事在unordered_*上做不到。因为它是前向迭代器没有rbegin()/rend()。要反序输出只能先收集到vector再std::reverse。4. 算法的最低迭代器要求速查标准库算法在文档里都会标注所需的迭代器类别这张表决定了「这个算法能不能用在这个容器上」算法最低要求因此不能用在这些容器上std::find/std::count/std::for_each输入都能用std::copy/std::transform输入 → 输出都能用std::remove_if/std::unique前向都能用std::rotate/std::inplace_merge前向 / 双向forward_list之外基本都能用std::reverse/std::next_permutation双向不能用forward_list和unordered_*std::lower_bound/std::equal_range前向C11 起放宽都能用但无序容器上语义无意义std::sort/std::stable_sort随机访问不能用list/map/set/unordered_*std::partial_sort/std::nth_element随机访问同上std::make_heap/std::push_heap随机访问同上list::sort/forward_list::sort容器内建只在这两个容器上可用官方文档算法库总览 — cppreference每个算法页面都标了 LegacyIterator 要求5. advance / next / distance 与 const_iteratorstd::advance/std::next/std::prev/std::distance是四个「按迭代器类别自动选实现」的工具也是观察类别的窗口。// iterator_utils.cpp — 编译: g -stdc17 -Wall -O2 iterator_utils.cpp -o demo#includecstddef#includecstdio#includeiterator#includelist#includevectorintmain(){conststd::vectorintv{10,20,30,40,50};conststd::listintl{10,20,30,40,50};// distance随机访问迭代器走「直接相减」O(1)其余类别只能一步步 到 O(n)std::printf(vector 距离 %tdO(1)直接相减\n,std::distance(v.begin(),v.end()));std::printf(list 距离 %tdO(n)逐个 \n,std::distance(l.begin(),l.end()));// next / prev返回一个新迭代器不修改入参constautovitstd::next(v.begin(),2);constautolitstd::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就地移动没有返回值autoaitl.begin();std::advance(ait,3);std::printf(advance(list::begin, 3) %d\n,*ait);// cbegin / cend强制得到 const_iterator从类型上禁止误改元素constautocitv.cbegin();std::printf(cbegin %d\n,*cit);}vector 距离 5O(1)直接相减 list 距离 5O(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()C11 起是 O(1)。cbegin()/cend()是「只读」的编译期保证begin()在const对象上才返回const_iterator。函数参数故意写成const auto或者显式用cbegin()能让「本意只读」这件事被编译器守住。官方文档std::distance、std::advance、std::next6. 迭代器失效大表全篇最该收藏的一节「迭代器失效iterator invalidation」指的是容器做了某个操作后之前拿到的迭代器不能再用了继续解引用或自增就是未定义行为undefined behaviorUB。标准对每个容器的每种操作都有明确规定汇总如下。容器insert/emplaceerase(it)push_back/pop_back重分配 / rehashclear()vector未超capacity→ 插入点之后的失效超了 →全部失效被删元素及其之后的全部失效push_back同上可能扩容pop_back只让被删元素失效reserve/ 扩容 →全部失效全部失效deque全部迭代器失效但指向元素的引用/指针仍有效全部失效元素本身还在的仍可引用push_front/push_back→全部失效pop_*只让被删元素失效不适用全部失效list只有end()失效只有被删元素失效只有end()失效不适用全部失效forward_list只有end()/before_begin()失效只有被删元素失效push_front不影响其他迭代器不适用全部失效map/set/ 多重版本全部保持有效只有被删元素失效不适用不适用全部失效unordered_map/unordered_set未 rehash → 保持有效rehash → 全部失效只有被删元素失效不适用rehash → 迭代器全失效但指向元素的指针/引用仍有效全部失效string同vectorSSO 短字符串时引用也可能失效同vector同vector同vector全部失效array不适用定长不适用不适用不适用不适用三个最容易记混的点拎出来单独说vector的「部分失效」有条件。只有capacity够、不发生重新分配时才是「插入点之后的失效」一旦扩容整块缓冲区搬家所有迭代器、指针、引用全废。第 7 节会把这个搬家过程画出来。deque是「迭代器比引用脆」的典型。push_front/push_back会让所有迭代器失效但已经存在的元素不会搬家所以指向元素的引用和指针仍然有效。这个区别在有外部缓存引用时很关键。list/map/set是「节点式容器」失效面最小。插入不搬任何已有节点所以除end()外全部迭代器保持有效删除也只影响被删的那个。想让「指向元素的指针/引用长期稳定」就得选节点式容器。另外C11 起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 -stdc17 -Wall -O2 vector_realloc.cpp -o demo#includecstdio#includevectorintmain(){std::vectorintv;v.reserve(2);// 预分配 2 个位置v.push_back(1);v.push_back(2);constint*buffer_beforev.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 后: size2 capacity2 再插一个之后 : size3 capacity4 缓冲区搬家了吗: 搬了旧迭代器全部失效所以「提前reserve(n)」不只是性能优化少几次分配和拷贝它还是避免迭代器失效的手段 —— 容量一次给够后面就不会因为扩容而整块搬家。这也是为什么《vector 扩容策略与迭代器失效全解》里反复强调「知道元素数量就reserve」。官方文档std::vector::reserve、C Core Guidelines — SL.con.2 默认选 vector8. 遍历中删除元素两种必崩的写法这是迭代器失效在真实代码里最高频的翻车现场。// 反例 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 -stdc17 -Wall -O2 erase_pattern.cpp -o demo#includecstdio#includeiterator#includelist#includemap#includevectorintmain(){// ① vectorerase 返回下一个有效迭代器必须用它续上std::vectorintv{1,2,3,4,5,6};for(autoitv.begin();it!v.end();){if(*it%20){itv.erase(it);// 关键用返回值续上不要 it}else{it;// 不删才前进}}std::printf(vector 删偶数后: );for(intx:v){std::printf(%d ,x);}std::printf(\n);// ② map同一个模式而且 erase 只让被删元素失效其他迭代器不受影响std::mapint,intm{{1,10},{2,20},{3,30},{4,40}};for(autoitm.begin();it!m.end();){if(it-first%20){itm.erase(it);}else{it;}}std::printf(map 删偶数 key 后大小 %zu\n,m.size());// ③ list还是同一个模式list 是双向迭代器没有 n用 std::next 前进std::listintlst{1,2,3,4,5,6};for(autoitlst.begin();it!lst.end();){if(*it%20){itlst.erase(it);}else{itstd::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; ← 不删才手动前进 } 口诀**删了就接返回值没删就手动 绝不同时做两件事。**C20 还给了更省事的写法std::erase_if(container, pred)一行搞定内部就是上面这个循环。// verify: stdc20// 需要 C20std::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_traitsif constexpr写一个「随机访问就 O(1) 求长度否则老老实实数」的版本// category_dispatch.cpp — 编译: g -stdc17 -Wall -O2 category_dispatch.cpp -o demo#includecstddef#includecstdio#includeforward_list#includeiterator#includelist#includemap#includetype_traits#includevectornamespace{// 按迭代器类别在编译期选实现随机访问直接相减其余类别逐个 templatetypenameItstd::size_tcountElems(It first,It last){usingCategorytypenamestd::iterator_traitsIt::iterator_category;ifconstexpr(std::is_base_of_vstd::random_access_iterator_tag,Category){returnstatic_caststd::size_t(last-first);// O(1)}else{std::size_t n0;for(;first!last;first){// O(n)n;}returnn;}}}// namespaceintmain(){conststd::vectorintv{1,2,3,4,5};conststd::listintl{1,2,3};conststd::forward_listintf{1,2,3,4};conststd::mapint,intm{{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_traitsIt::iterator_category是「问编译器这个迭代器属于哪一类」的标准入口。if constexprC17让分支在编译期就被丢弃——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 constexprC1710. 延伸阅读迭代器库 — 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 基本就绝迹了。