c++iterator百度讲解

编辑

迭代器模式(Iteratorpattern)

迭代这个名词对于熟悉Java的人来说绝对不陌生。我们常常使用JDK提供的迭代接口进行javacollection的遍历&＃xff1a;

Iterator it &＃61; list.iterator();

while(it.hasNext()){

//using “it.next();”do some businesss logic

}

而这就是关于迭代器模式应用很好的例子。

这也是迭代器最常用的方法。

编辑

然而在前一种情况&＃xff0c;容器承受了过多的功能&＃xff0c;它不仅要负责自己“容器”内的元素维护&＃xff08;添加、删除等等&＃xff09;&＃xff0c;而且还要提供遍历自身的接口&＃xff1b;而且由于遍历状态保存的问题&＃xff0c;不能对同一个容器对象同时进行多个遍历。第二种方式倒是省事&＃xff0c;却又将容器的内部细节暴露无遗。

而迭代器模式的出现&＃xff0c;很好的解决了上面两种情况的弊端。先来看下迭代器模式的真面目吧。

迭代器模式由以下角色组成&＃xff1a;

1) 迭代器角色&＃xff08;Iterator&＃xff09;&＃xff1a;迭代器角色负责定义访问和遍历元素的接口。

2) 具体迭代器角色&＃xff08;Concrete Iterator&＃xff09;&＃xff1a;具体迭代器角色要实现迭代器接口&＃xff0c;并要记录遍历中的当前位置。

3) 容器角色&＃xff08;Container&＃xff09;&＃xff1a;容器角色负责提供创建具体迭代器角色的接口。

4) 具体容器角色&＃xff08;Concrete Container&＃xff09;&＃xff1a;具体容器角色实现创建具体迭代器角色的接口——这个具体迭代器角色与该容器的结构相关。

迭代器模式的类图如下&＃xff1a;

从结构上可以看出&＃xff0c;迭代器模式在客户与容器之间加入了迭代器角色。迭代器角色的加入&＃xff0c;就可以很好的避免容器内部细节的暴露&＃xff0c;而且也使得设计符合“单一职责原则”。

注意&＃xff0c;在迭代器模式中&＃xff0c;具体迭代器角色和具体容器角色是耦合在一起的——遍历算法是与容器的内部细节紧密相关的。为了使客户程序从与具体迭代器角色耦合的困境中脱离出来&＃xff0c;避免具体迭代器角色的更换给客户程序带来的修改&＃xff0c;迭代器模式抽象了具体迭代器角色&＃xff0c;使得客户程序更具一般性和重用性。这被称为多态迭代。

编辑

在实现自己的迭代器的时候&＃xff0c;一般要操作的容器有支持的接口才可以。而且我们还要注意以下问题&＃xff1a;

在迭代器遍历的过程中&＃xff0c;通过该迭代器进行容器元素的增减操作是否安全呢&＃xff1f;

在容器中存在复合对象的情况&＃xff0c;迭代器怎样才能支持深层遍历和多种遍历呢&＃xff1f;

以上两个问题对于不同结构的容器角色&＃xff0c;各不相同&＃xff0c;值得考虑。

编辑

由上面的讲述&＃xff0c;我们可以看出迭代器模式给容器的应用带来以下好处&＃xff1a;

1) 支持以不同的方式遍历一个容器角色。根据实现方式的不同&＃xff0c;效果上会有差别。

2) 简化了容器的接口。但是在java Collection中为了提高可扩展性&＃xff0c;容器还是提供了遍历的接口。

3) 对同一个容器对象&＃xff0c;可以同时进行多个遍历。因为遍历状态是保存在每一个迭代器对象中的。

由此也能得出迭代器模式的适用范围&＃xff1a;

1) 访问一个容器对象的内容而无需暴露它的内部表示。

2) 支持对容器对象的多种遍历。

3) 为遍历不同的容器结构提供一个统一的接口&＃xff08;多态迭代&＃xff09;。

编辑

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

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

根据STL中的分类&＃xff0c;iterator包括&＃xff1a;

输入迭代器&＃xff08;Input Iterator&＃xff09;&＃xff1a;通过对输入迭代器解除引用&＃xff0c;它将引用对象&＃xff0c;而对象可能位于集合中。最严格的输入迭代只能以只读方式访问对象。 [1] 

输出迭代器&＃xff08;Output Iterator&＃xff09;&＃xff1a;该类迭代器和Input Iterator极其相似&＃xff0c;也只能单步向前迭代元素&＃xff0c;不同的是该类迭代器对元素只有写的权力。

以上两种基本迭代器可进一步分为三类&＃xff1a;

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

双向迭代器&＃xff08;Bidirectional Iterator&＃xff09;&＃xff1a;该类迭代器是在Forward Iterator的基础上提供了单步向后迭代元素的能力。

随机迭代器&＃xff08;Random Access Iterator&＃xff09;&＃xff1a;该类迭代器能完成上面所有迭代器的工作&＃xff0c;它自己独有的特性就是可以像指针那样进行算术计算&＃xff0c;而不是仅仅只有单步向前或向后迭代。

vector 和deque提供的是RandomAccessIterator&＃xff0c;list提供的是BidirectionalIterator&＃xff0c;set和map提供的 iterators是 ForwardIterator&＃xff0c;关于STL中iterator的更多信息&＃xff0c;请阅读参考1或2。

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

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

以下是一个遍历二叉树的Iterator的例子&＃xff0c;为了方便支持多种遍历方式&＃xff0c;并便于遍历方式的扩展&＃xff0c;其中还使用了Strategy模式&＃xff08;见笔记21&＃xff09;&＃xff1a;

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

#include

#include

#include

#include

#include

using namespace std;

template

class BinaryTree;

template

class Iterator;

template

class BinaryTreeNode

{

public:

typedef BinaryTreeNode NODE;

typedef BinaryTreeNode* NODE_PTR;

BinaryTreeNode(const T& element) : data(element), leftChild(NULL), rightChild(NULL), parent(NULL) { }

BinaryTreeNode(const T& element, NODE_PTR leftChild, NODE_PTR rightChild)

:data(element), leftChild(leftChild), rightChild(rightChild), parent(NULL)

{

if (leftChild)

leftChild->setParent(this);

if (rightChild)

rightChild->setParent(this);

}

T getData(void) const { return data; }

NODE_PTR getLeft(void) const { return leftChild; }

NODE_PTR getRight(void) const { return rightChild; }

NODE_PTR getParent(void) const { return parent; }

void SetData(const T& data) { this->data &＃61; item; }

void setLeft(NODE_PTR ptr) { leftChild &＃61; ptr; ptr->setParent(this); }

void setRight(NODE_PTR ptr) { rightChild &＃61; ptr; ptr->setParent(this); }

void setParent(NODE_PTR ptr) { parent &＃61; ptr; }

private:

T data;

NODE_PTR leftChild;

NODE_PTR rightChild;

NODE_PTR parent; // pointer to parent node, needed by iterator

friend class BinaryTree;

};