当前位置： 首页 > article >正文

C++软件设计模式之迭代器模式

article 2025/1/7 13:06:06

迭代器模式是一种行为设计模式，它允许你顺序访问一个聚合对象的元素，而不暴露其底层表示。在C++软件设计中，迭代器模式的主要目的是将数据的遍历行为与数据结构本身分离，使得数据结构的修改不会影响到遍历代码。

目的和意图

  1. 解耦遍历与数据结构：迭代器模式使得遍历算法独立于数据结构的实现。这意味着你可以改变数据结构的内部表示，而不需要修改遍历代码。

  2. 提供统一的访问接口：无论底层数据结构如何，迭代器都提供了一套统一的接口来访问元素，使得客户端代码更加简洁和易读。

  3. 支持多种遍历方式：通过实现不同的迭代器，可以支持对同一数据结构的不同遍历方式，例如前序遍历、中序遍历、后序遍历等。

普通树数据结构叶节点访问迭代器的C++示例代码

下面是一个简单的C++示例，展示了如何为一棵普通树数据结构实现一个叶节点访问迭代器。

首先，定义树节点的结构：

#include <vector>
#include <iostream>

struct TreeNode {
    int value;
    std::vector<TreeNode*> children;

    TreeNode(int val) : value(val) {}
};

接下来，定义一个迭代器类，用于遍历树的叶节点：

class LeafIterator {
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = TreeNode;
    using difference_type = std::ptrdiff_t;
    using pointer = TreeNode*;
    using reference = TreeNode&;

    LeafIterator(TreeNode* node = nullptr) : current_(node) {}

    reference operator*() const {
        return *current_;
    }

    pointer operator->() const {
        return current_;
    }

    LeafIterator& operator++() {
        // Move to the next leaf node
        if (current_ == nullptr) {
            return *this;
        }

        // Find the next leaf node
        while (!stack_.empty() || current_->children.size() > 0) {
            if (current_->children.size() > 0) {
                stack_.push_back(current_);
                current_ = current_->children[0];
            } else {
                // Found a leaf node
                break;
            }
        }

        if (current_ != nullptr && current_->children.empty()) {
            // Move to the next leaf
            while (!stack_.empty()) {
                TreeNode* parent = stack_.back();
                stack_.pop_back();

                size_t child_index = findChildIndex(parent, current_);
                if (child_index + 1 < parent->children.size()) {
                    current_ = parent->children[child_index + 1];
                    break;
                }
                current_ = parent;
            }
        }

        return *this;
    }

    LeafIterator operator++(int) {
        LeafIterator temp = *this;
        ++(*this);
        return temp;
    }

    friend bool operator==(const LeafIterator& lhs, const LeafIterator& rhs) {
        return lhs.current_ == rhs.current_;
    }

    friend bool operator!=(const LeafIterator& lhs, const LeafIterator& rhs) {
        return !(lhs == rhs);
    }

private:
    TreeNode* current_;
    std::vector<TreeNode*> stack_;

    size_t findChildIndex(TreeNode* parent, TreeNode* child) {
        for (size_t i = 0; i < parent->children.size(); ++i) {
            if (parent->children[i] == child) {
                return i;
            }
        }
        return parent->children.size();
    }
};

现在，我们可以创建一个树，并使用叶节点迭代器来遍历叶节点：

int main() {
    // Build a simple tree
    TreeNode* root = new TreeNode(1);
    root->children.push_back(new TreeNode(2));
    root->children.push_back(new TreeNode(3));
    root->children[0]->children.push_back(new TreeNode(4));
    root->children[0]->children.push_back(new TreeNode(5));
    root->children[1]->children.push_back(new TreeNode(6));

    // Create iterators
    LeafIterator begin(root);
    LeafIterator end(nullptr);

    // Iterate through leaf nodes
    for (LeafIterator it = begin; it != end; ++it) {
        std::cout << (*it).value << std::endl;
    }

    // Clean up
    // Note: Proper deletion of tree nodes is needed but omitted for brevity

    return 0;
}

在这个示例中，LeafIterator 类实现了对树的叶节点的前序遍历。迭代器维护一个栈来跟踪遍历路径，并在每次递增操作时找到下一个叶节点。通过这种方式，我们可以轻松地遍历树的叶节点，而不需要关心树的内部结构。

