# C\+\+ 迭代器模式详解

迭代器模式（Iterator Pattern）是**行为型设计模式**之一，核心思想是**提供一种统一的方式来顺序访问聚合对象中的元素，而无需暴露聚合对象的内部存储结构**。它是 C\+\+ 标准模板库（STL）的核心设计基础，将容器与算法彻底解耦，也是泛型编程的重要支撑模式。

## 一、核心思想与基本概念

### 1\. 解决的问题

不同的聚合对象（数组、链表、二叉树、哈希表）底层存储结构差异极大，如果直接暴露内部结构让客户端遍历，会带来诸多问题：

- 客户端必须了解容器的内部实现细节，耦合度极高；

- 遍历逻辑与容器本身绑定，新增遍历方式必须修改容器类，违反单一职责和开闭原则；

- 不同容器的遍历接口不统一，切换容器类型需要重写所有遍历代码。

迭代器模式把**遍历逻辑从容器中抽离**，封装成独立的迭代器对象，所有迭代器对外提供一致的访问接口。客户端只需要和迭代器交互，完全不需要知道容器底层是数组、链表还是树。

### 2\. 内部迭代器 vs 外部迭代器

- **外部迭代器**：遍历的控制权在客户端手中，客户端可以主动控制前进、后退、获取当前元素。这是最常见的形式，比如 STL 迭代器、GoF 标准定义的迭代器。

- **内部迭代器**：遍历的控制权在迭代器 / 容器内部，客户端只需要传入要执行的操作，遍历过程自动完成。比如`std::for_each`、多数语言的`forEach`方法。

### 3\. 本质

以统一的接口封装不同的遍历算法，实现「存储结构」与「遍历行为」的解耦，让算法可以透明地作用于任意容器。

## 二、模式角色与结构

迭代器模式包含 4 个核心角色：

|角色|作用|
|---|---|
|**Iterator（抽象迭代器）**|定义遍历元素的统一接口，通常包含`hasNext()`、`next()`、`current()`等方法|
|**ConcreteIterator（具体迭代器）**|实现抽象迭代器接口，针对特定容器实现具体遍历逻辑，记录当前遍历位置|
|**Aggregate（抽象聚合）**|定义创建对应迭代器的接口，通常为`createIterator()`|
|**ConcreteAggregate（具体聚合）**|实现创建迭代器的方法，返回对应具体迭代器实例，持有实际的数据存储|

## 三、经典 C\+\+ 实现（GoF 继承 \+ 虚函数版）

这是 GoF 设计模式中定义的标准实现，通过继承和虚函数实现多态，属于面向对象风格的迭代器。

### 示例场景

实现一个自定义动态数组容器，并提供对应的顺序迭代器。

```cpp
#include <iostream>
#include <vector>
#include <memory>

// 1. 抽象迭代器
template <typename T>
class Iterator {
public:
    virtual ~Iterator() = default;
    virtual bool hasNext() const = 0;  // 是否还有下一个元素
    virtual T& next() = 0;             // 移动到下一个元素并返回
    virtual T& current() const = 0;    // 获取当前元素
    virtual void reset() = 0;          // 重置到起始位置
};

// 2. 抽象聚合（容器）
template <typename T>
class Aggregate {
public:
    virtual ~Aggregate() = default;
    virtual std::unique_ptr<Iterator<T>> createIterator() = 0; // 创建迭代器
    virtual size_t size() const = 0;
    virtual T& at(size_t index) = 0;
};

// 3. 具体迭代器：动态数组迭代器
template <typename T>
class VectorIterator : public Iterator<T> {
private:
    Aggregate<T>* aggregate;
    size_t position;
public:
    explicit VectorIterator(Aggregate<T>* agg) 
        : aggregate(agg), position(0) {}

    bool hasNext() const override {
        return position < aggregate->size();
    }

    T& next() override {
        return aggregate->at(position++);
    }

    T& current() const override {
        return aggregate->at(position);
    }

    void reset() override {
        position = 0;
    }
};

// 4. 具体聚合：自定义动态数组
template <typename T>
class MyVector : public Aggregate<T> {
private:
    std::vector<T> data;
public:
    void push_back(const T& value) {
        data.push_back(value);
    }

    std::unique_ptr<Iterator<T>> createIterator() override {
        return std::make_unique<VectorIterator<T>>(this);
    }

    size_t size() const override {
        return data.size();
    }

    T& at(size_t index) override {
        return data.at(index);
    }
};

// 客户端使用
int main() {
    MyVector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);

    // 通过迭代器遍历，完全不关心容器内部实现
    auto it = vec.createIterator();
    std::cout << "遍历容器元素：" << std::endl;
    while (it->hasNext()) {
        std::cout << it->next() << " ";
    }
    std::cout << std::endl;

    // 重置迭代器，重新遍历
    it->reset();
    std::cout << "重置后再次遍历：" << std::endl;
    while (it->hasNext()) {
        std::cout << it->next() << " ";
    }

    return 0;
}
```

