迭代器模式的核心目标是将集合对象的遍历逻辑与集合本身的结构解耦，让客户端无需了解集合内部实现就能完成元素访问。当需要实现多种遍历方式时，只需为集合提供不同遍历逻辑的迭代器实现即可，深度优先和广度优先遍历就是典型的多遍历场景。
迭代器模式的基础结构
标准的迭代器模式包含四个核心角色：抽象迭代器、具体迭代器、抽象集合、具体集合。抽象迭代器定义遍历的通用接口，具体迭代器实现具体的遍历逻辑，抽象集合定义创建迭代器的方法，具体集合返回对应遍历逻辑的迭代器实例。
我们先定义一个简单的树形结构集合作为示例，树节点包含值和子节点列表，后续基于这个集合实现两种遍历迭代器。
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <memory>
// 树节点定义
struct TreeNode {
int val;
std::vector<std::shared_ptr<TreeNode>> children;
TreeNode(int v) : val(v) {}
};
// 抽象迭代器接口
class TreeIterator {
public:
virtual ~TreeIterator() = default;
virtual bool hasNext() = 0;
virtual int next() = 0;
};
// 抽象集合接口
class TreeCollection {
public:
virtual ~TreeCollection() = default;
virtual std::unique_ptr<TreeIterator> createDFSIterator() = 0;
virtual std::unique_ptr<TreeIterator> createBFSIterator() = 0;
virtual std::shared_ptr<TreeNode> getRoot() = 0;
};
深度优先遍历迭代器实现
深度优先遍历（DFS）的核心是优先遍历当前节点的子节点，再遍历兄弟节点，通常使用栈来保存待访问的节点。具体迭代器内部维护一个栈结构，初始化时将根节点入栈，每次调用next()方法时弹出栈顶节点，同时将该节点的子节点逆序入栈，保证遍历顺序符合深度优先的逻辑。
// 深度优先遍历具体迭代器
class DFSIterator : public TreeIterator {
private:
std::stack<std::shared_ptr<TreeNode>> nodeStack;
public:
DFSIterator(std::shared_ptr<TreeNode> root) {
if (root) {
nodeStack.push(root);
}
}
bool hasNext() override {
return !nodeStack.empty();
}
int next() override {
if (!hasNext()) {
throw std::runtime_error("No more elements");
}
auto current = nodeStack.top();
nodeStack.pop();
// 逆序入栈子节点，保证先遍历第一个子节点
for (auto it = current->children.rbegin(); it != current->children.rend(); ++it) {
nodeStack.push(*it);
}
return current->val;
}
};
广度优先遍历迭代器实现
广度优先遍历（BFS）的核心是优先遍历同一层的节点，再遍历下一层节点，通常使用队列来保存待访问的节点。具体迭代器内部维护一个队列结构，初始化时将根节点入队，每次调用next()方法时弹出队首节点，同时将该节点的所有子节点按顺序入队，保证遍历顺序符合广度优先的逻辑。
// 广度优先遍历具体迭代器
class BFSIterator : public TreeIterator {
private:
std::queue<std::shared_ptr<TreeNode>> nodeQueue;
public:
BFSIterator(std::shared_ptr<TreeNode> root) {
if (root) {
nodeQueue.push(root);
}
}
bool hasNext() override {
return !nodeQueue.empty();
}
int next() override {
if (!hasNext()) {
throw std::runtime_error("No more elements");
}
auto current = nodeQueue.front();
nodeQueue.pop();
// 按顺序入队子节点，保证先遍历同一层节点
for (const auto& child : current->children) {
nodeQueue.push(child);
}
return current->val;
}
};
具体集合实现与使用示例
接下来实现具体的树集合类，实现抽象集合的接口，分别返回深度优先和广度优先的迭代器实例。然后构建一棵测试树，分别用两种迭代器遍历，验证实现的正确性。
// 具体树集合实现
class ConcreteTree : public TreeCollection {
private:
std::shared_ptr<TreeNode> root;
public:
ConcreteTree(std::shared_ptr<TreeNode> r) : root(r) {}
std::unique_ptr<TreeIterator> createDFSIterator() override {
return std::make_unique<DFSIterator>(root);
}
std::unique_ptr<TreeIterator> createBFSIterator() override {
return std::make_unique<BFSIterator>(root);
}
std::shared_ptr<TreeNode> getRoot() override {
return root;
}
};
int main() {
// 构建测试树
// 1
// / |
// 2 3 4
// /
// 5 6
auto root = std::make_shared<TreeNode>(1);
auto node2 = std::make_shared<TreeNode>(2);
auto node3 = std::make_shared<TreeNode>(3);
auto node4 = std::make_shared<TreeNode>(4);
auto node5 = std::make_shared<TreeNode>(5);
auto node6 = std::make_shared<TreeNode>(6);
root->children = {node2, node3, node4};
node2->children = {node5, node6};
ConcreteTree tree(root);
// 深度优先遍历
std::cout << "深度优先遍历结果: ";
auto dfsIter = tree.createDFSIterator();
while (dfsIter->hasNext()) {
std::cout << dfsIter->next() << " ";
}
std::cout << std::endl;
// 广度优先遍历
std::cout << "广度优先遍历结果: ";
auto bfsIter = tree.createBFSIterator();
while (bfsIter->hasNext()) {
std::cout << bfsIter->next() << " ";
}
std::cout << std::endl;
return 0;
}
实现要点总结
要让迭代器模式支持多种遍历，核心思路是为每种遍历逻辑实现独立的TreeIterator子类，不同子类的内部状态维护（栈或队列）和next()方法的逻辑根据遍历规则编写。集合类只需要提供创建不同迭代器的方法，客户端可以根据需求选择对应的迭代器，无需关心遍历的具体实现细节。
这种实现方式符合开闭原则，如果后续需要添加新的遍历方式，只需要新增迭代器子类，修改集合的创建方法即可，不需要改动原有遍历逻辑的代码。