第18章 迭代器模式

1、第第18章章 迭代器模式迭代器模式(ITERATOR)生活中的例子生活中的例子迭代迭代器模式定义器模式定义提供一种方法来访问提供一种方法来访问聚合对象聚合对象，而不用，而不用暴露这个对象的内部表示暴露这个对象的内部表示.聚合：指一组对象的组合结构，比如：聚合：指一组对象的组合结构，比如：Java中的集合、数组等中的集合、数组等迭代器模式迭代器模式针对不同的需要，可能还要针对不同的需要，可能还要以不同的方式以不同的方式遍历整个聚合对象遍历整个聚合对象，但，但并不希望在聚合对象并不希望在聚合对象的抽象层接口中充斥着各种不同遍历的操作的抽象层接口中充斥着各种不同遍历的操作怎样遍历一个聚合对象，又不需

2、要了解聚怎样遍历一个聚合对象，又不需要了解聚合对象的内部结构，还能够提供多种不同的合对象的内部结构，还能够提供多种不同的遍历方式，这就是遍历方式，这就是迭代器模式迭代器模式所要解决的问所要解决的问题。题。迭代迭代器模式动机器模式动机提供一个提供一个外部的迭代器外部的迭代器来对聚合对象进行来对聚合对象进行访问和遍历，迭代器定义了一个访问该聚访问和遍历，迭代器定义了一个访问该聚合元素的接口，并可以跟踪当前遍历的元合元素的接口，并可以跟踪当前遍历的元素，了解哪些元素已经遍历过。素，了解哪些元素已经遍历过。有了迭代器模式，对一个复杂的聚合对象有了迭代器模式，对一个复杂的聚合对象的操作会变得非常简单。的

3、操作会变得非常简单。迭代器模式迭代器模式UML类图类图 迭代器角色（迭代器角色（Iterator）：定义访问和遍历元素的：定义访问和遍历元素的接口接口 具体迭代器角色（具体迭代器角色（ConcreteIterator）：具体的迭）：具体的迭代器实现对象。实现对聚合对象的遍历，并跟踪遍代器实现对象。实现对聚合对象的遍历，并跟踪遍历时的当前位置。历时的当前位置。 聚合即集合或容器类聚合即集合或容器类 AbstractAggregate角色角色：定：定义创建相应迭代器对象的接口义创建相应迭代器对象的接口 具体聚合角色（具体聚合角色（Concrete Aggregate）：）：实现创建实现创建具体迭代

4、器角色的对象。它与该容器的结构相关。具体迭代器角色的对象。它与该容器的结构相关。 聚合类是用来存放数据的聚合类是用来存放数据的迭代器模式迭代器模式聚合是一个聚合是一个管理和组织数据对象管理和组织数据对象的数据结构的数据结构聚合对象主要拥有两个职责：一是聚合对象主要拥有两个职责：一是存储内部数据存储内部数据；二是二是遍历内部数据遍历内部数据 存储数据存储数据是聚合对象最基本的职责是聚合对象最基本的职责将将遍历聚合对象中数据的行为提取出来遍历聚合对象中数据的行为提取出来，封装到封装到一个迭代器中一个迭代器中，通过专门的迭代器来遍历聚合对，通过专门的迭代器来遍历聚合对象的内部数据，这就是迭代器模式的

5、本质象的内部数据，这就是迭代器模式的本质/聚合接口类聚合接口类 public interface Aggregate /Iterator的泛型由的泛型由Aggregate决定决定 public Iterator createIterator(); public int length(); public E get(int index); public void add(E obj); /聚合实现类聚合实现类public class ConcreteAggregate implements Aggregate private List items = new ArrayList(); publi

6、c Iterator createIterator() return new ConcreteIterator(this); public int length() return items.size(); public E get(int index) return (E)items.get(index); public void add(E obj) items.add(obj); /遍历器接口类遍历器接口类public interface Iterator public E first(); public boolean hasNext(); public E next(); publi

