数据结构模式：Composite、Iterator、Chain of Responsibility

动机

在软件构建过程中，集合对象内部结构常常变化各异。但对于这些集合对象，我们希望在不暴露其内部结构的同时，可以让外部客户代码透明地访问其中包含的元素；同时这种“透明遍历”也为“同一种算法在多种集合对象上进行操作”提供了可能。

使用面向对象技术将这种遍历机制抽象为“迭代器对象”为“应对变化中的集合对象”提供了一种优雅的方式

模式定义

提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露（稳定）该对象的内部表示。——《设计模式》GoF

不暴露：就是隔离变化，让外界得以稳定

结构

image.png

【在C++语言中，基于模板的迭代器 性能优于 基于面向对象的迭代器】
GoF定义的迭代器模式是以面向对象的方式实现迭代器的。但这种方式在C++中已经过时了，在C++STL中也有迭代器，两者的思想是一样的，都是通过一种接口来隔离算法和容器之间的变化。

在泛型编程、STL面市之后（大概在98年），大家一对比，发现面向对象的方式有很多缺点，最大的缺点也正是在面向对象上

  1. 面向对象的核心是多态，多态的调用涉及到虚函数，虚函数调用是有性能成本的（是因为虚函数表，要经过二次的指针运算进行调用）
  2. 那每次使用迭代器方法时都要多态调用，而且是一个容器的循环。如果容器有10万个元素，那就调用10万次，每一次调用多一点性能开销，那10万次就差很多了

而泛型编程中的迭代器，是基于模板来描述的。而模板实际上也是一种多态技术，但模板实现的是编译式多态（编译器在编译的时候会辨析具体调用哪个代码）。但面向对象的虚函数是运行时多态，运行时多态性能会低于编译时多态，因为编译的时候已经把调用谁的工作做完了，运行时就直接调用对应的函数，不需要在计算它的函数地址了。

事实也证明，在工业界，在系统软件层面，有了泛型编程的迭代器，大家再也不用面向对象的迭代器了。
但在其他语言中，面向对象的迭代器还是得到了极大的应用。其他语言还是基于运行时多态，因为它们不支持编译式的多态。

【泛型编程的迭代器有很多种】泛型编程的迭代器发展出来了更多的可能性

  1. 有往前走，有往后走，甚至往前走n步，往后走n步。而面向对象只有一个方向，虽然也可以实现，但这个成本很高
  2. 五种迭代器：正向迭代器、双向迭代器、随机访问迭代器、输入迭代器、输出迭代器

代码：用面向对象的方式实现迭代器

  1. //抽象迭代器
  2. template<typename T>
  3. class Iterator
  4. {
  5. public:
  6.     virtual void first() = 0;
  7.     virtual void next() = 0;
  8.     virtual bool isDone() const = 0;
  9.     virtual T& current() = 0; //取当前元素
  10.     //注：有些类库会把next和current合二为一
  11.     //即virtual T& next() = 0;
  12. };
  14. //一个集合类
  15. template<typename T>
  16. class MyCollection{
  17. public:
  18.     //得到MyCollection的迭代器
  19.     Iterator<T> GetIterator(){
  20.         //...
  21.     }
  22. };
  24. //实现MyCollection的迭代器
  25. template<typename T>
  26. class CollectionIterator : public Iterator<T>{
  27.     MyCollection<T> mc;
  28. public:
  29.     CollectionIterator(const MyCollection<T> & c): mc(c){ }
  31.     void first() override {
  32.     }
  33.     void next() override {
  34.     }
  35.     bool isDone() const override{
  36.     }
  37.     T& current() override{
  38.     }
  39. };
  41. //具体使用时
  42. void MyAlgorithm()
  43. {
  44.     MyCollection<int> mc;
  46.     Iterator<int> iter= mc.GetIterator();
  48.     for (iter.first(); !iter.isDone(); iter.next()){
  49.         cout << iter.current() << endl;
  50.     }
  51. }

要点总结

要点一：迭代抽象

迭代抽象：访问一个聚合对象的内容，不需要暴露它的内部表示

说明：客户代码不需要关心容器内部是如何实现的，是链表、树状结构，还是堆，还是栈实现的，无所谓。

要点二：迭代多态

迭代多态：为遍历不同的集合结构提供一个统一的接口，从而支持同样的算法在不同集合结构上进行操作

要点三：迭代器的健壮性考虑

迭代器的健壮性考虑：遍历的同时要更改迭代器所在的集合结构，会导致问题

说明：如果在遍历的时候，你更改集合的结构（比如删除一个元素），可能会导致问题。很多迭代器要求是只读的，不允许修改。但迭代器指向的内容是可以改的，结构不允许改。