【C++设计模式】第十六篇：迭代器模式（Iterator）

注意：复现代码时，确保 VS2022 使用 C++17/20 标准以支持现代特性。

遍历聚合对象的统一方式

1. 模式定义与用途

核心思想

• ​迭代器模式：提供一种方法顺序访问聚合对象的元素，而无需暴露其内部表示。
• 关键用途：
  1.​统一遍历接口：为不同数据结构（如数组、链表、树）提供一致的遍历方式。
  ​2.支持多种遍历策略：前向、反向、条件过滤等。
  ​3.简化聚合类设计：将遍历逻辑从聚合类中分离。

经典场景

• STL容器的迭代器（如std::vector::iterator）。
• 自定义集合类（如链表、图）的遍历。
• 数据库查询结果的逐行遍历。

2. 模式结构解析

UML类图

+---------------------+          +---------------------+  
|      Aggregate      |          |       Iterator       |  
+---------------------+          +---------------------+  
| + createIterator()  |<>------->| + next(): void       |  
+---------------------+          | + hasNext(): bool    |  
          ^                      +---------------------+  
          |                                ^  
          |                                |  
  +-------+-------+              +---------+---------+  
  |               |              |                   |  
+---------------------+    +-------------------+ +----------------+  
| ConcreteAggregate   |    |  ConcreteIterator | |     Client      |  
+---------------------+    +-------------------+ +----------------+  
| + createIterator()  |    | + next()          | | 通过迭代器遍历聚合对象 |  
+---------------------+    | + hasNext()       | +----------------+  
                           +-------------------+  

角色说明

1. Aggregate：聚合接口，定义创建迭代器的方法（如createIterator()）。
2. ​ConcreteAggregate：具体聚合类，实现迭代器创建逻辑。
3. Iterator：迭代器接口，定义遍历方法（如next()、hasNext()）。
4. ConcreteIterator：具体迭代器，实现特定遍历逻辑。
5. Client：通过迭代器访问聚合对象，无需依赖其内部结构。

3. 现代C++实现示例

场景：自定义链表迭代器

步骤1：定义链表节点与聚合类

#include <iostream>  
#include <memory>  

template <typename T>  
class ListNode {  
public:  
    T value;  
    std::shared_ptr<ListNode<T>> next;  
    ListNode(T val) : value(val), next(nullptr) {}  
};  

// 聚合类：单向链表  
template <typename T>  
class LinkedList {  
public:  
    void append(T value) {  
        auto newNode = std::make_shared<ListNode<T>>(value);  
        if (!head_) {  
            head_ = newNode;  
        } else {  
            tail_->next = newNode;  
        }  
        tail_ = newNode;  
    }  

    // 创建正向迭代器  
    class Iterator;  
    Iterator begin() { return Iterator(head_); }  
    Iterator end() { return Iterator(nullptr); }  

private:  
    std::shared_ptr<ListNode<T>> head_ = nullptr;  
    std::shared_ptr<ListNode<T>> tail_ = nullptr;  
};  

步骤2：实现迭代器类

template <typename T>  
class LinkedList<T>::Iterator {  
public:  
    Iterator(std::shared_ptr<ListNode<T>> node) : current_(node) {}  

    T& operator*() const { return current_->value; }  
    Iterator& operator++() {  
        if (current_) current_ = current_->next;  
        return *this;  
    }  
    bool operator!=(const Iterator& other) const {  
        return current_ != other.current_;  
    }  

private:  
    std::shared_ptr<ListNode<T>> current_;  
};  

步骤3：客户端代码

int main() {  
    LinkedList<int> list;  
    list.append(1);  
    list.append(2);  
    list.append(3);  

    // 使用范围for循环（依赖begin()和end()）  
    for (auto num : list) {  
        std::cout << num << " ";  // 输出：1 2 3  
    }  

    // 手动迭代  
    auto it = list.begin();  
    while (it != list.end()) {  
        std::cout << *it << " ";  
        ++it;  
    }  
}  

扩展：反向迭代器

template <typename T>  
class LinkedList<T>::ReverseIterator {  
public:  
    ReverseIterator(std::shared_ptr<ListNode<T>> head) {  
        // 遍历链表，将节点指针存入栈以实现反向  
        auto curr = head;  
        while (curr) {  
            stack_.push(curr);  
            curr = curr->next;  
        }  
    }  

    T& operator*() { return stack_.top()->value; }  
    ReverseIterator& operator++() {  
        if (!stack_.empty()) stack_.pop();  
        return *this;  
    }  
    bool operator!=(const ReverseIterator& other) {  
        return !stack_.empty() || !other.stack_.empty();  
    }  

private:  
    std::stack<std::shared_ptr<ListNode<T>>> stack_;  
};  

4. 应用场景示例

场景1：树结构的深度优先遍历

class TreeNode {  
public:  
    int value;  
    std::vector<std::shared_ptr<TreeNode>> children;  
};  

class DepthFirstIterator {  
public:  
    DepthFirstIterator(std::shared_ptr<TreeNode> root) {  
        stack_.push(root);  
    }  

    std::shared_ptr<TreeNode> next() {  
        auto node = stack_.top();  
        stack_.pop();  
        for (auto it = node->children.rbegin(); it != node->children.rend(); ++it) {  
            stack_.push(*it);  
        }  
        return node;  
    }  

    bool hasNext() { return !stack_.empty(); }  

private:  
    std::stack<std::shared_ptr<TreeNode>> stack_;  
};  

场景2：过滤迭代器（条件遍历）

template <typename T, typename Predicate>  
class FilterIterator {  
public:  
    FilterIterator(typename LinkedList<T>::Iterator it, Predicate pred)  
        : it_(it), pred_(pred) {  
        // 找到第一个满足条件的元素  
        while (it_ != end_ && !pred_(*it_)) ++it_;  
    }  

    T& operator*() { return *it_; }  
    FilterIterator& operator++() {  
        do { ++it_; } while (it_ != end_ && !pred_(*it_));  
        return *this;  
    }  
    bool operator!=(const FilterIterator& other) { return it_ != other.it_; }  

private:  
    typename LinkedList<T>::Iterator it_;  
    typename LinkedList<T>::Iterator end_;  
    Predicate pred_;  
};  

// 使用示例：遍历链表中的偶数  
auto isEven = [](int x) { return x % 2 == 0; };  
FilterIterator<int, decltype(isEven)> begin(list.begin(), isEven);  
FilterIterator<int, decltype(isEven)> end(list.end(), isEven);  
while (begin != end) {  
    std::cout << *begin << " ";  
    ++begin;  
}  

5. 优缺点分析

6. 调试与优化策略

调试技巧（VS2022）​

1.​验证迭代器有效性：

• 在迭代器越界时触发断言：

T& operator*() {  
    assert(current_ != nullptr && "迭代器越界！");  
    return current_->value;  
}  

2. ​检查迭代器状态：

• 在operator++()中设置断点，观察指针移动是否符合预期。

性能优化

1. 预计算遍历路径：

• 对树或图的遍历，预计算路径并缓存结果（如广度优先遍历队列）。

2. 内存连续性优化：

• 使用std::vector存储节点，利用内存局部性提升遍历速度。