7、c E current(); /遍历器实现类遍历器实现类 public class ConcreteIterator implements Iterator private Aggregate aggregate; private int currentIndex = 0; /遍历状态遍历状态 public ConcreteIterator(Aggregate aggregate) this.aggregate = aggregate; public E first() currentIndex = 0; if(hasNext() return aggregate.get(currentInd

8、ex); else return null; /遍历器实现类遍历器实现类 public boolean hasNext() return (currentIndex aggregate.length(); public E next() currentIndex+; if(hasNext() return aggregate.get(currentIndex); else return null; public E current() return aggregate.get(currentIndex); /测试类测试类public class Test public static void

9、main(String args) Aggregate a = new ConcreteAggregate(); a.add(111); a.add(222); a.add(333); Iterator it = a.createIterator(); for(String s=it.first();it.hasNext();s=it.next() System.out.println(s); 1. 创建的集合创建的集合ConcreteAggregate可以存放任可以存放任何类型的数据何类型的数据2. 使用使用createIterator方法转换成方法转换成Iterator对象对象3. 使用使

10、用Iterator对象来按顺序显示集合中的内对象来按顺序显示集合中的内容容迭代器模式迭代器模式OO Example: C-string Iteratorclass StringIterator public:StringIterator(char *s); void first(); void next(); bool isDone(); char *currentItem();private: char *m_s; char *m_current;StringIterator:StringIterator(char *s):m_s(s), m_current(s) Object-orient

11、ed iterator is naturally implemented as a class Constructor stores passed pointer to char string s Also sets m_current to svoid StringIterator:first() m_current = m_s;void StringIterator:next() +m_current;bool StringIterator:isDone() return *m_current = 0;char *StringIterator:currentItem() return m_

12、current; “first” method (re)positions iterator at start of the string “next” method moves iterator to the next position “isDone” method tests whether iterator is at the end of the string “currentItem” returns a pointer to the character at the current iterator positionOO Example: C-string Iteratorint

13、 letterCount (StringIterator &si, char c) int count = 0; for (si.first(); ! si.isDone( ); si.next() if (*si.current_item() = c) +count; return count; Iterators naturally support use in looping constructs Here we show a for loop “first” is used to initialize “isDone” used for loop test “next” use

14、d to increment “currentItem” is used in the body of the loop When the loop completes, the function shown has Iterated through the whole string Counted occurrences of the passed character in the string Returned the occurrence countOO Example: C-string IteratorSTL与迭代器模式与迭代器模式 STL(Standard Template Lib

15、rary)是是C标准标准庫的一部分（庫的一部分（80%），是用），是用C Template(泛型泛型)机制来表达泛型的庫机制来表达泛型的庫 提示提示: Boost C+ LibrariesSTL设计的精髓在于设计的精髓在于: 把容器把容器Containers）和算法（）和算法（Algorithms）分开，）分开，彼此独立设计，最后再用迭代器把他们粘合在一起彼此独立设计，最后再用迭代器把他们粘合在一起 STL六大组件六大组件 容器（容器（Container） 算法（算法（Algorithm） 迭代器（迭代器（Iterator） 仿函数（仿函数（Function object） 适配器（适配器（A

16、daptor）(对对容器容器queue、stack) 空间配制器（空间配制器（allocator）STL的六大组件的六大组件全都是全都是抽象抽象出来出来的的ConceptsSTL与迭代器模式与迭代器模式STL与迭代器模式与迭代器模式vector:iterator FindMin(vector &vect) vector:iterator min = vect.begin(); vector:iterator iter = vect.begin(); while(iter != vect.end() if(*iter).Value (*min).Value) min = iter; it

17、er +; return min;Java迭代器模式迭代器模式Collection是所有是所有Java聚合类的根接口聚合类的根接口C o l l e c t i o n 的的 i t e r a t o r ( ) 方 法 返 回 一 个方 法 返 回 一 个java.util.Iterator类型的对象，而其子接口类型的对象，而其子接口java.util.List的的listIterator()方法返回一个方法返回一个java.util.ListIterator类型的对象类型的对象ListIterator是是Iterator的子类。它们构成了的子类。它们构成了Java语 言 对 迭 代 器

18、模 式 的 支 持 ，语 言 对 迭 代 器 模 式 的 支 持 ， J a v a 语 言 的语 言 的java.util.Iterator接口就是迭代器模式的应用。接口就是迭代器模式的应用。 Java迭代器可以理解为它工作在聚合对象的各个元迭代器可以理解为它工作在聚合对象的各个元素之间，每调用一次素之间，每调用一次next()方法，迭代器便越过下方法，迭代器便越过下个元素，并且返回它刚越过的那个元素的地址引用。个元素，并且返回它刚越过的那个元素的地址引用。 但也有一些限制，如某些迭代器只能单向移动。在但也有一些限制，如某些迭代器只能单向移动。在使用迭代器时，访问某个元素的唯一方法就是调用使

19、用迭代器时，访问某个元素的唯一方法就是调用next()。Java迭代器模式迭代器模式Java迭代器模式迭代器模式Iterator it = list.iterator(); while(it.hasNext() /using “it.next();”do some businesss logic 迭代器迭代器模式优点模式优点支持不同方式遍历一个聚合对象。支持不同方式遍历一个聚合对象。迭代器简化了聚合类。迭代器简化了聚合类。在同一个聚合上可以有多个遍历。在同一个聚合上可以有多个遍历。在迭代器模式中，增加新的聚合类和迭代在迭代器模式中，增加新的聚合类和迭代器类都很方便，无须修改原有代码，满足器类都

20、很方便，无须修改原有代码，满足“开闭原则开闭原则”的要求的要求。由于迭代器模式将存储数据和遍历数据由于迭代器模式将存储数据和遍历数据的职责分离，的职责分离，增加新的聚合类需要对应增加新的聚合类需要对应增加新的迭代器类增加新的迭代器类，类的个数，类的个数成对增加成对增加，这在一定程度上增加系统的复杂性。这在一定程度上增加系统的复杂性。迭代迭代器模式缺点器模式缺点访问一个聚合对象的内容而无须暴露它访问一个聚合对象的内容而无须暴露它的内部表示的内部表示需要为聚合对象提供多种遍历方式需要为聚合对象提供多种遍历方式为遍历不同的聚合结构提供一个统一的为遍历不同的聚合结构提供一个统一的接口接口 迭代器模式适

21、用情况迭代器模式适用情况 现在如有一个关于如何查询名册的问题，也就是要对一个名字的聚合对象来做巡访public class Person private String name = ; public Person(String name) = name; public String getName() return name; public class ConcreteAggregate private Person namecollection; private int last = 0; public ConcreteAggregate(int maxsize) thi

22、collection = new Personmaxsize; public Person getPersonAt(int index) return namecollectionindex; public void appendPerson(Person personName) collectionlast = personName; last+; public int getLength() return last; public class IteratorExample1 public static void main(String args) Concr

23、eteAggregate namecollection = new ConcreteAggregate(3); Person person; namecollection.appendPerson(new Person(Davis); namecollection.appendPerson(new Person(Frank); namecollection.appendPerson(new Person(Jeny); for(int i=0; inamecollection.getLength(); i+) person = namecollection.getPersonAt(i); Sys

24、tem.out.println( + person.getName(); 看起来好像不错，问题解决了，而且有点面向对象的味道，但 ConcreteAggregate类别跟 Person 类别绑在一起，如果要换成其他类别的话，ConcreteAggregate 类别势必要重写，如果 ConcreteAggregate 类别里的 Person namecollection，想换成 Vector 或 List 的话，那 IteratorExample1 类别的巡访方式也要重写，所以程序代码显得没有弹性，无法再利用利用利用 Iterator 模式來寫程式模式來寫程式public interface A

25、ggregate public abstract Iterator iterator();public interface Iterator public abstract boolean hasNext(); public abstract Object next();import java.util.* ;public class ConcreteAggregate implements Aggregate private Object collection; /private Vector collection; private int last = 0; public Concrete

26、Aggregate() /collection = new Vector(3); collection = new Object3; public Object getItemAt(int index) return collectionindex; /return (Object)collection.get(index); public void appendItem(Object item) this.collectionlast = item; last+; /collection.add(item); public int getLength() return last; /retu

27、rn collection.capacity(); public Iterator iterator() return new ConcreteIterator(this); public class ConcreteIterator implements Iterator private ConcreteAggregate namecollection; private int index; public ConcreteIterator(ConcreteAggregate collection) collection = collection; this.index =

28、0; public boolean hasNext() if (index namecollection.getLength() return true; else return false; public Object next() Object item = namecollection.getItemAt(index); index+; return item; public class IteratorExample2 public static void main(String args) ConcreteAggregate collection = new ConcreteAggregate(); collection.appendItem(new Person(Davis);