设计模式·数据结构模式

 

Composite:通过树形结构组织多个对象,对外提供统一的接口 Iterator:迭代器对象 职责链:一个请求可以有多个对象响,将这些对象连接成一条链,由它自行决定谁来处理

  • Composite:通过树形结构组织多个对象,对外提供统一的接口
  • Iterator:迭代器对象
  • 职责链:一个请求可以有多个对象响,将这些对象连接成一条链,由它自行决定谁来处理

数据结构模式

  • 有一些组件在内部有特定的数据结构
    • 如果让客户依赖这些特定的数据结构
    • 会极大破坏组件的复用
  • 将这些特定的数据结构封装在内部
    • 对外提供统一的接口
    • 实现与特定数据结构无关的访问
    • 是解决方案
  • 典型模式
    • Composite
    • Iterator
    • Chain of Resposibility

Composite 模式

动机

  • 某些情况下,客户代码过多依赖对象内部复杂的实现结构
    • 对象内部结构的变化会引起客户的变化
    • 带来代码维护、扩展必的困难
  • 如何将客户与对象复杂的结构解耦?
    • 让对象自己来实现自身的复杂结构
    • 从而使客户像处理简单对象一样处理复杂的对象容器?

模式定义

  • 将对象组合成树形结构,以表示整体-部分的层次结构
  • Composite使得用户地单个对象和组合对象的使用具有一致性(稳定)

结构

模式实现

  • 基类

    class Component {
    public:
        virtual void process() = 0;
        virtual ~Component(){}
    };
    
  • 定义树形结构

    • 结点

      //树节点
      class Composite : public Component{
          string name;
          // 多态对象,既可以是Component结点也可以是Leaf叶子
          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(); //多态调用
          }
      };
      
    • 叶子结点

      class Leaf : public Component{
          string name;
      public:
          Leaf(string s) : name(s) {}
                      
          void process(){
              //process current node
          }
      };
      
  • 客户端

    • 一致性处理

      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);
              
          // 一致性地处理所有对象
          process(root);
          process(leaf2);
          process(treeNode3);
      }
      

要点总结

  • Composite模式采用树形结构来实现对象容器
    • 将“一对多”转换成“一对一”
      • 如果把process()中的第2步去掉
      • Invoke()就必须对Leaf和Node两种情况分别进行处理
      • 就使Invoke()一对多种情况
      • 加上之后,Invoke()就是用e.process()一对一处理所有情况
    • 使得客户代码可以一致地(复用)处理对象和对象容器
    • 无需关心面对的是单一对象还是组合的对象容器
  • 将客户代码与对象容器解耦是Composite的核心思想
    • 解耦之后,客户代码只是纯粹的抽象接口发生依赖
      • 而非对象容器的内部实现
  • Composite在具体实现中
    • 可以让子对象反向追溯
    • 如果父对象有频繁的遍历需求
      • 可以使用缓存技巧来改善效率

Iterator 迭代器模式

动机

  • 软件构建过程中,集合对象内部结构常常变化各异
    • 如何让客户代码透明的访问其中的元素?
    • 这种透明遍历又可以为同一种算法在多种集合对象上进行操作提供可能
  • 将这种遍历机制抽象为“迭代器对象”
    • 为应对变化中的集合对象提供了优雅的方式

模式定义

提供一种方法,顺序访问集合中的各个元素,而又不暴露(稳定)该对象的内部表示

结构

模式实现

  • 迭代器类

    template<typename T>
    class Iterator {
    public:
        virtual void first() = 0;
        virtual void next() = 0;
        virtual bool isDone() const = 0;
        virtual T& current() = 0;
    };
    
  • 自已的对象集合

    template<typename T>
    class MyCollection{
    public:
        Iterator<T> GetIterator(){
            //...
        }
    };
    
    class CollectionIterator : public Iterator<T>{
    
        MyCollection<T> mc;
    
    public:
        // 需要把自定义的集合传进来
        CollectionIterator(const MyCollection<T> & c): mc(c){ }
          
        void first() override { ... }
        void next() override { ... }
        bool isDone() const override{ ... }
        T& current() override{ ... }
    };
    

    返回一个迭代器

  • 使用

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

    • 以类的方式得到的迭代器,iter是4个虚函数
    • 每次虚函数调用有性能成本
      • 运行时多态
      • 运行时计算函数地址
    • cpp使用模板(泛型),是编译时多态