### 输出结果

```Plain Text
遍历容器元素：
10 20 30 40 
重置后再次遍历：
10 20 30 40
```

**扩展性说明**：如果需要新增逆序遍历，只需要新增一个`ReverseVectorIterator`迭代器子类，容器类完全不需要修改，符合开闭原则。

## 四、现代 C\+\+：STL 迭代器体系

C\+\+ 标准模板库（STL）是迭代器模式最经典的工程化实现，但它没有采用面向对象的继承 \+ 虚函数方案，而是通过 \\*\\* 泛型编程 \+ 类型约定（鸭子类型）\\*\\* 实现，性能更高、灵活性更强，是现代 C\+\+ 的主流方式。

### 1\. 核心设计思想

STL 将容器、迭代器、算法三者完全解耦：

- 容器负责数据存储，提供`begin()`和`end()`方法返回迭代器；

- 迭代器封装遍历逻辑，提供统一的操作接口（`++`、`*`、`->`等）；

- 算法只依赖迭代器接口，不关心具体容器类型，一套算法可以作用于所有符合要求的容器。

### 2\. 迭代器分类（按能力强弱）

STL 根据迭代器支持的操作，将其分为 5 类，层级依次增强，上层迭代器完全具备下层迭代器的所有能力：

|迭代器类别|支持的核心操作|典型对应场景|
|---|---|---|
|**输入迭代器**|只读、单次遍历、仅支持`++`前进|`std::istream_iterator`|
|**输出迭代器**|只写、单次遍历、仅支持`++`前进|`std::ostream_iterator`、插入迭代器|
|**前向迭代器**|可读写、多次遍历、仅支持`++`前进|`std::forward_list`、无序关联容器|
|**双向迭代器**|可读写、多次遍历、支持`++`和`--`双向移动|`std::list`、`set`、`map`|
|**随机访问迭代器**|可读写、支持任意位置跳转、支持`+/-`偏移、下标访问|`std::vector`、`deque`、`string`、原生数组|

### 3\. 范围 for 循环：迭代器的语法糖

C\+\+11 引入的范围 for 循环，底层就是基于迭代器实现的。编译器会自动将范围 for 展开为`begin()`到`end()`的迭代器遍历：

```cpp
std::vector<int> vec = {1,2,3,4};
// 范围for写法
for (int x : vec) {
    std::cout << x;
}

// 编译器等价展开
for (auto it = vec.begin(); it != vec.end(); ++it) {
    int x = *it;
    std::cout << x;
}
```

只要自定义类型实现了`begin()`和`end()`方法并返回符合要求的迭代器，就可以直接使用范围 for 循环。

## 五、自定义 STL 兼容迭代器

要让自定义迭代器能和 STL 算法配合使用，需要遵循 STL 迭代器约定，定义 5 个标准内嵌类型。

### 完整示例：自定义链表的双向迭代器

