d2 range 和 标准C++中的Iterator（迭代器）简介

原文： http://hi.baidu.com/crash1/blog/item/90269a088a8000d562d986b3.html

只引用标准C++中的Iterator（迭代器）的介绍，关于d range 的介绍请参阅相关文章，是否一一对应或相关区别，请高手点评 

d2 range 相关参考：
D2 的 range设计http://dolive.iteye.com/blog/373077
std.range （2.030）http://dolive.iteye.com/blog/372383

标准C++中的Iterator（迭代器）简介
2007-12-23 22:42

一、概述
Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

由于Iterator模式的以上特性：与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。

根据STL中的分类，iterator包括：
1、Input Iterator：只能单步向前迭代元素，不允许修改由该类迭代器引用的元素。
2、Output Iterator：该类迭代器和Input Iterator极其相似，也只能单步向前迭代元素，不同的是该类迭代器对元素只有写的权力。

3、Forward Iterator：该类迭代器可以在一个正确的区间中进行读写操作，它拥有Input Iterator的所有特性，和Output Iterator的部分特性，以及单步向前迭代元素的能力。

4、Bidirectional Iterator：该类迭代器是在Forward Iterator的基础上提供了单步向后迭代元素的能力。

5、Random Access Iterator：该类迭代器能完成上面所有迭代器的工作，它自己独有的特性就是可以像指针那样进行算术计算，而不是仅仅只有单步向前或向后迭代。

这五类迭代器的从属关系，如下图所示，其中箭头A→B表示，A是B的强化类型，这也说明了如果一个算法要求B，那么A也可以应用于其中。

图1、五种迭代器之间的关系
vector 和deque提供的是RandomAccessIterator，list提供的是BidirectionalIterator，set和map提供的 iterators是 ForwardIterator，关于STL中iterator的更多信息，请阅读参考1或2。

二、结构
Iterator模式的结构如下图所示：

图2、Iterator模式类图示意

三、应用
Iterator模式有三个重要的作用：
1）它支持以不同的方式遍历一个聚合 复杂的聚合可用多种方式进行遍历，如二叉树的遍历，可以采用前序、中序或后序遍历。迭代器模式使得改变遍历算法变得很容易: 仅需用一个不同的迭代器的实例代替原先的实例即可，你也可以自己定义迭代器的子类以支持新的遍历，或者可以在遍历中增加一些逻辑，如有条件的遍历等。

2）迭代器简化了聚合的接口 有了迭代器的遍历接口，聚合本身就不再需要类似的遍历接口了，这样就简化了聚合的接口。

3）在同一个聚合上可以有多个遍历 每个迭代器保持它自己的遍历状态，因此你可以同时进行多个遍历。

4）此外，Iterator模式可以为遍历不同的聚合结构（需拥有相同的基类）提供一个统一的接口，即支持多态迭代。

简 单说来，迭代器模式也是Delegate原则的一个应用，它将对集合进行遍历的功能封装成独立的Iterator，不但简化了集合的接口，也使得修改、增 加遍历方式变得简单。从这一点讲，该模式与Bridge模式、Strategy模式有一定的相似性，但Iterator模式所讨论的问题与集合密切相关， 造成在Iterator在实现上具有一定的特殊性，具体将在示例部分进行讨论。

四、优缺点
正如前面所说，与集合密切相关，限制了 Iterator模式的广泛使用，就个人而言，我不大认同将Iterator作为模式提出的观点，但它又确实符合模式“经常出现的特定问题的解决方案”的 特质，以至于我又不得不承认它是个模式。在一般的底层集合支持类中，我们往往不愿“避轻就重”将集合设计成集合 + Iterator 的形式，而是将遍历的功能直接交由集合完成，以免犯了“过度设计”的诟病，但是，如果我们的集合类确实需要支持多种遍历方式（仅此一点仍不一定需要考虑 Iterator模式，直接交由集合完成往往更方便），或者，为了与系统提供或使用的其它机制，如STL算法，保持一致时，Iterator模式才值得考 虑。

五、举例
可以考虑使用两种方式来实现Iterator模式：内嵌类或者友元类。通常迭代类需访问集合类中的内部数据结构，为此，可在集合类中设置迭代类为friend class，但这不利于添加新的迭代类，因为需要修改集合类，添加friend class语句。也可以在抽象迭代类中定义protected型的存取集合类内部数据的函数，这样迭代子类就可以访问集合类数据了，这种方式比较容易添加新的迭代方式，但这种方式也存在明显的缺点：这些函数只能用于特定聚合类，并且，不可避免造成代码更加复杂。

STL的list::iterator、deque::iterator、rbtree::iterator等采用的都是外部Iterator类的形式，虽然STL的集合类的iterator分散在各个集合类中，但由于各Iterator类具有相同的基类，保持了相同的对外的接口（包括一些traits及tags等，感兴趣者请认真阅读参考1、2），从而使得它们看起来仍然像一个整体，同时也使得应用algorithm成为可能。我们如果要扩展STL的iterator，也需要注意这一点，否则，我们扩展的iterator将可能无法应用于各algorithm。

以下是一个遍历二叉树的Iterator的例子，为了方便支持多种遍历方式，并便于遍历方式的扩展，其中还使用了Strategy模式（见笔记21）：

（注：1、虽然下面这个示例是本系列所有示例中花费我时间最多的一个，但我不得不承认，它非常不完善，感兴趣的朋友，可以考虑参考下面的参考材料将其补充完善，或提出宝贵改进意见。2、 我本想考虑将其封装成与STL风格一致的形式，使得我们遍历二叉树必须通过Iterator来进行，但由于二叉树在结构上较线性存储结构复杂，使访问必须 通过Iterator来进行，但这不可避免使得BinaryTree的访问变得异常麻烦，在具体应用中还需要认真考虑。3、以下只提供了Inorder<中序>遍历iterator的实现。）


c++迭代器相关参考：http://www.songxiaolong.com/articles/c%E8%BF%AD%E4%BB%A3%E5%99%A8%E7%AE%80%E4%BB%8B.html
http://www.cppreference.com/wiki/cn/iterator/start
http://tech.ddvip.com/2009-06/1243930851122051.html
http://blogold.chinaunix.net/u2/87718/showart_1981101.html
http://blog.csdn.net/arthurhebe/archive/2010/01/30/5273678.aspx

http://docs.google.com/viewer?a=v&q=cache:lzsy897q04QJ:jpkc.ntu.edu.cn/kecheng/jsj/paper/C%2B%2B%2520STL%25E8%25BF%25AD%25E4%25BB%25A3%25E5%2599%25A8%25E6%259C%25BA%25E5%2588%25B6%25E5%2589%2596%25E6%259E%2590.pdf+c%2B%2B+%E8%BF%AD%E4%BB%A3%E5%99%A8&hl=zh-CN&pid=bl&srcid=ADGEESgmhqySIe1gcoYn4sifpkl58b2xFVa2LXa6gBCCHugY6HBw4HEdaKf5NDxBY9LslO-EfrgHdHMQcfu-VBQDmPWV9A1QgmD-DWmQg7Iw3_xkVOyVR7Yj57wBXibbJFchsFserB5z&sig=AHIEtbQw6AM0MYETnUIWR4qhkcpd7NbCWA&pli=1