悠悠楠杉
网站页面
C++迭代器模式实现多维度遍历的艺术：深度优先与广度优先的优雅融合
07/12
迭代器模式本质剖析
迭代器模式（Iterator Pattern） 提供了一种方法顺序访问聚合对象的元素，而又不暴露其底层表示。这种解耦带来的灵活性，让我们能够：
- 支持多种遍历方式
- 简化聚合接口
- 实现并行遍历
cpp
template<typename T>
class Iterator {
public:
virtual ~Iterator() = default;
virtual T next() = 0;
virtual bool hasNext() const = 0;
};
深度优先迭代器实现
深度优先搜索（DFS）适合层级数据的完整路径探索，比如文档的标题树结构：
cpp
class DepthFirstIterator : public Iterator
std::stack<DocumentNode*> stack;
public:
explicit DepthFirstIterator(DocumentNode* root) {
if(root) stack.push(root);
}
DocumentNode* next() override {
auto current = stack.top();
stack.pop();
for(auto it = current->children.rbegin();
it != current->children.rend(); ++it) {
stack.push(*it);
}
return current;
}
bool hasNext() const override {
return !stack.empty();
}
};
关键技术点：
- 使用栈结构实现后进先出
- 反向压栈保证正常顺序
- 惰性求值避免内存浪费
广度优先迭代器设计
广度优先（BFS）更适合平级内容扫描，如关键词的同级扩展：
cpp
class BreadthFirstIterator : public Iterator
std::queue<DocumentNode*> queue;
public:
explicit BreadthFirstIterator(DocumentNode* root) {
if(root) queue.push(root);
}
DocumentNode* next() override {
auto current = queue.front();
queue.pop();
for(auto& child : current->children) {
queue.push(child);
}
return current;
}
bool hasNext() const override {
return !queue.empty();
}
};
设计差异：
- 队列实现先进先出
- 自然形成层级扩散
- 适合最短路径类需求
多维度遍历的统一接口
通过策略模式组合迭代器，实现灵活的策略切换：
cpp
class DocumentTraverser {
std::unique_ptr<Iterator
public:
enum TraversalType { DFS, BFS };
void setTraversalStrategy(TraversalType type, DocumentNode* root) {
switch(type) {
case DFS:
iterator = std::make_unique<DepthFirstIterator>(root);
break;
case BFS:
iterator = std::make_unique<BbreadthFirstIterator>(root);
break;
}
}
void traverse(std::function<void(DocumentNode*)> visit) {
while(iterator->hasNext()) {
visit(iterator->next());
}
}
};
实际应用场景示例
在文档处理系统中，不同场景需要不同遍历策略：
全文生成：深度优先保证内容连贯性
cpp traverser.setTraversalStrategy(DocumentTraverser::DFS, root); traverser.traverse([](auto node){ cout << node->content << endl; });关键词提取：广度优先获取同级重要信息
cpp traverser.setTraversalStrategy(DocumentTraverser::BFS, root); traverser.traverse([](auto node){ if(node->isKeyword) { keywords.push_back(node->text); } });
性能优化与注意事项
内存管理：
- 使用智能指针避免内存泄漏
- 考虑迭代器失效问题
线程安全：
- 迭代过程加锁
- 或返回元素副本
扩展性：
- 预留自定义过滤接口
- 支持中断机制
cpp
class SafeIterator : public Iterator<DocumentNode> {
std::mutex mtx;
//... 线程安全实现
};
结语：模式背后的哲学
迭代器模式的价值不仅在于技术实现，更体现了"单一责任"和"开闭原则"的设计哲学。通过将遍历算法与数据结构解耦，我们获得的是适应需求变化的弹性架构。当面对下一个复杂数据系统时，不妨思考：迭代器是否能将复杂变为优雅？
"优秀的架构就像好的导游，带你遍历所有景点，却不会让你迷失在细节中。" —— 匿名程序员
