迭代器模式（Iterator）：用统一的方式遍历一切
更新时间：2026-08-25。本文按"先看不用模式的困境 → 再用模式重构 → 类图对比分析"的结构，论述迭代器模式。可运行代码：demos/design-patterns/iterator。
一、问题场景：不同容器要有统一的遍历方式
遍历数组、链表、二叉树、哈希表、图……容器内部结构不同，但客户端希望"遍历"这件事用同一套写法，且遍历过程中不暴露内部表示。
二、不使用模式：客户端按容器结构各写各的遍历
cpp
// 数组
for (size_t i = 0; i < arr.size(); i++) { visit(arr[i]); }
// 链表
for (Node* n = head; n; n = n->next) { visit(n->data); }
// 二叉树
void dfs(Node* n) { if (!n) return; visit(n->val); dfs(n->left); dfs(n->right); }
// 每个容器一套遍历逻辑，客户端要知道内部结构| 缺陷 | 说明 |
|---|---|
| 遍历代码散落 | 每处用容器都要重写遍历逻辑 |
| 暴露内部结构 | 客户端必须知道数组下标/链表指针/树递归 |
| 违反 LoD/封装 | 客户端深入了解容器内部 |
| 无法统一算法 | 想写"对所有容器求和"，每种容器写一遍 |
不使用模式的类图
三、使用模式：迭代器统一"取下一个"的接口
迭代器模式让容器提供 begin()/end() 返回迭代器；迭代器实现统一的 operator*（当前元素）、operator++（下一个）、operator!=（是否到头）。客户端只写一套遍历代码，容器内部结构完全隐藏。
cpp
// 统一遍历接口（C++ 迭代器约定）
template <typename T>
double sumAll(T& container) {
double s = 0;
for (auto it = container.begin(); it != container.end(); ++it)
s += *it;
return s;
}
// 同一套代码遍历任何容器
std::vector<int> v{1,2,3};
std::list<int> l{1,2,3};
Tree<int> t(/* 二叉树 */);
sumAll(v); sumAll(l); sumAll(t); // 客户端无感知容器内部
// 自定义树容器只需提供自己的迭代器
template <typename T>
class Tree {
public:
class Iterator { // 树迭代器：封装前序/中序遍历状态
// operator* / operator++ / operator!= 实现
};
Iterator begin() { return Iterator(root_); }
Iterator end() { return Iterator(nullptr); }
};使用模式的类图
四、类图对比与分析
| 维度 | 不使用（按结构遍历） | 使用迭代器 |
|---|---|---|
| 遍历代码 | 每种容器一套 | 一套通用 |
| 内部结构 | 暴露给客户端 | 完全隐藏（封装） |
| 加新容器 | 客户端新写遍历 | 容器提供迭代器即可 |
| 遍历算法复用 | 无 | 求和/过滤/转换通用于一切容器 |
| 结构成本 | 无 | 容器要额外实现迭代器 |
分析结论：迭代器把"遍历"从客户端劳动变成容器能力，客户端只写一套代码。C++ 里 STL 已内置（vector/list 迭代器），本仓库重点是自定义容器的迭代器实现——注意迭代器失效规则（容器修改后迭代器可能失效）与遍历期间的结构突变风险。范围 for 循环（range-based for）就是迭代器模式的语法糖。
五、适用边界
| 适用 | 不适用 |
|---|---|
| 多种容器要统一遍历 | 只有一种简单容器（下标即可） |
| 容器结构要对外隐藏 | 客户端就是要裸数据访问 |
| 遍历期间需要安全保护（快照/快迭代） | 极热路径在意迭代器抽象开销（可裸循环） |
迭代器失效（本仓库坑点）：vector 扩容、list 删除元素都会使迭代器失效——遍历中修改容器是经典 bug 源；需要边遍历边删时用 erase 返回的迭代器或改用索引/标记延迟删除。
一句话总结
迭代器模式让容器提供统一的 begin()/end() 与迭代器接口，客户端用同一套代码遍历任意容器、内部结构不外泄——遍历从客户端劳动变成容器能力，算法可通用于一切容器；代价是容器需实现迭代器且要遵守迭代器失效规则。