要点总结

  • 迭代抽象
    • 访问一个聚合对象中的内容,而无需暴露它的内部表示
  • 迭代多态
    • 为遍历不同的合集结构提供一个统一的接口
    • 从而让同样的算法在不同的集合结构上进行操作
  • 迭代器的健壮性考虑
    • 遍历的同时,更改迭代器的内部结构,会导致问题

职责链

  • 在软件构建过程中
    • 一个请求可能被多个对象处理
    • 但每个请求在运行中只能有一个接受者
    • 如果显示指定
      • 会带来请求者与接受者之间的耦合
  • 如果使请求者不需要指定具体的接受者?
    • 让接受者自己在运行时决定处理请求

模式定义

  • 使多个对象都有机会处理请求
    • 从而避免请求的发送者与接收者之间的耦合关系
  • 将这些对象连接成一条链
    • 并沿着这条链传递请求
    • 直到有一个对象处理它为止

结构

模式现实

  • 请求类型

    enum class RequestType {
      REQ_HANDLER1,
      REQ_HANDLER2,
      REQ_HANDLER3,
    };
    
  • 请求类

    class Request {
      string description;
      RequesetType reqType;
    public:
      Request(const string &desc, RequestType type) { return reqType;}
      const string& getDescription() const {return description;}
    };
    
  • 职责链

    class ChainHandler {
      ChainHandler *nextChain;
      void sendRequestToNextHandler(const Request &req) {
        if (nextChain != nullptr)
          nextChain->handler(req);
      }
    protected:
      virtual bool canHandlerRequest(const Request &req) = 0;
      virtual void processRequest(const Request &req) = 0;
    public:
      ChainHandler() {nextChain = nullptr;}
      void setNextChain(ChainHandler *next) {nextChain = next;}
    
      void handle(const Request &req) {
        if (canHandleRequest(req))
          processRequest(req);
        else
          sendRequestToNextHandler(req);
      }
    }
    
  • 处理

    class Handler1: public ChainHandler {
    protected:
      bool canHandleRequest(const Request &req) override {
        return req.getReqType() == RequestType::REQ_HANDLER1;
      }
      void processRequest(const Request &req) override {
        cout << "Handler1 is handle request: " << req.getDescription << endl;
      }
    }
    
    class Handler2: public ChainHandler {
    protected:
      bool canHandleRequest(const Request &req) override {
        return req.getReqType() == RequestType::REQ_HANDLER2;
      }
      void processRequest(const Request &req) override {
        cout << "Handler2 is handle request: " << req.getDescription << endl;
      }
    }
    
    class Handler3: public ChainHandler {
    protected:
      bool canHandleRequest(const Request &req) override {
        return req.getReqType() == RequestType::REQ_HANDLER3;
      }
      void processRequest(const Request &req) override {
        cout << "Handler3 is handle request: " << req.getDescription << endl;
      }
    }
    
  • 使用

    int main() {
      Handler1 h1;
      Handler2 h2;
      Handler3 h3;
      h1.setNextChain(&h2);
      h2.setNextChain(&h3);
    
      Request req("process task ...", RequestType::REQ_HANDLER3);
      h1.handle(req);
      return 0;
    }
    

要点总结

  • 职责链模式的应用场合
    • 一个请求可以有多个接受者
    • 但最后真正的接受者只能有一个
  • 可以在运行时动态添加/修改请求的处理职责
  • 如果请求传递到职责链的末尾还没有处理
    • 应该有一个合理的处理机制