迭代器模式是一种非常通用的设计模式，它能够与其他设计模式结合使用，以增强系统的灵活性、可维护性以及代码的可复用性。以下是一些常见的迭代器模式与其他模式结合使用的情况：

1. 迭代器模式与组合模式（Composite Pattern）

组合模式用于递归地表示树形结构，其中叶子节点和组合节点（有子节点的节点）具有一致的接口。迭代器模式可以与组合模式结合，用于遍历这些树形结构。

结合使用场景：
  • 统一接口：组合模式使得所有节点（无论是叶子节点还是组合节点）都具有相同的接口。迭代器模式可以提供一个统一的接口来遍历这些节点。
  • 递归遍历：迭代器模式可以用于递归地遍历树形结构，无论是前序遍历、中序遍历还是后序遍历。
示例：

在前面的示例中，我们已经展示了如何为树结构（组合模式）实现一个叶节点访问迭代器。这里的关键点是，组合模式的节点结构允许我们递归地遍历整个树。

2. 迭代器模式与工厂模式（Factory Pattern）

工厂模式用于创建对象，而迭代器模式用于遍历对象。结合这两种模式，可以创建不同类型的迭代器来遍历不同的数据结构。

结合使用场景：
  • 动态选择迭代器：工厂模式可以用于创建不同类型的迭代器（例如前序迭代器、中序迭代器、后序迭代器等），而客户端代码只需要使用工厂创建迭代器，而不需要关心迭代器的具体实现。
  • 扩展性：如果需要添加新的迭代器类型，只需在工厂中添加新的迭代器创建逻辑，而不需要修改客户端代码。
示例：

假设我们需要为不同的遍历方式创建不同的迭代器，可以使用工厂模式来创建这些迭代器。

class IteratorFactory {
public:
    virtual LeafIterator* createIterator(TreeNode* root) = 0;
};

class PreOrderIteratorFactory : public IteratorFactory {
public:
    LeafIterator* createIterator(TreeNode* root) override {
        return new PreOrderIterator(root);
    }
};

class PostOrderIteratorFactory : public IteratorFactory {
public:
    LeafIterator* createIterator(TreeNode* root) override {
        return new PostOrderIterator(root);
    }
};

// Usage
IteratorFactory* factory = new PreOrderIteratorFactory();
LeafIterator* iterator = factory->createIterator(root);

3. 迭代器模式与访问者模式（Visitor Pattern）

访问者模式用于在不修改现有对象结构的情况下，为对象结构中的元素添加功能。迭代器模式可以与访问者模式结合，用于遍历对象结构并应用访问者逻辑。

结合使用场景：
  • 动态扩展功能：访问者模式允许在不修改对象结构的情况下，为对象结构中的元素添加新的操作。迭代器模式可以用于遍历对象结构，并在遍历过程中调用访问者逻辑。
  • 分离遍历与操作：迭代器负责遍历对象结构，而访问者负责对遍历到的元素进行操作。
示例：

假设我们有一个树结构，并且希望在不修改树节点的情况下，为节点添加一些额外的操作（例如打印节点值）。

class Visitor {
public:
    virtual void visit(TreeNode* node) = 0;
};

class PrintVisitor : public Visitor {
public:
    void visit(TreeNode* node) override {
        std::cout << node->value << std::endl;
    }
};

class LeafIteratorWithVisitor {
public:
    LeafIteratorWithVisitor(TreeNode* node, Visitor* visitor) : current_(node), visitor_(visitor) {}

    void traverse() {
        if (current_ == nullptr) return;

        for (TreeNode* child : current_->children) {
            traverse(child);
        }

        if (current_->children.empty()) {
            visitor_->visit(current_);
        }
    }

private:
    TreeNode* current_;
    Visitor* visitor_;
};

// Usage
Visitor* visitor = new PrintVisitor();
LeafIteratorWithVisitor iterator(root, visitor);
iterator.traverse();

4. 迭代器模式与观察者模式（Observer Pattern）

观察者模式用于在对象状态发生变化时，通知一组观察者。迭代器模式可以与观察者模式结合，用于遍历一组观察者并通知它们。

结合使用场景：
  • 动态通知观察者：当对象状态发生变化时，迭代器模式可以用于遍历所有观察者，并通知它们状态变化。
  • 解耦通知逻辑：迭代器负责遍历观察者列表，而通知逻辑由观察者自己实现。
