【设计模式】迭代器模式和组合模式

本篇介绍了迭代器模式和组合模式及相关的面向对象设计原则。这两种模式都是面向数据结构的设计模式。

迭代器模式（Iterator）提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露其内部的表示。
组合模式（Composite）将对象组合成树形结构来表示“整体-部分”的层次关系，从而让客户对单个对象和组合对象的使用具有一致性。

1 迭代器模式

我们对迭代器的概念非常熟悉，许多情况下面对不同的对象集合，我们希望能有统一的方式遍历他们，但不对外暴露其内部的实现方式。比如 C++ 的 vector、list、map 等容器都支持迭代器，利用迭代器我们可以使用统一的方法，比如 first()、end()、next() 等，对不同集合的对象进行统一的操作。

迭代器模式的类图如下：

首先实现迭代器接口：

template<typename T>
class Iterator
{
public:
    virtual void first() = 0;
    virtual void next() = 0;
    virtual bool end() const = 0;
    virtual T& current() = 0;
};

然后实现一个和自己的元素容器，该容器需要有一个迭代器对象，并能够返回该迭代器：

template<typename T>
class MyCollection{
public: 
    Iterator<T> GetIterator(){
        // 提供当前容器的迭代器
    } 
};

然后实现我们容器的具体迭代器：

template<typename T>
class CollectionIterator : public Iterator<T>{
    MyCollection<T> mc;
public:
    CollectionIterator(const MyCollection<T> & c): mc(c) {}
   
    void first() override {
        // 指向第一个元素
    }
    void next() override {
        // 指向下一个元素
    }
    bool end() const override{
        // 是否指向最后一个元素
    }
    T& current() override{
        // 返回当前指向的元素
    }
};

最后调用时：

void MyAlgorithm()
{
    MyCollection<int> mc;
    Iterator<int> iter = mc.GetIterator();
    for (iter.first(); !iter.end(); iter.next()){
        cout << iter.current() << endl;
    }
}

迭代器模式把元素之间游走的责任交给迭代器去处理，这样一来元素容器本身就不需要关注如何处理对象的遍历，而是专注于对象的管理操作上。迭代器模式不仅让客户遍历不同的容器更加方便，也会让元素容器的接口更加简洁。

那么为什么不让元素容器本身去实现各自的遍历操作呢，因为一个类的每个责任都有发生变化的可能，容器管理对象是一个责任，负责对象的遍历和访问又是一个责任，责任越多，意味着未来发生变化的可能性越大，要修改的代码也就越多。因此迭代器模式引出了一个重要的设计原则：

设计原则：单一责任原则

一个类应该只有一个引起变化的原因，尽量让每个类保持单一责任。

2 组合模式

在一些情况下，对象内部的结构可能较为复杂，不再是单一的容器了。比如一个容器内部的每一个元素又是一个可以容纳多个对象的容器，此时使用迭代器模式就没有办法直接遍历这样的复杂结构了，因此需要使用组合模式。

组合模式将对象组合成树形结构来表示“整体-部分”的层次关系，从而让客户对单个对象和组合对象的使用具有一致性。上面的例子中，一级容器的每个元素相当于树的一个中间节点，节点包含二级容器中的各个元素，因此我们可以将这个树状结构构建出来，并让每一级容器中的元素都继承自同一个父类，这个父类被称为基本的组件（Component），这样在客户代码中就无需关注对象是叶子节点（单一对象）还是中间节点（组合对象）了，因为他们都有相同的接口。

组合模式的类图如下：

首先是实现 Component 接口：

class Component {
public:
    virtual void process() = 0;
    virtual ~Component() {}
};

然后实现叶子节点，叶子节点不包含其他子节点，只实现对应的操作：

// 叶子节点
class Leaf : public Component {
    string name;
public:
    Leaf(string s) : name(s) {}
            
    void process() {
        // process current node
    }
};

然后是中间节点，也就是组合对象，中间节点包含其他叶子节点，执行操作时就是先处理自身，然后遍历所有叶子节点，按顺序调用叶子节点的操作：

// 中间节点
class Composite : public Component {
    string name;
    list<Component*> elements;		// 包含的子节点集合，子节点可以是其他组合对象，也可以是叶子节点
public:
    Composite(const string & s) : name(s) {}
    // 组合对象还支持增加或删除节点的操作
    void add(Component* element) {
        elements.push_back(element);
    }
    void remove(Component* element) {
        elements.remove(element);
    }
    // 组合节点的操作就是处理自身，并依次调用叶子节点
    void process() {
        //1. process current node
        
        //2. process leaf nodes
        for (auto &e : elements)
            e->process();  // 递归多态调用
    }
};

然后为该对象的处理写一个统一的接口供客户代码使用：

void Invoke(Component & c){
    //...
    c.process();
    //...
}

然后写一个测试程序：

int main()
{
    // 构建对象关系
    Composite root("root");
    Composite treeNode1("treeNode1");
    Composite treeNode2("treeNode2");
    Composite treeNode3("treeNode3");
    Composite treeNode4("treeNode4");
    Leaf leat1("left1");
    Leaf leat2("left2");
    
    root.add(&treeNode1);
    treeNode1.add(&treeNode2);
    treeNode2.add(&leaf1);
    
    root.add(&treeNode3);
    treeNode3.add(&treeNode4);
    treeNode4.add(&leaf2);
    
    // 对组合对象和单一对象的调用是统一的
    Invoke(root);
    Invoke(leaf2);
    Invoke(treeNode3);  
}

同样，我们也可以结合组合模式和迭代器，实现组合迭代器，只要为每个组件加上一个迭代器对象，然后递归的遍历即可。之前在实现光线追踪时的 BVH 结构就是组合模式的典型例子，可以回顾一下【RayTracer】（十）实现 BVH。

组合模式采用树形结构来表达层次关系，将“一对多”的关系转变为“一对一”的关系，使客户代码可以一致的处理对象本身和对象容器，而无需关心处理的是单个对象还是组合对象。组合模式将客户代码和复杂的对象容器结构解耦，客户代码只与纯粹的抽象接口发生依赖，而不是具体的对象容器，从而更能应对变化。