常州网站建站,网站备案地址,住房和城乡建设部网站行标,企业网站营销解决方案Iterator 迭代器也是属于“数据结构”模式。GoF中面向对象的迭代器已经过时#xff0c;C中目前使用泛型编程的方式实现#xff0c;其他语言还在使用面向对象的迭代器。 文章目录 1. 动机(Motivation)2. 模式定义3. Iterator 迭代器代码分析4. 面向对象的迭代器与泛型编程实现…Iterator 迭代器也是属于“数据结构”模式。GoF中面向对象的迭代器已经过时C中目前使用泛型编程的方式实现其他语言还在使用面向对象的迭代器。 文章目录 1. 动机(Motivation)2. 模式定义3. Iterator 迭代器代码分析4. 面向对象的迭代器与泛型编程实现的迭代器的对比5. 结构( Structure )6. 要点总结7. 其他参考 1. 动机(Motivation)
在软件构建过程中集合对象内部结构常常变化各异。但对于这些集合对象我们希望在不暴露其内部结构的同时可以让外部客户代码透明地访问其中包含的元素;同时这种“透明遍历”也为同一种算法在多种集合对象上进行操作”提供了可能。
不关心内部实现结构一种算法可以应用到树形结构也可以应用到链表、堆、栈的结构
使用面向对象技术将这种遍历机制抽象为“迭代器对象”为“应对变化中的集合对象”提供了一种优雅的方式。
2. 模式定义
提供一种方法顺序访问一个聚合对象中的各个元素而又不暴露(稳定)该对象的内部表示。
----《设计模式》GoF
GoF中最早提出面向对象对象的方式实现迭代器但是在讲面向对象的方式之前需要重点说一下这种方式在C今天来讲已经过时了因为学过STL泛型编程的都知道泛型编程中存在迭代器思想与今天所讲的是一样的都是通过一种接口的方式来隔离算法和容器之间的变化但是GoF当初定义是面向对象的方式来定义的。
3. Iterator 迭代器代码分析
整体代码
templatetypename T
class Iterator
{
public:virtual void first() 0;virtual void next() 0;virtual bool isDone() const 0;virtual T current() 0;
};templatetypename T
class MyCollection{public:IteratorT GetIterator(){//...}};templatetypename T
class CollectionIterator : public IteratorT{MyCollectionT mc;
public:CollectionIterator(const MyCollectionT c): mc(c){ }void first() override {}void next() override {}bool isDone() const override{}T current() override{}
};void MyAlgorithm()
{MyCollectionint mc;Iteratorint iter mc.GetIterator();for (iter.first(); !iter.isDone(); iter.next()){cout iter.current() endl;}}代码分析
首先来看GoF定义的代码面向对象的方式
templatetypename T
class Iterator
{
public:virtual void first() 0;virtual void next() 0;virtual bool isDone() const 0;virtual T current() 0;
};first()提供第一个元素next()是往下一个元素走isDone() 代表到头了T current()是取你当前的一组有些设计会将next()和T current()合二为一。
templatetypename T
class MyCollection{public:IteratorT GetIterator(){//...}};MyCollection是自己定义的集合会返回一个属于我这个集合的迭代器
templatetypename T
class CollectionIterator : public IteratorT{MyCollectionT mc;
public:CollectionIterator(const MyCollectionT c): mc(c){ }void first() override {}void next() override {}bool isDone() const override{}T current() override{}
};继承Iterator抽象类对纯虚函数进行实现一般实现的时候需要将集合传递进来CollectionIterator(const MyCollectionT c): mc(c){ }
到具体使用的时候
void MyAlgorithm()
{MyCollectionint mc; //塞一个类型Iteratorint iter mc.GetIterator(); //拿到迭代器//进行遍历操作for (iter.first(); !iter.isDone(); iter.next()){cout iter.current() endl;}}4. 面向对象的迭代器与泛型编程实现的迭代器的对比
当我们说到面向对象时多态是其特征。像刚才说这种面向对象的设计已经过时就因为泛型编程STL库在98年出来之后大家一对比发现面向对象的实现方式具有很多的缺点具体来说最核心的缺点就出在面向对象上面向对象的方式都是虚函数调用虚函数都是有性能成本的要绕虚表指针找到函数地址需要二次指针的间接运算每次都这样做当进行遍历操作时数据假如有10万个元素这个循环造成的成本就差了很多。 //进行遍历操作for (iter.first(); !iter.isDone(); iter.next()){cout iter.current() endl;}98年之后的C泛型编程中使用到的迭代器是使用模板来描述的而模板也是一种多态技术其实现的多态是编译式多态即编译器在编译的时候会遍析具体的源代码但是虚函数是运行时多态运行时多态性能要低于编译时多态因为编译时已经把工作做了运行时直接调用源代码不需要计算函数地址因此以STL为标准的泛型编程广泛使用的是基于模板的多态迭代器性能高于虚函数面向对象的迭代器。
而且第二个泛型编程里有很多种迭代器迭代器的接口发展出了更多的可能性上面的写法只支持往前走(next())不支持往回走(back())我们知道泛型编程里迭代器可以往前--往后走这些通过虚函数实现也可以但是成本很高。模板的灵活性基于隐式约束可以利用、–操作符做为接口描述面向对象只有虚函数一种。事实也证明有了泛型编程的迭代器大家再也不会用面向对象的迭代器。
但是上面所写的设计思路在其他语言比如javaC#等得等到了极大的应用(基于运行时的多态)其他语言不支持编译时的模板体制。
5. 结构( Structure ) 上图是《设计模式》GoF中定义的Iterator 迭代器的设计结构。结合上面的代码看图中对应关系如下图。 6. 要点总结 迭代抽象访问一个聚合对象的内容而无需暴露它的内部表示。 迭代多态为遍历不同的集合结构提供一个统一的接口从而支持同样的算法在不同的集合结构上进行操作。 迭代器的健壮性考虑遍历的同时更改迭代器所在的集合结构会导致问题。
7. 其他参考
C设计模式——迭代器模式