```cpp
#include <iostream>
#include <algorithm>
#include <iterator>

// 自定义双向链表节点
template <typename T>
struct Node {
    T value;
    Node* prev;
    Node* next;
    Node(const T& v) : value(v), prev(nullptr), next(nullptr) {}
};

// 自定义双向迭代器
template <typename T>
class MyListIterator {
public:
    // STL迭代器必须的5个标准类型定义
    using iterator_category = std::bidirectional_iterator_tag; // 迭代器类别
    using value_type = T;                                      // 元素类型
    using difference_type = std::ptrdiff_t;                    // 迭代器差值类型
    using pointer = T*;                                        // 指针类型
    using reference = T&;                                      // 引用类型

    explicit MyListIterator(Node<T>* node) : current(node) {}

    // 解引用操作
    reference operator*() const {
        return current->value;
    }

    pointer operator->() const {
        return &(current->value);
    }

    // 前置++
    MyListIterator& operator++() {
        current = current->next;
        return *this;
    }

    // 后置++
    MyListIterator operator++(int) {
        MyListIterator tmp = *this;
        current = current->next;
        return tmp;
    }

    // 前置--
    MyListIterator& operator--() {
        current = current->prev;
        return *this;
    }

    // 后置--
    MyListIterator operator--(int) {
        MyListIterator tmp = *this;
        current = current->prev;
        return tmp;
    }

    // 相等/不等比较
    bool operator==(const MyListIterator& other) const {
        return current == other.current;
    }

    bool operator!=(const MyListIterator& other) const {
        return current != other.current;
    }

private:
    Node<T>* current;
};

// 自定义双向链表容器
template <typename T>
class MyList {
private:
    Node<T>* head;
    Node<T>* tail;
    size_t len;
public:
    MyList() : head(nullptr), tail(nullptr), len(0) {}

    ~MyList() {
        while (head) {
            Node<T>* tmp = head;
            head = head->next;
            delete tmp;
        }
    }

    void push_back(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        if (!tail) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        len++;
    }

    // 返回首尾迭代器
    MyListIterator<T> begin() {
        return MyListIterator<T>(head);
    }

    MyListIterator<T> end() {
        return MyListIterator<T>(nullptr);
    }

    size_t size() const { return len; }
};

int main() {
    MyList<int> list;
    list.push_back(3);
    list.push_back(1);
    list.push_back(4);
    list.push_back(2);

    // 1. 范围for遍历（自动调用begin/end）
    std::cout << "范围for遍历：";
    for (int x : list) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 2. 兼容STL标准算法
    int count = std::count_if(list.begin(), list.end(), [](int x) { return x > 2; });
    std::cout << "大于2的元素个数：" << count << std::endl;

    return 0;
}
```

### 关键说明

- 只要正确定义了`iterator_category`等 5 个内嵌类型，迭代器就能无缝适配所有 STL 算法；

- C\+\+20 引入了概念（Concept）来约束迭代器类型，代码更简洁，类型检查也更严格。

## 六、重要注意事项：迭代器失效

迭代器本质是指向容器内部元素的 “指示器”，当容器发生结构变化（插入、删除、扩容）时，部分或全部迭代器可能会失效，继续使用会导致未定义行为。

### 常见容器的迭代器失效规则

|容器|插入操作|删除操作|
|---|---|---|
|`vector`|尾插：触发扩容则所有迭代器失效；不扩容仅尾后迭代器失效|删除点之后的所有迭代器失效|
|`deque`|首尾插入：所有迭代器失效；中间插入：所有迭代器失效|首尾删除：仅被删元素迭代器失效；中间删除：所有迭代器失效|
|`list` / `set` / `map`|不会导致其他迭代器失效（仅被删元素自身失效）|仅被删除元素的迭代器失效|

### 安全遍历删除的正确写法

```cpp
// 错误写法：erase后it已失效，++it会触发未定义行为
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it == target) vec.erase(it);
}

// 正确写法：利用erase返回下一个有效迭代器
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it == target) {
        it = vec.erase(it);
    } else {
        ++it;
    }
}
```

## 七、适用场景

1. **需要遍历多种不同结构的容器**，希望客户端以统一的接口进行访问；

