迭代器模式与几个经典的C++实现
迭代器模式详解
1. 定义与意图
迭代器模式（Iterator Pattern） 是一种行为设计模式，它提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露该对象的内部表示。
主要意图：
为不同的聚合结构提供统一的遍历接口。
将遍历数据的职责与聚合对象本身分离，简化聚合接口。
支持以不同方式遍历同一个聚合（如前序、中序、后序遍历二叉树）。
2. 模式结构
迭代器模式包含以下几个角色：
Iterator（迭代器接口）：定义访问和遍历元素的接口。
ConcreteIterator（具体迭代器）：实现迭代器接口，跟踪遍历的当前位置。
Aggregate（聚合接口）：定义创建相应迭代器对象的接口。
ConcreteAggregate（具体聚合）：实现创建相应迭代器的接口，返回具体迭代器的实例。
3. 适用场景
需要访问聚合对象的内容而不暴露其内部表示
支持对聚合对象的多种遍历方式
为遍历不同的聚合结构提供统一的接口
4. 优点
单一职责原则：将遍历算法与聚合对象分离
开闭原则：可以引入新的迭代器而不修改现有代码
可以并行遍历同一聚合，因为每个迭代器都有自己的状态
可以暂停遍历并在需要时继续
5. 缺点
对于简单的集合可能过于复杂
某些情况下，使用专门的遍历方法可能比迭代器更高效
C++ 实现例子
例子1：自定义数组容器的迭代器
#include <iostream>
#include <stdexcept>template <typename T, size_t SIZE>
class Array {
private:T data[SIZE];public:// 迭代器类class Iterator {private:T* ptr;public:explicit Iterator(T* p) : ptr(p) {}// 前置++Iterator& operator++() {++ptr;return *this;}// 后置++Iterator operator++(int) {Iterator temp = *this;++ptr;return temp;}T& operator*() const {return *ptr;}T* operator->() const {return ptr;}bool operator==(const Iterator& other) const {return ptr == other.ptr;}bool operator!=(const Iterator& other) const {return !(*this == other);}};// const迭代器类class ConstIterator {private:const T* ptr;public:explicit ConstIterator(const T* p) : ptr(p) {}ConstIterator& operator++() {++ptr;return *this;}ConstIterator operator++(int) {ConstIterator temp = *this;++ptr;return temp;}const T& operator*() const {return *ptr;}const T* operator->() const {return ptr;}bool operator==(const ConstIterator& other) const {return ptr == other.ptr;}bool operator!=(const ConstIterator& other) const {return !(*this == other);}};// 获取开始迭代器Iterator begin() {return Iterator(data);}Iterator end() {return Iterator(data + SIZE);}ConstIterator begin() const {return ConstIterator(data);}ConstIterator end() const {return ConstIterator(data + SIZE);}ConstIterator cbegin() const {return ConstIterator(data);}ConstIterator cend() const {return ConstIterator(data + SIZE);}T& operator[](size_t index) {if (index >= SIZE) {throw std::out_of_range("Index out of range");}return data[index];}const T& operator[](size_t index) const {if (index >= SIZE) {throw std::out_of_range("Index out of range");}return data[index];}size_t size() const {return SIZE;}
};// 使用示例
int main() {Array<int, 5> arr = {1, 2, 3, 4, 5};// 使用迭代器遍历std::cout << "Using iterator: ";for (auto it = arr.begin(); it != arr.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 使用范围for循环（基于迭代器）std::cout << "Using range-based for: ";for (const auto& item : arr) {std::cout << item << " ";}std::cout << std::endl;return 0;
}例子2：二叉树的中序遍历迭代器
#include <iostream>
#include <stack>
#include <memory>template <typename T>
struct TreeNode {T value;std::shared_ptr<TreeNode> left;std::shared_ptr<TreeNode> right;TreeNode(T val) : value(val), left(nullptr), right(nullptr) {}
};template <typename T>
class BinaryTree {
private:std::shared_ptr<TreeNode<T>> root;public:BinaryTree() : root(nullptr) {}void setRoot(std::shared_ptr<TreeNode<T>> node) {root = node;}// 中序遍历迭代器class InOrderIterator {private:std::stack<std::shared_ptr<TreeNode<T>>> stack;std::shared_ptr<TreeNode<T>> current;void pushLeft(std::shared_ptr<TreeNode<T>> node) {while (node) {stack.push(node);node = node->left;}}public:explicit InOrderIterator(std::shared_ptr<TreeNode<T>> root) {current = nullptr;pushLeft(root);if (!stack.empty()) {current = stack.top();stack.pop();}}T& operator*() const {return current->value;}InOrderIterator& operator++() {if (current->right) {pushLeft(current->right);}if (stack.empty()) {current = nullptr;} else {current = stack.top();stack.pop();}return *this;}bool operator!=(const InOrderIterator& other) const {return current != other.current;}bool hasNext() const {return current != nullptr;}};InOrderIterator begin() {return InOrderIterator(root);}InOrderIterator end() {return InOrderIterator(nullptr);}
};// 使用示例
int main() {// 创建二叉树: // 1// / \// 2 3// / \// 4 5auto root = std::make_shared<TreeNode<int>>(1);root->left = std::make_shared<TreeNode<int>>(2);root->right = std::make_shared<TreeNode<int>>(3);root->left->left = std::make_shared<TreeNode<int>>(4);root->left->right = std::make_shared<TreeNode<int>>(5);BinaryTree<int> tree;tree.setRoot(root);std::cout << "In-order traversal: ";for (auto it = tree.begin(); it.hasNext(); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}例子3：STL风格的迭代器适配器
#include <iostream>
#include <vector>
#include <iterator>// 过滤迭代器：只返回满足条件的元素
template <typename Iterator, typename Predicate>
class FilterIterator {
private:Iterator current;Iterator end;Predicate predicate;void advanceToNextValid() {while (current != end && !predicate(*current)) {++current;}}public:FilterIterator(Iterator begin, Iterator end, Predicate pred): current(begin), end(end), predicate(pred) {advanceToNextValid();}FilterIterator& operator++() {if (current != end) {++current;advanceToNextValid();}return *this;}typename std::iterator_traits<Iterator>::value_type operator*() const {return *current;}bool operator!=(const FilterIterator& other) const {return current != other.current;}bool operator==(const FilterIterator& other) const {return current == other.current;}
};// 辅助函数创建过滤迭代器
template <typename Iterator, typename Predicate>
FilterIterator<Iterator, Predicate> make_filter_iterator(Iterator begin, Iterator end, Predicate pred) {return FilterIterator<Iterator, Predicate>(begin, end, pred);
}int main() {std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};// 定义谓词：只返回偶数auto isEven = [](int n) { return n % 2 == 0; };std::cout << "Even numbers: ";auto begin = make_filter_iterator(numbers.begin(), numbers.end(), isEven);auto end = make_filter_iterator(numbers.end(), numbers.end(), isEven);for (auto it = begin; it != end; ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}例子4：支持多种遍历方式的集合
#include <iostream>
#include <vector>
#include <algorithm>template <typename T>
class CustomCollection {
private:std::vector<T> data;public:void add(const T& item) {data.push_back(item);}// 前向迭代器class ForwardIterator {private:typename std::vector<T>::iterator it;public:explicit ForwardIterator(typename std::vector<T>::iterator iter) : it(iter) {}ForwardIterator& operator++() {++it;return *this;}T& operator*() const {return *it;}bool operator!=(const ForwardIterator& other) const {return it != other.it;}};// 反向迭代器class ReverseIterator {private:typename std::vector<T>::reverse_iterator it;public:explicit ReverseIterator(typename std::vector<T>::reverse_iterator iter) : it(iter) {}ReverseIterator& operator++() {++it;return *this;}T& operator*() const {return *it;}bool operator!=(const ReverseIterator& other) const {return it != other.it;}};ForwardIterator begin() {return ForwardIterator(data.begin());}ForwardIterator end() {return ForwardIterator(data.end());}ReverseIterator rbegin() {return ReverseIterator(data.rbegin());}ReverseIterator rend() {return ReverseIterator(data.rend());}
};int main() {CustomCollection<int> collection;for (int i = 1; i <= 5; ++i) {collection.add(i);}std::cout << "Forward: ";for (auto it = collection.begin(); it != collection.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;std::cout << "Reverse: ";for (auto it = collection.rbegin(); it != collection.rend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}总结
迭代器模式是C++中非常重要的设计模式，它：
提供统一的遍历接口：无论底层数据结构如何，都能使用相同的方式遍历
支持多种遍历算法：可以根据需要实现不同的遍历策略
符合开闭原则：添加新的遍历方式不需要修改现有代码
与STL完美集成：C++标准库大量使用迭代器模式
在实际开发中，迭代器模式常用于：
自定义容器的实现
复杂数据结构的遍历
数据过滤和转换操作
提供与STL算法兼容的接口