一直用到迭代器但没细想过它的人，看完这篇应该能把“为什么这么设计”想明白。C++ STL 系列写到第四篇，前面聊容器和算法的时候我多次提到迭代器，但都是一句话带过。这次把它单独拿出来讲透，是因为迭代器在 STL 里承担的角色太特殊了：它是容器和算法之间的粘合剂，也是整个标准库能保持优雅的唯一理由。
先说个所有 C++ 开发都经历过的小场景。假设你要写一个“在容器里找第一个负数”的函数，手头有std::vector<int>、std::list<int>、std::map<int, int>三种结构。最朴素的做法是给每种容器各写一份遍历逻辑——vector 用下标、list 用节点指针、map 要同时取 key 和 value。写三遍倒也能跑，但这三份代码的逻辑除了“访问方式不同”之外，其余完全一样。迭代器就是把“容器怎么存”和“算法怎么读”彻底分开的协议层。一个std::find_if能同时处理数组、链表、哈希表、输入流，靠的就是迭代器提供了一套统一访问语义。
这篇文章适合正在学 STL 但总感觉“容器和算法接不上”的人，也适合那些已经写过不少业务代码、却从没深究过迭代器失效和自定义迭代器的进阶开发者。我会从设计动机讲起，一路聊到 traits 机制、失效规则、手写迭代器、反向迭代器，每一部分都带着实际能跑的代码和踩坑记录。
1. 迭代器到底在解决什么问题：从一段“多容器适配”的代码说起
1.1 先看一段让你头疼的“三份代码”
很多初学者第一次意识到迭代器的价值，往往是被逼出来的。我模拟一个非常常见的需求：遍历一个容器，把满足条件的元素找出来。不用迭代器，不考虑模板，直接面向具体容器写，你会得到下面这种结果。
// 面向 vector：下标访问 int find_negative_vector(const std::vector<int>& v) { for (std::size_t i = 0; i < v.size(); ++i) { if (v[i] < 0) return v[i]; } return 0; } // 面向 list：节点遍历 int find_negative_list(const std::list<int>& lst) { for (auto p = lst.begin(); p != lst.end(); ++p) { if (*p < 0) return *p; } return 0; } // 面向 map：只能走 iterator int find_negative_map(const std::map<std::string, int>& m) { for (auto it = m.begin(); it != m.end(); ++it) { if (it->second < 0) return it->second; } return 0; }这三份代码的骨架完全一样：初始化一个“标记”、判断是否到末尾、移动“标记”、读取当前元素。区别只在于 vector 用下标[i]，list 和 map 用某种“类似指针的东西”。如果你试着把这些逻辑合成一个模板，问题就来了——vector 想走下标路线，list 没有随机访问能力，map 的*it是个 pair，你没法用统一的方式写。这正是迭代器存在的理由：它把“它是一个元素”这件事抽象出来，抹掉容器的物理布局差异。
1.2 迭代器把“怎么走”和“看什么”分离
迭代器的核心思想其实非常朴素：一切容器都把自己内部的“位置”包装成一个统一的对象，这个对象支持若干固定的操作——*取当前元素的值，++移动到下一个位置，==判断是否和另一个位置相同。容器只需要告诉外界“从哪开始（begin）”“到哪结束（end）”，以及“端点怎么移动”。
拿最常见的std::vector举例，它的迭代器本质就是一个原生指针的薄封装，v.begin()返回的迭代器内部存着数组首元素地址，++it就是指针自增。而std::list的迭代器内部则是一个双向链表的节点指针，++it实际走的是next指针。从外部用起来却是同一个符号++，同一个解引用*，这就是抽象的力量——你不需要关心它内部到底是数组还是链表，也不需要关心元素在内存里是不是连续的。
这个抽象把“怎么走”和“看什么”分离了：容器负责实现“怎么走”，算法只负责“看什么”。于是std::count_if、std::find、std::accumulate这些算法完全不依赖具体容器类型，它们只需要三个迭代器参数：一个起点、一个终点、或者加上一个初始值。这也是为什么你总是能在两个完全不同的容器上调用同一个算法。
1.3 为什么不能直接传原生指针
有人会说：“vector 的迭代器不就是指针吗？那直接用指针不就行了？”这个想法对一半错一半。凡是以连续内存为底的容器（vector、array、string），原生指针确实能胜任；但 list、map、set、unordered_map 都做不到。它们的元素散布在节点的字段里，谁也没法保证内存连续，裸指针++毫无意义。
而且就算某个容器恰好能用原生指针，算法内部如果依赖“指针一定能p + n跳 n 步”，遇到 list 就直接编不过。所以迭代器必须是一个独立类型，由容器自己定义，内部可以是指针，也可以不是。标准库算法只信任迭代器暴露出来的操作集，不信任任何具体类型。这个“最小可信接口”的设计思路，后来也影响了整个泛型编程的写法。
2. 五类迭代器的能力阶梯：算法调度背后的“能力证书”
2.1 先记住这张能力对照表
迭代器不是一个扁平的概念，它内部有明确的等级体系。标准库把迭代器能力分成五类，从弱到强依次是：输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器。每一种都承诺一组操作，更强的类别自动继承更弱类别的全部能力。
| 能力 | 输入迭代器 | 前向迭代器 | 双向迭代器 | 随机访问迭代器 |
|---|---|---|---|---|
读取当前元素（*it） | 支持 | 支持 | 支持 | 支持 |
向前移动（++it） | 支持 | 支持 | 支持 | 支持 |
| 多次遍历同一序列 | 不支持 | 支持 | 支持 | 支持 |
向后移动（--it） | 不支持 | 不支持 | 支持 | 支持 |
一次跳 n 步（it + n） | 不支持 | 不支持 | 不支持 | 支持 |
下标访问（it[n]） | 不支持 | 不支持 | 不支持 | 支持 |
比较大小（a < b） | 不支持 | 不支持 | 不支持 | 支持 |
这张表一定要背熟。算法能不能接收你的迭代器，就看你提供的迭代器落在哪一级。比如std::sort要求随机访问迭代器，因为快速排序每次都要比较并跳跃中间位置；std::reverse要求双向迭代器，因为它要从两头向中间交换；std::forward_list只提供前向迭代器，所以你没法对它调用std::reverse。这种分类不是拍脑袋，而是每种容器的物理结构决定了它天然只能提供哪级能力。
2.2 各类迭代器出现在哪：容器与流场景
输入迭代器最典型的例子是std::istream_iterator。它能从输入流里逐个读取数据，读过的数据不会回头重来——你没法“倒回去”再看一眼上一次读的值。它满足“单遍扫描”的语义，恰好符合输入流的性质。输出迭代器则反过来，std::ostream_iterator只能往里写，写完就没了，没有读的能力。这两个类别虽然能力最弱，但能把标准算法直接接在 I/O 上，比如用std::copy把一组数直接打印到控制台。
前向迭代器是“能反复扫描同一序列”的底线能力，std::forward_list的迭代器就是这个档次。双向迭代器加上了--回退能力，std::list、std::map、std::set都提供它。到了随机访问迭代器这一档，vector、deque、array的迭代器都能做到任意跳转和下标访问。每一档能力都对应容器内存布局的“物理自由度”——链表节点想吃回头草可以，想瞬间跳到中间不行，因为只能沿着指针走。
2.3 能力差异如何决定算法效率
迭代器等级不只是“能不能编译”的问题，它直接决定算法的时间复杂度。std::distance(first, last)求两个迭代器之间的距离：对随机访问迭代器，直接返回last - first，O(1)；对前向迭代器或双向迭代器，只能从first一路++数过去，O(n)。实现上标准库就是用标签分发做优化的，下一节会讲。
另一个典型是std::advance(it, n)。随机访问迭代器直接it += n，双向迭代器要循环 n 次++或--，前向迭代器只能正向单调地走。你的容器能力越强，同样的调用得到的速度就越快。这也是为什么选容器时要考虑“我要调哪些算法”——决策不能只盯着常用操作，还要看你打算给它喂什么算法。
3. iterator_traits 与 tag dispatch：算法是怎么“试”出迭代器能力的
3.1 一个质疑：模板不是轻量能把类型拿全吗？
既然迭代器是个类模板，算法直接在里面decltype推断不就行了？理论上可以，但标准库遇到两个实际问题：第一，迭代器类型要提供统一的信息接口，否则每个算法都得自己猜测；第二，存在原生指针这种“天然迭代器”，指针没有成员 typedef，算法没法从指针身上问出value_type。两个问题合在一起，标准库引入了一个统一的中转站：std::iterator_traits。
template <typename Iterator> struct iterator_traits { using value_type = typename Iterator::value_type; using difference_type = typename Iterator::difference_type; using pointer = typename Iterator::pointer; using reference = typename Iterator::reference; using iterator_category = typename Iterator::iterator_category; };对原生指针，标准库额外提供了一个偏特化版本，把T*直接映射成相关的五个类型。这样算法写typename std::iterator_traits<It>::value_type，就既能处理自定义迭代器，也能处理裸指针。traits 就是“给任何迭代器提取身份信息”的清洁接口。
3.2 标签分派：编译期“路由”
traits 里最重要的字段是iterator_category。它是一个表示迭代器等级的空类型，比如std::input_iterator_tag、std::forward_iterator_tag、std::random_access_iterator_tag。这些空类型本身没有任何数据，唯一的用途是参与函数重载。算法根据iterator_category选择不同版本的重载函数，这就是 tag dispatch（标签分派）。
namespace detail { // 普通版本：适用于前向/双向迭代器，线性前进 template <typename InputIt, typename T> InputIt find_impl(InputIt first, InputIt last, const T& val, std::forward_iterator_tag) { while (first != last) { if (*first == val) return first; ++first; } return last; } // 随机访问版本：同样只能线性比较，但可以留出优化空间 template <typename RandomIt, typename T> RandomIt find_impl(RandomIt first, RandomIt last, const T& val, std::random_access_iterator_tag) { while (first != last) { if (*first == val) return first; ++first; } return last; } } template <typename InputIt, typename T> InputIt find_any(InputIt first, InputIt last, const T& val) { using category = typename std::iterator_traits<InputIt>::iterator_category; return detail::find_impl(first, last, val, category{}); }这段代码整个逻辑都没变，但难点在于：它在编译时就把“迭代器属于哪一级”定下来了，不会引入运行时判断开销。模板实例化时category{}会被推断成某个具体的 tag 类型，编译器只保留匹配的那个函数版本。这个技巧在 STL 源码里稀疏平常，你写的自定义泛型代码也能用。它比if constexpr更古老，也比 C++ 早期的手写特化更轻，直到今天依然是一个值得掌握的编译期路由手法。
3.3 C++20 之后：concept 的接管
C++20 引入了 concept，约束编程不再完全依赖 tag dispatch 那套转发。你可以直接写：
template <std::random_access_iterator It> void sort_wrapper(It first, It last) { /* ... */ }编译器会在实例化时检查It是否满足随机访问迭代器的全部要求。tag dispatch 依然存在，但很多场景下 concept 提供的静态约束让代码读起来更直接。我的建议是：读老代码要知道 traits 和 tag dispatch，写新代码优先考虑 concept。底层逻辑没有改变，迭代器依然必须提供那五个类型别名和对应运算符。
4. 迭代器失效：程序跑着跑着就黑屏的常见元凶
4.1 一个典型崩溃模式的逐步拆解
如果你现在去搜索引擎查 STL 高频 bug，迭代器失效绝对能排进前三。最经典的错误是“在遍历 vector 时删除元素”：
std::vector<int> v{1, 2, 3, 4, 5}; for (auto it = v.begin(); it != v.end(); ++it) { if (*it % 2 == 0) { v.erase(it); // 错误：erase 之后 it 已失效 } }这段代码的问题在于：v.erase(it)会把it之后的元素全部向前搬移，让it指向的内存变成悬垂区域，同时也会破坏原有迭代器的有效性。循环里继续++it，本质上是在一个已经失效的迭代器上做自增操作，行为未定义。为什么在 debug 下有时不崩、release 下必崩？因为 vector 底层数据没有被立即回收，失效迭代器在内存里“看起来还能用”，碰上内存内容变化的时机才爆。
正确的写法有几种。最不容易出错的是利用erase的返回值：
for (auto it = v.begin(); it != v.end();) { if (*it % 2 == 0) { it = v.erase(it); } else { ++it; } }erase返回被删除元素的下一个元素的迭代器，于是循环结构变得清楚：删除时接过新迭代器，不删除时正常前进。另一种根本不用迭代器写循环的做法是用 erase-remove 惯用法：
v.erase(std::remove_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; }), v.end());这个组合先remove_if把不满足条件的元素移到区间末尾，再一次性erase掉尾部垃圾。它规避了“边遍历边删”的迭代器失效问题，而且通常性能更好，因为元素搬移次数最少。
4.2 各容器的失效规则速查表
搞清楚哪些操作会让哪些迭代器失效，是避免崩盘的基本功。不同容器的失效范围相差很大，我把主流容器的规则整理了一张表，都是极简结论，复杂细节看标准：
| 容器 | 触发操作 | 失效范围 |
|---|---|---|
vector/string | 插入导致重新分配内存 | 全部迭代器、指针、引用 |
vector/string | 插入/删除未重新分配 | 插入/删除位置到末尾的所有迭代器 |
deque | 两端插入/删除 | 涉及端点分块调整时可能全体失效，尤其中间插入 |
list/forward_list | 插入/删除 | 仅被删除元素的迭代器，其他全部安全 |
map/set | 插入/删除 | 仅被删除节点指向的迭代器 |
unordered_map/unordered_set | 插入触发 rehash | 全部迭代器 |
unordered_map/unordered_set | 仅删除，不 rehash | 仅被删除元素的迭代器 |
一个容易被忽略的规则是vector扩容：push_back如果导致容量不够，内部会重新申请一块更大的连续内存，把所有元素搬过去，此时所有迭代器、指针、引用全部失效。最危险的是你以为只插一个元素，但迭代器已经被底层指针变更全部作废。所以在循环里既遍历又用push_back向 vector 加数据，是典型的隐患组合。更安全的做法是先预估容量reserve，或者改用“先算好数量再一次性插入”的方式。
4.3 erase 返回值与“删除-移除”惯用法
C++11 之前，容器erase有两种重载：删除单个迭代器、删除一个迭代器区间。那时 list 的erase返回删除元素的下一迭代器，vector 的erase也返回，但很多老代码不知道用，于是“先减后删”的怪异写法满天飞。C++11 以后各大实现基本保证erase返回下一个有效元素的迭代器，推荐一律用返回值接住。
再说说“删除-移除”惯用法为什么是首选。std::remove不是真的“删除”元素，它只是把要保留的元素搬到前面，返回新逻辑末尾对应的迭代器。配合erase才真正缩减 size。这个组合对 vector、string 这类连续序列特别友好，对 list 则可以直接调用 list::remove_if（list 自己做了优化）。算法层面不想纠结失效问题的话，能交给标准组合就交给标准组合。
5. 手写一个可放进标准算法的自定义迭代器
5.1 需求：用迭代器包装“大步遍历”
前面讲的都是“用现成的”，这一节进入“写自己的”。自定义迭代器在业务代码里并不罕见：封装一个分页视图、按固定步长取样数组、迭代一个二进制文件的记录块，都用得上。我挑一个简单的例子：ChunkView，以固定步长线性访问一段数组元素的工具。比如有 10 个数，你想隔 2 个取一个，那么遍历结果应该是 arr[0]、arr[2]、arr[4]……。
template <typename T> class ChunkView { public: ChunkView(T* data, std::size_t count, std::size_t step) : m_data(data), m_count(count), m_step(step) {} class iterator { public: using iterator_category = std::forward_iterator_tag; using value_type = T; using difference_type = std::ptrdiff_t; using pointer = T*; using reference = T&; iterator(T* ptr, std::size_t step) : m_ptr(ptr), m_step(step) {} reference operator*() const { return *m_ptr; } pointer operator->() const { return m_ptr; } iterator& operator++() { m_ptr += m_step; return *this; } iterator operator++(int) { iterator tmp = *this; ++(*this); return tmp; } bool operator==(const iterator& other) const { return m_ptr == other.m_ptr; } bool operator!=(const iterator& other) const { return !(*this == other); } private: T* m_ptr; std::size_t m_step; }; iterator begin() const { return iterator(m_data, m_step); } iterator end() const { return iterator(m_data + m_count * m_step, m_step); } private: T* m_data; std::size_t m_count; std::size_t m_step; };这段代码是“最简但可用”的模板。它已经能塞进std::for_each、std::count_if、std::find_if等算法里，因为它们对前向迭代器的要求就这么多。注意iterator_category我选的是std::forward_iterator_tag：我没有实现--，所以不能宣称自己支持双向；但++可以一直往前走，比输入迭代器多了“可多重扫描”能力，因此定义为前向迭代器。
5.2 核心实现：五个类型别名加六个运算符
自定义迭代器能不能被标准库接受，关键在于它必须是一个“规范的迭代器”。官方要求其实就两件事：提供五个 typedef，实现必要的运算符。五个 typedef 是iterator_category、value_type、difference_type、pointer、reference。有了它们，std::iterator_traits才能正常工作。上面我直接在类内部写了using别名，这就是提供给 traits 的接口。
运算符方面，读语义的迭代器至少要实现：解引用*、箭头->、前置自增++、后置自增++(int)、相等==、不等!=。后置自增的惯用实现是“先复制、再自增、返回副本”，一定要返回旧值而不是引用。很多人漏了operator->，结果迭代器没法访问元素的成员函数或字段。箭头操作符的返回类型是指针时可以直接返回，返回自定义代理对象也行，但新手阶段直接用pointer最省事。
5.3 新手最常漏掉的三处细节
写迭代器最容易踩的坑，我整理成三条忠告：
常量性没处理好。上面例子里的
operator*返回的是T&，意味着通过迭代器可以修改底层数据。如果你希望const ChunkView遍历时不能写数据，严格做法是再写一个const_iterator并让其解引用返回const T&。很多代码只写一个 iterator，导致 const 对象完全没法遍历，这是很尴尬的接口缺陷。判断
end()的语义要想清楚。我这里的end()是“最后一个有效元素之后再走一个 step”的位置，而不是“最后一个元素”。这种“尾后”语义和 STL 的[begin, end)半开区间一致，算法才能正确判断终止。千万别把 end 做成最后一个有效元素，否则当你对空视图调用 begin 和 end 时会得到相同的指针吗？空视图应让 begin 和 end 相等，我上面的实现已经符合。不同 step 的迭代器不要互相比较。我这个实现里两个迭代器比较只看裸指针，如果一个是 step=2 的迭代器、一个是 step=3 的迭代器，它们可能碰巧指向同一个地址，比较结果就是“相等”，这在语义上是错的。严谨的做法是在相等判断里同时比较 step，或者干脆规定同一视图的迭代器才能互相比较。自定义迭代器越接近 STL 风格，越要提前考虑这些“读者可能不看但有隐藏行为”的细节。
6. 迭代器适配器：反向遍历与“把写入包装成迭代器”
6.1 反向迭代器 base() 的偏移，看似反直觉其实很严谨
std::vector<int> v{1,2,3,4,5};，想从后往前遍历，直接写for (auto it = v.rbegin(); it != v.rend(); ++it)循环体里看到的输出是5 4 3 2 1。这是 STL 早就提供的反向迭代器适配器。但很多人拿到rbegin()之后想转回正向迭代器，一用base()就懵：
auto rit = v.rbegin(); // 指向逻辑上的 5 auto it = rit.base(); // 你以为是 v[4]，实际上是 v.end()为什么？因为 STL 的半开区间设计规定：正向区间是[begin, end)，反向迭代器的逻辑区间变成了[rbegin, rend)，折回到正向时，rbegin().base()恰好是end()，而不是begin() + (size-1)。base() 永远指向“反向迭代器当前逻辑元素的下一个正向位置”。这个偏移不是你写错了，而是区间法则的必然结果。
对应的转换公式很简洁：如果rit逻辑上指向元素x，那么rit.base()是x的下一个元素；反过来，如果你想在正向迭代器it的位置构造一个反向迭代器，用std::make_reverse_iterator(it)，它逻辑上指向it的前一个元素。理解这个偏移最直接的方法是把rbegin()想成reverse_iterator(end())，把rend()想成reverse_iterator(begin())——反向迭代器只是在正向区间的基础上做了一个“起点换成终点、终点换成起点”的封装，具体元素位置靠解引用时的-1偏移来修正。
6.2 插入迭代器：让算法可以从“输出尾巴”写数据
反向迭代器处理“从后往前读”，插入迭代器则负责“把算法输出接到容器写入”上。std::copy可以把一段数据拷贝到输出迭代器，而输出迭代器再往容器里写时，有三种适配策略：back_inserter在末尾push_back，front_inserter在头部push_front，inserter在指定位置insert。
std::vector<int> src{1, 2, 3}; std::vector<int> dst; std::copy(src.begin(), src.end(), std::back_inserter(dst)); // dst: 1 2 3这里的关键是：dst一开始是空的，而你并没有预先分配空间。如果没有back_inserter，你就得先resize到 3，再按位置赋值。back_inserter把“写”操作翻译成“在末尾追加”，使算法无需知道目标容器现在有多大，也不用预知数据量。对 list 这类可以高效头插的容器，front_inserter则能玩出“反转拷贝”的效果。
6.3 插入迭代器的性能代价，多数人没注意
插入迭代器让代码写起来极爽，但用之前要想清楚性能。反复push_back在 vector 上如果没有提前reserve，可能触发多次扩容搬移，最终复杂度从 O(n) 退化成 O(n) 分摊摊还——其实也不是灾难，但如果你明确知道数据量，最好先dst.reserve(src.size())再挂back_inserter。反过来用inserter往 vector 中间反复插入，每次插入都导致后面元素搬移，复杂度是 O(n*m)，数据量一大立刻暴露性能问题。这种“用起来简单，跑起来慢”的情况，正是迭代器适配器带给懒人的陷阱。
要在网上找这类性能问题的经验，正常搜“back_inserter reserve”、“insert iterator performance”这些词就有大量讨论。我的建议始终是：迭代器适配器是便利工具，不是让你忘记数据结构特性的借口。它把“写入动作”抽象成了接口，但底层代价永远是真实存在的。选适配器之前，先问一句：这个目标容器的插入操作是高效的吗？
最后分享一条我个人的实操体会：真正把迭代器用顺，不是靠背接口，而是靠把“半开区间”“迭代器失效”“能力等级”这三个概念刻进脑回路。半开区间决定了所有循环边界写法，失效规则决定你能不能边遍历边改容器，能力等级决定你在算法调度和自定义迭代器时会不会踩坑。遇到新容器、新接口，先拿这三个维度去套，基本都能迅速定位问题。尤其是自定义迭代器这门手艺，标准库里现成的东西再多，也总有你需要“按某套规矩造轮子”的一天，把前面那五个 typedef 和六个运算符练熟，以后读源码、写泛型代码都会顺手很多。