2. **需要隐藏容器的内部实现细节**，只对外暴露遍历能力，不暴露存储结构；

3. **需要为同一个容器提供多种遍历方式**（如正序、逆序、深度优先、广度优先）；

4. **需要遍历逻辑与容器业务逻辑解耦**，符合单一职责原则；

5. **泛型库设计**：需要编写通用算法，适配任意符合规范的容器。

## 八、优缺点分析

### 优点

1. **解耦性强**：遍历与存储完全分离，容器只负责数据管理，迭代器负责遍历逻辑；

2. **接口统一**：客户端用同一套代码可以遍历任意容器，降低学习成本和代码重复；

3. **扩展性好**：新增遍历方式只需新增迭代器，新增容器只需提供对应迭代器，互不影响；

4. **支持多遍历并存**：同一个容器可以同时存在多个独立的迭代器，各自维护遍历状态；

5. **支撑泛型编程**：STL 迭代器是标准库算法体系的基石，实现了算法与容器的完美解耦。

### 缺点

1. **增加代码复杂度**：每个容器都需要配套迭代器实现，一定程度增加了代码量；

2. **迭代器失效风险**：C\+\+ 中容器结构变化容易导致迭代器失效，使用不当容易引发难以排查的 bug；

3. 传统面向对象实现有虚函数开销：GoF 风格的迭代器有虚函数调用成本，STL 泛型实现无此问题。

## 九、与相似模式对比

|模式|类型|核心目的|关键区别|
|---|---|---|---|
|迭代器模式|行为型|遍历聚合对象的元素，隐藏内部结构|关注**顺序访问集合元素**，核心是遍历逻辑|
|访问者模式|行为型|对集合元素执行多种不同操作|关注**对元素执行操作**，依赖双分派机制|
|组合模式|结构型|统一处理单个对象和组合对象|常和迭代器配合，用迭代器遍历组合结构|
|工厂方法模式|创建型|封装对象创建过程|迭代器的创建通常使用工厂方法，容器作为工厂创建迭代器|

## 十、总结

迭代器模式的本质是**封装变化的遍历算法，提供一致的访问接口**，是处理集合遍历场景的标准方案。

- 面向对象设计中，使用 GoF 风格的继承式迭代器，适合多态遍历场景；

- 现代 C\+\+ 开发中，**STL 风格的泛型迭代器是绝对主流**，性能更高、兼容性更好，是编写自定义容器的标准做法。

迭代器模式已经深度融入 C\+\+ 语言和标准库，是每个 C\+\+ 开发者必须掌握的核心设计模式。理解迭代器模式，是深入理解 STL 设计思想、编写高质量泛型代码的基础。

需要我补充一个二叉树的深度优先 / 广度优先迭代器实现示例吗？

> （注：部分内容可能由 AI 生成）

