迭代器模式通过将遍历逻辑封装到独立的迭代器类中，使同一容器支持多种遍历方式。1. 定义统一接口iterator，包含hasnext()和next()方法；2. 实现dfsiterator使用栈实现深度优先遍历；3. 实现bfsiterator使用队列实现广度优先遍历；4. 容器类tree根据参数返回对应的迭代器实例；5. 用户通过统一接口操作不同遍历方式，无需关心内部实现细节。这种方式提高了代码可扩展性和维护性，同时降低了容器与遍历逻辑的耦合度。
在C++中，迭代器模式支持多种遍历方式（比如深度优先和广度优先），关键在于将不同的遍历逻辑封装到不同的迭代器类中。这样做的好处是使用者不需要关心底层结构如何遍历，只需要通过统一的接口操作即可。
下面我们就来看看，怎么用迭代器来实现这两种常见的遍历方式。
什么是迭代器模式
迭代器模式的核心思想是将遍历逻辑从容器中抽离出来，交给专门的迭代器对象处理。这样做的优势在于：
立即学习“C++免费学习笔记（深入）”；
- 容器不负责具体遍历方式
- 同一个容器可以有多个不同行为的迭代器
- 遍历逻辑可扩展、易维护
在C++中，我们通常定义一个公共的迭代器基类或接口（如Iterator），然后为每种遍历方式提供具体实现（如DFSIterator, BFSIterator）。
如何设计支持多种遍历的迭代器接口
为了支持深度优先（DFS）和广度优先（BFS），我们需要先设计一个通用的迭代器接口。基本功能包括：
class Iterator {
public:
virtual bool hasNext() = 0;
virtual int next() = 0;
};然后针对不同遍历策略分别实现：
深度优先遍历（DFS）
适用于树形结构，比如二叉树。可以用栈来模拟递归：
class DFSIterator : public Iterator {
private:
std::stack<Node*> stack_;
public:
DFSIterator(Node* root) {
if (root) stack_.push(root);
}
bool hasNext() override {
return !stack_.empty();
}
int next() override {
Node* node = stack_.top();
stack_.pop();
// 假设是二叉树，先压右后压左，保证左子树先访问
if (node->right) stack_.push(node->right);
if (node->left) stack_.push(node->left);
return node->value;
}
};广度优先遍历（BFS）
适用于图或者树的层序遍历，通常使用队列实现：
class BFSIterator : public Iterator {
private:
std::queue<Node*> queue_;
public:
BFSIterator(Node* root) {
if (root) queue_.push(root);
}
bool hasNext() override {
return !queue_.empty();
}
int next() override {
Node* node = queue.front();
queue.pop();
// 将子节点加入队列（如果是图，要加访问标记）
for (Node* child : node->children) {
if (child) queue_.push(child);
}
return node->value;
}
};这两个类都实现了相同的接口，但内部遍历顺序完全不同。
怎样在容器中选择不同的迭代器
假设我们有一个树结构的容器类，我们可以根据需要返回不同的迭代器实例：
class Tree {
private:
Node* root_;
public:
Tree(Node* root) : root_(root) {}
std::unique_ptr<Iterator> createIterator(const std::string& type) {
if (type == "dfs") {
return std::make_unique<DFSIterator>(root_);
} else if (type == "bfs") {
return std::make_unique<BFSIterator>(root_);
}
return nullptr;
}
};用户使用时：
Tree tree(root);
auto it = tree.createIterator("dfs");
while (it->hasNext()) {
std::cout << it->next() << " ";
}实现细节上的几个注意事项
- 如果是图结构，做BFS/DFS时记得记录已访问节点，防止重复访问。
- 迭代器最好用智能指针管理生命周期，避免内存泄漏。
- 接口设计尽量保持简单，只暴露
hasNext()和next()两个方法。 - 可以考虑用模板泛化支持不同类型的数据结构。
基本上就这些了。用迭代器支持多种遍历方式其实并不复杂，但需要注意把遍历逻辑和数据结构分离清楚，才能真正发挥出模式的优势。
