1. 迭代器模式到底在解决什么问题1.1 从一个没法复用的遍历代码说起如果你写过一阵子 C肯定见过这种代码std::vectorint v{1, 2, 3, 4}; for (size_t i 0; i v.size(); i) { std::cout v[i] std::endl; }这段代码本身没毛病但你想把它换到std::list上立刻就行不通。链表不提供随机下标访问你要是强行用v[i]写出来的效率也会惨不忍睹。你想把“遍历一堆元素”这动作抽象出来复用下标方案做不到。迭代器模式解决的就是这个问题把“怎么遍历”和“用什么容器存”彻底分开。遍历方只跟迭代器打交道迭代器负责把容器内部的真实结构藏起来对外暴露统一的、*、这些操作。你可以在不知道容器底层是数组、链表、红黑树还是哈希表的情况下写出对它们一视同仁的算法代码。你可以把迭代器理解成图书馆的索书牌。书库内部是分架区还是密集架读者根本不需要关心读者拿到的索书牌会精确指向某一本书往前走一格就是下一本接着往前走还能继续找到更多书。图书管理员只要保证索书牌能正确映射到每本书读者的遍历流程就永远成立。这正是设计模式里典型的“行为型模式”它解耦的不是数据结构本身而是遍历这一行为。1.2 为什么 C 把迭代器变成了“算法协议”C 的迭代器和其他语言里的Iterator接口相比另一个显著不同是它不是靠虚函数约定而是靠“结构化语义 编译期契约”。这意味着标准库算法std::sort、std::find、std::accumulate不关心你迭代器的具体类型是什么只看你满不满足它需要的操作。满足多少能力就用多少能力。比如同样是找元素std::vectorint vec{10, 20, 30, 40}; std::listint lst{10, 20, 30, 40}; auto it1 std::find(vec.begin(), vec.end(), 30); auto it2 std::find(lst.begin(), lst.end(), 30);这两行代码的调用形式完全一样。但内部实现路径完全不同vector的迭代器是随机访问底层内存连续如果没有特殊优化算法也可以一个个走过去list的迭代器只能沿节点指针向前跳。对于使用者来说写法不变性能特征却一目了然——这正是 C 讲究“不为你不需要的东西买单”的体现。学这个模式的时候我最怕有人把它当成“八股概念”背下来。你真正要领会的是迭代器是连接算法与容器之间的协议层。设计模式书籍里描绘的 UML 类图落到 C 里就是这套类型契约和运算符语义。后面我会写一个完整可编译的自定义迭代器你跟着走一遍比背十张 UML 图都管用。2. 理解边界迭代器的分类与指针血缘2.1 五个迭代器类别的层次关系C 迭代器一共有五个分类很多人看到input_iterator、output_iterator、forward_iterator、bidirectional_iterator、random_access_iterator就头大。其实你不用背全只需要抓住一条主线输入/输出迭代器 → 前向迭代器 → 双向迭代器 → 随机访问迭代器这里输入和输出是两个独立分支日常使用中你可以先粗略理解为“功能更弱的前向迭代器”。具体看输入迭代器只能单向移动、*读取、不能回退典型代表是istream_iterator它包裹一个输入流每次相当于从流里读下一个值。输出迭代器只能单向写入*配合赋值使用典型代表是ostream_iterator。前向迭代器既能读也能写还支持保存迭代器副本继续推进典型代表是forward_list的迭代器。双向迭代器在前向基础上支持--能往前走也能往后退list、set、map的迭代器属于这一类。随机访问迭代器在双向基础上支持it n、it - n、it[n]甚至能做大小比较和求距离vector、deque的迭代器以及原生指针都属于这一类。为什么算法要区分这个层次因为不同能力可以让算法走不同实现路径。std::distance(it1, it2)遇到随机访问迭代器时直接算it2 - it1复杂度是 O(1)遇到双向迭代器时只能一个个数过去复杂度 O(n)。算法本身不笨它在编译期通过迭代器的 category 标签做分发。2.2 指针就是最朴素的迭代器C 里原生指针天然满足随机访问迭代器的全部操作*p解引用、p n跳转、p1 - p2求距离甚至p[n]走下标。所以数组可以不用写专门的迭代器类直接用T*作为begin()和end()的返回类型。这带来一个非常实用的启示写自定义迭代器本质上就是在模拟指针的语义。每写一个运算符重载之前先问自己一句如果这是一个原生指针它应该有什么行为照着这个思路去写基本不会跑偏。具体到代码实现上绝大多数自定义迭代器内部就放一个指向容器元素的原始指针或者指向链表节点的指针然后把自己包装成“一个受控的指针”。比如我后面案例里的FixedArrayIterator内部只有一个T* ptr_所有操作都是基于这个指针转译出来的。提示你完全可以在某些简单容器里直接把iterator定义成T*这是合法且高效的。但它的缺点是丢失了迭代器 traits 里的额外信息标准库在使用某些高级算法时可能把它当原生指针行为不够精确。正式代码里还是建议写一个完整的迭代器类至少做一次类型包装。3. 手写一个可用的迭代器从固定容器到完整实现3.1 从一个固定容量容器开始纸上谈兵没意思我直接以一个“固定容量小数组容器”为例把从容器到迭代器的每一步写出来。这种容器适合游戏里那些不想每次都做堆分配的场景元素数量有上限栈上放一块连续内存就够用。先用最原始的方式实现容器templatetypename T, std::size_t N class FixedArray { public: using value_type T; using iterator T*; T* begin() { return buf_; } T* end() { return buf_ N; } private: T buf_[N]; };这段代码能跑range-for也能正常遍历。但它还不够“设计模式”万一容器变成链表、跳表、B 树叶子链T*立刻失效。为了真正理解迭代器模式我下面把迭代器改成独立类。3.2 迭代器类的核心实现与五个成员类型自定义迭代器最容易被忽略的是五个嵌套类型。如果只把operator和operator*写出来很多算法编译不过因为算法内部需要通过迭代器拿到元素类型、指针类型、差值类型等元信息。templatetypename T class FixedArrayIterator { public: using iterator_category std::random_access_iterator_tag; using value_type T; using difference_type std::ptrdiff_t; using pointer T*; using reference T; FixedArrayIterator() : ptr_(nullptr) {} explicit FixedArrayIterator(T* p) : ptr_(p) {} reference operator*() const { return *ptr_; } pointer operator-() const { return ptr_; } FixedArrayIterator operator() { ptr_; return *this; } FixedArrayIterator operator(int) { FixedArrayIterator tmp *this; ptr_; return tmp; } FixedArrayIterator operator--() { --ptr_; return *this; } FixedArrayIterator operator--(int) { FixedArrayIterator tmp *this; --ptr_; return tmp; } private: T* ptr_; };为什么必须有这五个类型因为 STL 内部大量依赖std::iterator_traitsIt::value_type这种机制。比如std::accumulate里需要定义累加的临时变量如果不知道元素类型编译直接失败。iterator_category则像一张“能力证明”告诉算法我是随机访问的你可以大胆用it n和it - it。这里我故意把指针类型定义成T*、引用类型定义成T意图也值得解释当T是const U时这个类自动变成const迭代器。后面第 4 节我会详细讲这一点。3.3 补上随机访问操作并通过静态校验既然标了random_access_iterator_tag就必须把随机访问能力补齐否则等于吹牛不兑现。至少要写下面这些FixedArrayIterator operator(difference_type n) { ptr_ n; return *this; } FixedArrayIterator operator-(difference_type n) { ptr_ - n; return *this; } friend FixedArrayIterator operator(FixedArrayIterator it, difference_type n) { it n; return it; } friend FixedArrayIterator operator(difference_type n, FixedArrayIterator it) { it n; return it; } friend FixedArrayIterator operator-(FixedArrayIterator it, difference_type n) { it - n; return it; } friend difference_type operator-(const FixedArrayIterator a, const FixedArrayIterator b) { return a.ptr_ - b.ptr_; } friend bool operator(const FixedArrayIterator a, const FixedArrayIterator b) { return a.ptr_ b.ptr_; } friend bool operator!(const FixedArrayIterator a, const FixedArrayIterator b) { return a.ptr_ ! b.ptr_; } friend bool operator (const FixedArrayIterator a, const FixedArrayIterator b) { return a.ptr_ b.ptr_; } friend bool operator (const FixedArrayIterator a, const FixedArrayIterator b) { return a.ptr_ b.ptr_; } friend bool operator(const FixedArrayIterator a, const FixedArrayIterator b) { return a.ptr_ b.ptr_; } friend bool operator(const FixedArrayIterator a, const FixedArrayIterator b) { return a.ptr_ b.ptr_; }之后把容器端改成返回自定义迭代器templatetypename T, std::size_t N class FixedArray { public: using value_type T; using iterator FixedArrayIteratorT; iterator begin() { return iterator(buf_); } iterator end() { return iterator(buf_ N); } private: T buf_[N]; };写完后最好用编译期断言验证一遍而不是只看“能编译”就觉得没问题。C20 之前可以用std::iterator_traitsC20 以后直接用概念#include concepts static_assert(std::random_access_iteratorFixedArrayIteratorint);编译通过只能说明语法正确但类型语义是不是真的满足随机访问静态断言说了才算。我在写生产代码时几乎每给迭代器加一个功能就加一个static_assert因为迭代器一旦嵌入算法内部运行期出错的排查成本远比编译期高。4. 细节决定成败const 迭代器与反向遍历4.1 const 迭代器的正确打开方式新手最容易翻车的地方就是 const 迭代器。很多人以为只要给容器加上const_iterator begin() const就万事大吉结果在函数里直接被编译错误打脸。你首先要清楚一件事const 迭代器 指向 const 数据的迭代器而不是“迭代器对象本身不可修改”。这两种语义完全不一样。最简单的实现手法是让迭代器类模板化。用T可以既是普通类型又是const Utemplatetypename T class FixedArrayIterator { // 上面第 3 节里的所有代码照抄 using value_type T; };然后在容器里同时定义两种别名using iterator FixedArrayIteratorT; using const_iterator FixedArrayIteratorconst T; iterator begin() { return iterator(buf_); } const_iterator begin() const { return const_iterator(buf_); } const_iterator cbegin() const { return const_iterator(buf_); }当T const U时operator*的返回类型会退化成const U调用方只能读取不能修改。这就是“同一个类模板实例化两次自然得到两种语义”的技巧很多开源容器库都采用这个方案。注意别用const FixedArrayIteratorT作为const_iterator。那表达的是“迭代器对象本身不可变”不是“指向的对象不可变”。这个错误一旦犯下用户在 const 容器上还能通过迭代器修改元素编译期根本发现不了隐患。4.2 reverse_iterator 的“偏移一格”陷阱标准库里的std::reverse_iterator是一个适配器。它包住一个正向迭代器把映射成内部正向迭代器的--把--映射成内部的。你可以直接用没必要自己重造轮子using reverse_iterator std::reverse_iteratoriterator; reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); }这里最隐蔽的坑是rbegin()构造时传入的是end()而不是最后一个元素的位置。因为reverse_iterator内部存放的永远是“逻辑当前位置的下一个位置”取*rbegin()的时候它要先做内部--再解引用。如果你以后自己实现反向迭代器一定要记住这个“偏移一格”的语义。我自己就踩过这个坑早期实现反向迭代器时直接在begin()上构造结果首元素访问不到还隔三差五触发未定义行为。后来把构造参数改成end()所有问题一次性消失。5. 让自定义迭代器在 STL 算法里跑起来5.1 实战验证用 accumulate / reverse / sort 做压力测试迭代器写得好不好拉进标准库算法里遛一遛就知道了。下面是三个最常用的验证场景#include numeric #include algorithm FixedArrayint, 4 arr{10, 20, 30, 40}; int sum std::accumulate(arr.begin(), arr.end(), 0); // 100 std::reverse(arr.begin(), arr.end()); // arr 变为 {40, 30, 20, 10} std::sort(arr.begin(), arr.end()); // arr 恢复为 {10, 20, 30, 40}std::accumulate能通过说明输入迭代器语义没问题std::reverse能通过说明双向迭代器的--实现正确std::sort能通过说明随机访问和元素交换都正常。我最喜欢拿std::sort当试金石因为std::sort对迭代器要求极高内部会频繁调用std::iter_swap、比较运算符、operator-计算中点左右位置任何一处语义不对排序结果就会错得不着边际甚至直接崩溃。跑一次std::sort等于给迭代器做了全套心肺体检。5.2 用编译期断言守住迭代器契约除了运行期测试编译期静态校验也很重要。我习惯在文件底部写一批static_assert让编译器充当永远不厌烦的测试框架static_assert(std::is_same_v std::iterator_traitsFixedArrayIteratorint::iterator_category, std::random_access_iterator_tag); static_assert(std::is_same_v std::iterator_traitsFixedArrayIteratorint::value_type, int);如果你用的是 C20可以直接写标准概念更简洁也更符合现代写法。这些断言看着不起眼但在后续维护中价值巨大一旦有人把迭代器悄悄改成单链表版本却忘了改iterator_category算法可能选择了错误路径运行期只表现为莫名其妙变慢或者越界。有断言兜底错误在编译期就暴露了。6. 迭代器使用中的经典翻车现场6.1 迭代器失效永远先怪容器迭代器失效不是迭代器本身的问题而是容器结构变化导致的。最常见的例子是std::vector扩容std::vectorint v{1, 2, 3}; auto it v.begin(); v.push_back(4); // 触发扩容重新分配内存 // it 已经指向旧内存 —— 悬空 *it 99; // 未定义行为这个跟自定义迭代器直接相关如果你的容器内部用裸地址表示迭代器一旦容器重新分配存储所有旧迭代器集体失效。只是标准库容器已经明确规定了各自的失效规则而你的自定义容器必须把规则写在文档或者注释里否则用户会拿标准库的行为惯性来套你的容器然后踩坑。我自己的经验是迭代器内部永远不要缓存“位置之外”的任何东西。比如不要缓存容器指针更不要缓存某个索引值然后每次解引用时再去索引那会让迭代器语义彻底乱套。最简单的底层表示永远是“一个直接指向元素的原始指针或节点地址”。6.2 调试迭代器的几个土办法迭代器的问题经常在算法内部暴露而不是在你写的几行代码里。比如std::sort崩溃堆栈上只能看到一堆模板内部函数你自己写的迭代器代码早就被内联消失了。这时候我一般这么做临时在迭代器类的operator*、operator里加断言检查指针是否落在容器边界内。开启标准库调试模式GCC/libstdc 用_GLIBCXX_DEBUG宏MSVC 用/D_ITERATOR_DEBUG_LEVEL2。开启后标准库容器会帮你检查迭代器是否越界使用。记录迭代器创建时的容器地址解引用前再核对一遍类似弱引用的作用。第二个技巧特别值钱。默认编译模式下STL 迭代器基本不做边界检查很多越界问题只有在 debug 模式下才暴露。我遇到过一种死循环就是自定义容器返回的end()比实际缓冲区多了一个元素导致std::find一直读到了容器外部的内存。开了调试模式后编译器立刻报告越界问题瞬间定位。6.3 不同容器迭代器的比较问题两个来自不同容器的迭代器做比较在自定义迭代器里如果只是简单比较底层指针很难被及时拦截。例如v1.begin() v2.begin()底层指针恰好指向同一块内存的极端情况也存在但更常见的是它们指向不同地址比较结果一直是false你浑然不觉哪里出错。标准库的态度是比较不同容器的迭代器属于未定义行为。自定义迭代器也应该延续这个契约。如果你确实需要兼容这种误用可以考虑在 debug 模式下缓存容器标识比较前先查归属但在 release 版本里为了性能通常不做检查。我建议至少在注释里写明“跨容器比较未定义”让使用者心里有数。7. 现代 C 里还需要亲手写迭代器吗7.1 range-for 和标准库 ranges 带来的便利C11 的range-for让大部分人不再需要显式写出begin()和end()循环。你只要保证容器有这两个成员函数遍历逻辑就成了三个字符的事。C20 更进一步推出了std::ranges和视图适配器std::vectorint v{1, 2, 3, 4, 5}; auto even v | std::views::filter([](int x) { return x % 2 0; }) | std::views::transform([](int x) { return x * x; });你在这段代码里一个迭代器都看不到但ranges内部工作的核心依然是由一个个 view 迭代器串联完成的。问题是这些 view 迭代器的类型复杂得吓人比如transform_view::iterator同时包装了内部迭代器和函数对象解引用时调用变换函数比较时又要同时比较两个内部迭代器。如果你不理解迭代器模式的基本协议碰到这种复杂迭代器里的 bug连下手的思路都没有。7.2 哪些场景下还得自己写迭代器现代 C 弱化了手写迭代器的需求但远没有消灭它。我总结过至少四类场景绕不开自定义容器类型尤其是内存紧凑的组件容器比如游戏 ECS 里的扁平数组。对非容器资源做遍历封装比如按行遍历一个二进制日志文件、把数据库查询结果集封装成迭代器。天然非连续的容器跳表、倒排索引、B 树的叶子链这些结构没法用std::vector替代。不希望暴露裸指针的专用算法接口但仍想享受 STL 算法的便利。在这些场景里迭代器模式不是“为了用模式而用”而是在真正为数据结构建立面向算法的访问协议。7.3 我个人的一些选择标准这些年写容器和迭代器我总结出几条实操标准直接说给你听。第一先想清楚自己需要哪个层次的迭代器。如果你的容器只支持单向遍历就别硬凑随机访问标签。标签写高了算法会认为你可以 O(1) 跳转一旦实际做不到性能事故在运行期才暴露标签写低了算法只能走更慢的通用路径也不会出大错。所以我的原则是标签宁低勿高。第二迭代器越像指针越好。内部只存一个裸地址运算符语义跟原生指针保持一致。不要为了炫技加缓存、加虚函数、加引用计数器这些在迭代器高频调用场景里全是性能杀手。第三能复用标准库适配器就不要重复造轮子。std::reverse_iterator、std::istream_iterator、std::ostream_iterator这些现成的东西比你自己写的绝大多数版本都稳定。真正需要上手写的是那些标准库给不了你、必须绑定具体数据结构语义的迭代器。以我个人的体会迭代器模式在 C 里不是抽象的教条而是一套非常“手艺人向”的工程契约。你把容器当作家把算法当作客户迭代器就是那位既能听懂客户要求、又对家里结构了如指掌的经纪人。这个中介设计得越简单、越贴近指针语义后面所有依赖它的人都越省心。我建议你拿到一个自定义容器后第一步就是认真写一个像样的迭代器然后拿std::sort去压测它——这比任何设计模式书籍里的类图都能让你更快明白这一层协议到底为什么存在。