iterator百度百科

求助编辑百科名片 iterator 迭代器（Iterator）模式，又叫做游标（Cursor）模式。GOF给出的定义为：提供一种方法访问一个容器（contai ner）对象中各个元素，而又不需暴露该对象的内部细节。 从定义可见，迭代器模式是为容器而生。很明显，对 容器对象的访问必然涉及到遍历算法。你可以一股脑的将遍历方法塞到容器对象中去；或者根本不去提供什么遍 历算法，让使用容器的人自己去实现去吧。这两种情况好像都能够解决问题。 编辑本段 编辑本段 引言 迭代器模式(Iterator pattern) 迭代这个名词对于熟悉Java的人来说绝对不陌生。我们常常使用JDK提供的迭代接口进行java collection的遍历 ： Iterator it = list.iterator(); while(it.hasNext()){ //using “it.next();”do some businesss logic } 而这就是关于迭代器模式应用很好的例子。 定义与结构 然而在前一种情况，容器承受了过多的功能，它不仅要负责自己“容器”内的元素维护（添加、删除等等），而且 还要提供遍历自身的接口；而且由于遍历状态保存的问题，不能对同一个容器对象同时进行多个遍历。第二种方 式倒是省事，却又将容器的内部细节暴露无遗。 而迭代器模式的出现，很好的解决了上面两种情况的弊端。先来看下迭代器模式的真面目吧。 迭代器模式由以下角色组成： 1) 迭代器角色（Iterator）：迭代器角色负责定义访问和遍历元素的接口。 2) 具体迭代器角色（Concrete Iterator）：具体迭代器角色要实现迭代器接口，并要记录遍历中的当前位置。 3) 容器角色（Container）：容器角色负责提供创建具体迭代器角色的接口。 4) 具体容器角色（Concrete Container）：具体容器角色实现创建具体迭代器角色的接口——这个具体迭代器角 色与该容器的结构相关。 迭代器模式的类图如下： 从结构上可以看出，迭代器模式在客户与容器之间加入了迭代器角色。迭代器角色的加入，就可以很好的避免容 器内部细节的暴露，而且也使得符合“单一职责原则”。 注意，在迭代器模式中，具体迭代器角色和具体容器角色是耦合在一起的——遍历算法是与容器的内部细节紧密 相关的。为了使客户程序从与具体迭代器角色耦合的困境中脱离出来，避免具体迭代器角色的更换给客户程序带 目录 引言 定义与结构 举例 实现自己的迭代器 适用情况 标准C++中的Iterator（迭代器）简介 展开 编辑本段 来的修改，迭代器模式抽象了具体迭代器角色，使得客户程序更具一般性和重用性。这被称为多态迭代。 举例 由于迭代器模式本身的比较松散，所以具体实现也就五花八门。我们在此仅举一例，根本不能将实现方式一 一呈现。因此在举例前，我们先来列举下迭代器模式的实现方式。 1．迭代器角色定义了遍历的接口，但是没有规定由谁来控制迭代。在Java collection的应用中，是由客户程序来 控制遍历的进程，被称为外部迭代器；还有一种实现方式便是由迭代器自身来控制迭代，被称为内部迭代器。外 部迭代器要比内部迭代器灵活、强大，而且内部迭代器在java语言环境中，可用性很弱。 2．在迭代器模式中没有规定谁来实现遍历算法。好像理所当然的要在迭代器角色中实现。因为既便于一个容器 上使用不同的遍历算法，也便于将一种遍历算法应用于不同的容器。但是这样就破坏掉了容器的封装——容器角 色就要公开自己的私有属性，在java中便意味着向其他类公开了自己的私有属性。 那我们把它放到容器角色里来实现好了。这样迭代器角色就被架空为仅仅存放一个遍历当前位置的功能。但是遍 历算法便和特定的容器紧紧绑在一起了。 而在Java Collection的应用中，提供的具体迭代器角色是定义在容器角色中的内部类。这样便保护了容器的封装 。但是同时容器也提供了遍历算法接口，你可以扩展自己的迭代器。 好了，我们来看下Java Collection中的迭代器是怎么实现的吧。 //迭代器角色，仅仅定义了遍历接口 public interface Iterator { boolean hasNext(); Object next(); void remove(); } //容器角色，这里以List为例。它也仅仅是一个接口，就不罗列出来了 //具体容器角色，便是实现了List接口的ArrayList等类。为了突出重点这里指罗列和迭代器相关的内容 //具体迭代器角色，它是以内部类的形式出来的。AbstractList是为了将各个具体容器角色的公共部分提取出来而 存在的。 public abstract class AbstractList extends AbstractCollection implements List { …… //这个便是负责创建具体迭代器角色的工厂方法 public Iterator iterator() { return new Itr(); } //作为内部类的具体迭代器角色 private class Itr implements Iterator { int cursor = 0; int lastRet = -1; int expectedModCount = modCount; public boolean hasNext() { return cursor != size(); 编辑本段 } public Object next() { checkForComodification(); try { Object next = get(cursor); lastRet = cursor++; return next; } catch(IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } public void remove() { if (lastRet == -1) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.remove(lastRet); if (lastRet < cursor) cursor--; lastRet = -1; expectedModCount = modCount; } catch(IndexOutOfBoundsException e) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } 至于迭代器模式的使用。正如引言中所列那样，客户程序要先得到具体容器角色，然后再通过具体容器角色得到 具体迭代器角色。这样便可以使用具体迭代器角色来遍历容器了…… 实现自己的迭代器 在实现自己的迭代器的时候，一般要操作的容器有支持的接口才可以。而且我们还要注意以下问题： 在迭代器遍历的过程中，通过该迭代器进行容器元素的增减操作是否安全呢？ 编辑本段 编辑本段 在容器中存在复合对象的情况，迭代器怎样才能支持深层遍历和多种遍历呢？ 以上两个问题对于不同结构的容器角色，各不相同，值得考虑。 适用情况 由上面的讲述，我们可以看出迭代器模式给容器的应用带来以下好处： 1) 支持以不同的方式遍历一个容器角色。根据实现方式的不同，效果上会有差别。 2) 简化了容器的接口。但是在java Collection中为了提高可扩展性，容器还是提供了遍历的接口。 3) 对同一个容器对象，可以同时进行多个遍历。因为遍历状态是保存在每一个迭代器对象中的。 由此也能得出迭代器模式的适用范围： 1) 访问一个容器对象的内容而无需暴露它的内部表示。 2) 支持对容器对象的多种遍历。 3) 为遍历不同的容器结构提供一个统一的接口（多态迭代）。 标准C++中的Iterator（迭代器）简介 一、概述 Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不 需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该 模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的 各个元素。 由于Iterator模式的以上特性：与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类 ，如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。 根据STL中的分类，iterator包括： Input Iterator：只能单步向前迭代元素，不允许修改由该类迭代器引用的元素。 Output Iterator：该类迭代器和Input Iterator极其相似，也只能单步向前迭代元素，不同的是该类迭代器对元素 只有写的权力。 Forward Iterator：该类迭代器可以在一个正确的区间中进行读写操作，它拥有Input Iterator的所有特性，和Outp ut Iterator的部分特性，以及单步向前迭代元素的能力。 Bidirectional Iterator：该类迭代器是在Forward Iterator的基础上提供了单步向后迭代元素的能力。 Random Access Iterator：该类迭代器能完成上面所有迭代器的工作，它自己独有的特性就是可以像指针那样进 行算术计算，而不是仅仅只有单步向前或向后迭代。 vector 和deque提供的是RandomAccessIterator，list提供的是BidirectionalIterator，set和map提供的 iterators是 ForwardIterator，关于STL中iterator的更多信息，请阅读参考1或2。 二、应用 Iterator模式有三个重要的作用： 1）它支持以不同的方式遍历一个聚合 复杂的聚合可用多种方式进行遍历，如二叉树的遍历，可以采用前序、中 序或后序遍历。迭代器模式使得改变遍历算法变得很容易: 仅需用一个不同的迭代器的实例代替原先的实例即可 ，你也可以自己定义迭代器的子类以支持新的遍历，或者可以在遍历中增加一些逻辑，如有条件的遍历等。 2）迭代器简化了聚合的接口 有了迭代器的遍历接口，聚合本身就不再需要类似的遍历接口了，这样就简化了聚 合的接口。 3）在同一个聚合上可以有多个遍历 每个迭代器保持它自己的遍历状态，因此你可以同时进行多个遍历。 4）此外，Iterator模式可以为遍历不同的聚合结构（需拥有相同的基类）提供一个统一的接口，即支持多态迭代 。 简 单说来，迭代器模式也是Delegate原则的一个应用，它将对集合进行遍历的功能封装成独立的Iterator，不但 简化了集合的接口，也使得修改、增 加遍历方式变得简单。从这一点讲，该模式与Bridge模式、Strategy模式有 一定的相似性，但Iterator模式所讨论的问题与集合密切相关， 造成在Iterator在实现上具有一定的特殊性，具体 将在示例部分进行讨论。 三、优缺点 正如前面所说，与集合密切相关，限制了 Iterator模式的广泛使用，就个人而言，我不大认同将Iterator作为模式 提出的观点，但它又确实符合模式“经常出现的特定问题的解决”的 特质，以至于我又不得不承认它是个模式 。在一般的底层集合支持类中，我们往往不愿“避轻就重”将集合设计成集合 + Iterator 的形式，而是将遍历的功 能直接交由集合完成，以免犯了“过度设计”的诟病，但是，如果我们的集合类确实需要支持多种遍历方式（仅此 一点仍不一定需要考虑 Iterator模式，直接交由集合完成往往更方便），或者，为了与系统提供或使用的其它机 制，如STL算法，保持一致时，Iterator模式才值得考 虑。 四、举例 可以考虑使用两种方式来实现Iterator模式：内嵌类或者友元类。通常迭代类需访问集合类中的内部数据结构，为 此，可在集合类中设置迭代类为friend class，但这不利于添加新的迭代类，因为需要修改集合类，添加friend cla ss语句。也可以在抽象迭代类中定义protected型的存取集合类内部数据的函数，这样迭代子类就可以访问集合类 数据了，这种方式比较容易添加新的迭代方式，但这种方式也存在明显的缺点：这些函数只能用于特定聚合类， 并且，不可避免造成代码更加复杂。 STL的list::iterator、deque::iterator、rbtree::iterator等采用的都是外部Iterator类的形式，虽然STL的集合类的iter ator分散在各个集合类中，但由于各Iterator类具有相同的基类，保持了相同的对外的接口（包括一些traits及tags 等，感兴趣者请认真阅读参考1、2），从而使得它们看起来仍然像一个整体，同时也使得应用algorithm成为可能 。我们如果要扩展STL的iterator，也需要注意这一点，否则，我们扩展的iterator将可能无法应用于各algorithm。 以下是一个遍历二叉树的Iterator的例子，为了方便支持多种遍历方式，并便于遍历方式的扩展，其中还使用了St rategy模式（见笔记21）： （注：1、虽然下面这个示例是本系列所有示例中花费我时间最多的一个，但我不得不承认，它非常不完善，感 兴趣的朋友，可以考虑参考下面的参考材料将其补充完善，或提出宝贵改进意见。2、 我本想考虑将其封装成与 STL风格一致的形式，使得我们遍历二叉树必须通过Iterator来进行，但由于二叉树在结构上较线性存储结构复杂 ，使访问必须 通过Iterator来进行，但这不可避免使得BinaryTree的访问变得异常麻烦，在具体应用中还需要认 真考虑。3、以下只提供了Inorder<中序>遍历iterator的实现。） #include #include #include #include #include using namespace std; template class BinaryTree; template class Iterator; template class BinaryTreeNode { public: typedef BinaryTreeNode NODE; 1 2 扩展阅读： java核心技术 卷I http://www.java2000.net/f47 JAVA技术基础内容 开放分类： JAVA，Iterator 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 = item; } void setLeft(NODE_PTR ptr) { leftChild = ptr; ptr->setParent(this); } void setRight(NODE_PTR ptr) { rightChild = ptr; ptr->setParent(this); } void setParent(NODE_PTR ptr) { parent = ptr; } private: T data; NODE_PTR leftChild; NODE_PTR rightChild; NODE_PTR parent; // pointer to parent node, needed by iterator friend class BinaryTree; };