示例：

假设我们有一个发布者对象，它维护一个观察者列表，并在状态变化时通知所有观察者。

class Observer {
public:
    virtual void update() = 0;
};

class Subject {
public:
    void addObserver(Observer* observer) {
        observers_.push_back(observer);
    }

    void notifyObservers() {
        for (Observer* observer : observers_) {
            observer->update();
        }
    }

private:
    std::vector<Observer*> observers_;
};

// Usage
Subject subject;
Observer* observer1 = new ConcreteObserver();
Observer* observer2 = new ConcreteObserver();

subject.addObserver(observer1);
subject.addObserver(observer2);

subject.notifyObservers();

5. 迭代器模式与责任链模式（Chain of Responsibility Pattern）

责任链模式用于将请求沿着处理链传递，直到有一个处理者处理该请求。迭代器模式可以与责任链模式结合，用于遍历处理链。

结合使用场景：
  • 动态处理请求：迭代器模式可以用于遍历责任链中的各个处理者，并依次尝试处理请求。
  • 分离遍历与处理逻辑：迭代器负责遍历处理链，而处理逻辑由处理者自己实现。
示例：

假设我们有一个请求需要通过多个处理者进行处理，直到有一个处理者处理成功。

class Handler {
public:
    virtual void handleRequest(Request* request) = 0;
    void setNext(Handler* next) {
        next_ = next;
    }

protected:
    Handler* next_ = nullptr;
};

class ConcreteHandler1 : public Handler {
public:
    void handleRequest(Request* request) override {
        if (canHandle(request)) {
            // Handle the request
        } else if (next_) {
            next_->handleRequest(request);
        }
    }

    bool canHandle(Request* request) {
        // Determine if this handler can handle the request
    }
};

// Usage
Handler* handler1 = new ConcreteHandler1();
Handler* handler2 = new ConcreteHandler2();

handler1->setNext(handler2);

handler1->handleRequest(new Request());

总结

迭代器模式可以与其他设计模式结合使用，以增强系统的灵活性和可扩展性。以下是一些常见的结合场景：

  1. 与组合模式：用于遍历树形结构。
  2. 与工厂模式：用于动态选择和创建迭代器。
  3. 与访问者模式：用于在遍历过程中应用额外的操作。
  4. 与观察者模式：用于通知观察者列表。
  5. 与责任链模式：用于遍历处理链并处理请求。

通过结合这些模式，可以构建更加灵活、可维护和可扩展的系统。


http://www.kler.cn/a/467750.html

相关文章：

  • 欧科云链研究院：ChatGPT 眼中的 Web3
  • 【信号滤波 (补充)】二阶陷波滤波代码推导过程(C++)
  • (已开源-AAAI25) RCTrans：雷达相机融合3D目标检测模型
  • 汇编环境搭建
  • 初学vue3心得
  • 【openwrt】OpenWrt 路由器的 802.1X 动态 VLAN
  • es 3期 第20节-运用指标聚合快速统计数值
  • 面向对象分析与设计Python版 面向对象的核心特征
  • 功能篇：表单提交，multiple-data方式提交文件，后端接收方式
  • HTML——75. 内联框架
  • Jetpack Compose 学习笔记（三）—— 状态
  • 第一节：电路连接【51单片机+A4988+步进电机教程】
  • C++11编译器优化以及引用折叠
  • 加密算法分类与介绍：保障信息安全的核心技术
  • 【Leetcode】731. 我的日程安排表 II
  • 大麦抢票科技狠活
  • 【WPF】 数据绑定机制之INotifyPropertyChanged
  • 【华为OD-E卷 - 网上商城优惠活动 100分（python、java、c++、js、c）】
  • Huawei LiteOS 开发指南
  • AWS 申请证书、配置load balancer、配置域名
  • springboot3 redis 批量删除特定的 key 或带有特定前缀的 key
  • 我用AI学Android Jetpack Compose之入门篇（2）
  • 044_小驰私房菜_MTK平台Camera关闭多帧
  • 金融租赁系统的创新与发展推动行业效率提升
  • 使用python调用翻译大模型实现本地翻译【exe客户端版】
  • c#2025/1/4 周六