<!-- markdown for nginx, see https://phus.lu -->
<script>
!function(){
	var dom = {
		element: null,
		get: function (o) {
			var obj = Object.create(this)
			obj.element = (typeof o == "object") ? o : document.createElement(o)
			return obj
		},
		add: function (o) {
			var obj = dom.get(o)
			this.element.appendChild(obj.element)
			return obj
		},
		text: function (t) {
			this.element.appendChild(document.createTextNode(t))
			return this
		},
		attr: function (k, v) {
			this.element.setAttribute(k, v)
			return this
		}
	}

	if (!document.head) return
	head = dom.get(document.head)
	head.add('meta').attr('charset', 'utf-8')
	head.add('meta').attr('name', 'viewport').attr('content', 'width=device-width,initial-scale=1')

	if (!document.body) {
		document.write(["<div class=\"container\">",
		"<h3>nginx.conf</h3>",
		"<textarea rows=6 cols=50>",
		"# download markdown.html to /wwwroot",
		"location ~ \\.md$ {",
		"    default_type text/html;",
		"    add_after_body /markdown.html;",
		"}",
		"</textarea>",
		"</div>"].join("\n"))
		return
	}

	var bodytext = document.body.innerHTML
	document.body.innerHTML = ''

	div = dom.get('div').attr('class', 'container')

	div.add('script').attr('src', 'https://cdnjs.cloudflare.com/ajax/libs/marked/0.5.2/marked.min.js').attr('integrity', 'sha256-zFUosuESzULu5P+SZdjRRtBZR8+1u5RZDlbt3Q5KL8U=').attr('crossorigin', 'anonymous')
	div.add('link').attr('rel', 'stylesheet').attr('href', 'https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/5.1.0/github-markdown-light.min.css').attr('integrity', 'sha256-WQx0Y6LLZeGv3V3NVVge+YIL5MIOt45RPuFdkyNodls=').attr('crossorigin', 'anonymous')

	title = decodeURIComponent(document.location.pathname.replace(/.*\//, '').replace(/\.html$/, ''))
	document.title = '《' + title.replace(/\.md$/, '') + '》'
	tbody = div.add('table').add('tbody')
	tbody.add('tr').add('th').text(title).attr('class', 'octicon-book')
	tbody.add('tr').add('td').add('div').attr('id', 'readme').attr('class', 'markdown-body')

	wait = function (name, callback) {
		var interval = 10; // ms
		window.setTimeout(function() {
			if (window[name]) {
				callback(window[name])
			} else {
				window.setTimeout(arguments.callee, interval)
			}
		}, interval)
	}
	wait('marked', function() {
		document.getElementById("readme").innerHTML = marked.parse(bodytext)
	})

	document.body.appendChild(div.element)
}()
</script>

<style>
body {
	margin: 0;
	font-family: "ubuntu", "Tahoma", "Microsoft YaHei", Arial, Serif;
}
.markdown-body {
	float: left;
	font-family: "ubuntu", "Tahoma", "Microsoft YaHei", Arial, Serif;
}
.container {
	padding-right: 15px;
	padding-left: 15px;
	margin-right: auto;
	margin-left: auto;
}
@media (min-width: 768px) {
	.container {
		max-width: 80%;
	}
}
@media (min-width: 992px) {
	.container {
		max-width: 70%;
	}
}
@media (min-width: 1200px) {
	.container {
		max-width: 60%;
	}
}
table {
	width: 100%;
	max-width: 100%;
	margin-bottom: 20px;
	border: 1px solid #ddd;
	padding: 0;
	border-collapse: collapse;
}
table th {
	font-size: 14px;
}
table tr {
	border: 1px solid #ddd;
	padding: 5px;
}
table th, table td {
	border: 1px solid #ddd;
	font-size: 14px;
	line-height: 20px;
	padding: 3px;
	text-align: left;
}
.octicon-book {
	background-position: center left;
	background-repeat: no-repeat;
	padding-left: 20px;
	background-image: url("data:image/svg+xml;charset=utf8,%3Csvg xmlns='http://www.w3.org/2000/svg' width='16' height='16' viewBox='0 0 16 16'%3E%3Cpath d='M3,5 L7,5 L7,6 L3,6 L3,5 L3,5 Z M3,8 L7,8 L7,7 L3,7 L3,8 L3,8 Z M3,10 L7,10 L7,9 L3,9 L3,10 L3,10 Z M14,5 L10,5 L10,6 L14,6 L14,5 L14,5 Z M14,7 L10,7 L10,8 L14,8 L14,7 L14,7 Z M14,9 L10,9 L10,10 L14,10 L14,9 L14,9 Z M16,3 L16,12 C16,12.55 15.55,13 15,13 L9.5,13 L8.5,14 L7.5,13 L2,13 C1.45,13 1,12.55 1,12 L1,3 C1,2.45 1.45,2 2,2 L7.5,2 L8.5,3 L9.5,2 L15,2 C15.55,2 16,2.45 16,3 L16,3 Z M8,3.5 L7.5,3 L2,3 L2,12 L8,12 L8,3.5 L8,3.5 Z M15,3 L9.5,3 L9,3.5 L9,12 L15,12 L15,3 L15,3 Z' /%3E%3C/svg%3E");
}
</style>