首页 > 代码库 > Java 迭代器综述
Java 迭代器综述
一、摘要
迭代器模式是与集合共生共死的。一般来说,我们只要实现一个容器,就需要同时提供这个容器的迭代器。使用迭代器的好处是:封装容器的内部实现细节,对于不同的集合,可以提供统一的遍历方式,简化客户端的访问和获取容器内数据。在此基础上,我们可以使用 Iterator 完成对集合的遍历,此外,for 循环和foreach 语法也可以用于遍历集合类。ListIterator 是容器 List容器族特有的双向迭代器。本文要点主要包括:
- 迭代器模式
- Iterator 迭代器 与 Iterable 接口
- 循环遍历 : foreach,Iterator,for 的异同
- ListIterator 简述(容器 List 详解)
二、迭代器模式
迭代器模式是与集合共生共死的。一般来说,我们只要实现一个容器,就需要同时提供这个容器的迭代器,就像 Java 中的 Collection (List、Set 等) ,这些容器都有自己的迭代器。假如我们要实现一个新的容器,当然也需要引入迭代器模式,给我们的容器实现一个迭代器。使用迭代器的好处是:封装容器的内部实现细节,对于不同的集合,可以提供统一的遍历方式,简化客户端的访问和获取容器内数据。
但是,由于容器与迭代器的关系太密切了,所以大多数语言在实现容器的同时也提供了相应的迭代器,并且在绝大多数情况下,这些语言所提供的容器和迭代器都可以满足我们的需要。所以,现实中需要我们自己去实现迭代器模式的场景还是比较少见的,我们常常只需要使用语言中已有的容器和迭代器就可以了。
1、定义与结构
定义
迭代器(Iterator)模式,又叫做游标(Cursor)模式。GOF给出的定义为:提供一种方法访问一个容器(container)对象中的各个元素,而又不需暴露该容器对象的内部细节。
从定义可见,迭代器模式是为容器而生。我们知道,对容器对象的访问必然涉及到遍历算法。你可以一股脑的将遍历方法塞到容器对象中去,或者,根本不去提供什么遍历算法,让使用容器的人自己去实现。这两种情况好像都能够解决问题。然而,对于前一种情况,容器承受了过多的功能,它不仅要负责自己“容器”内的元素维护(增、删、改、查 等),而且还要提供遍历自身的接口;而且最重要的是, 由于遍历状态保存的问题,不能对同一个容器对象同时进行多个遍历,并且还需增加 reset 操作。第二种方式倒是省事,却又将容器的内部细节暴露无遗。
迭代器模式角色组成
迭代器角色(Iterator): 迭代器角色 负责定义访问和遍历元素的接口;
具体迭代器角色(Concrete Iterator): 具体迭代器角色 要实现迭代器接口,并要 记录遍历中的当前位置;
容器角色(Container): 容器角色 负责定义创建具体迭代器角色的接口;
具体容器角色(Concrete Container): 具体容器角色 实现创建具体迭代器角色的接口 —— 这个 具体迭代器角色 与该 容器的结构 相关。
结构图
从结构上可以看出,迭代器模式在客户端与容器之间加入了迭代器角色。迭代器角色的加入,就可以很好的避免容器内部细节的暴露,而且也使得设计符合 单一职责原则。
特别需要注意的是,在迭代器模式中,具体迭代器角色和具体容器角色是耦合在一起的 —— 遍历算法是与容器的内部细节紧密相关的。为了使客户程序从与具体迭代器角色耦合的困境中脱离出来,避免具体迭代器角色的更换给客户程序带来的修改,迭代器模式抽象了具体迭代器角色,使得客户程序更具一般性和重用性,这被称为 多态迭代 。
适用性
1.访问一个容器对象的内容而无需暴露它的内部表示;
2.支持对容器对象的多种遍历;
3.为遍历不同的容器结构提供一个统一的接口 ( 即,支持多态迭代 )。
2、举例
由于迭代器模式本身的规定比较松散,所以具体实现也就五花八门,我们在此仅举一例。在举例前,我们先来列举一下迭代器模式的实现方式。
迭代器角色定义了遍历的接口,但是没有规定由谁来控制迭代。在 Java Collection 框架中,是由客户程序来控制遍历的进程,被称为 外部迭代器;还有一种实现方式便是由迭代器自身来控制迭代,被称为 内部迭代器。外部迭代器要比内部迭代器灵活、强大,而且内部迭代器在 Java 语言环境中,可用性很弱;
在迭代器模式中没有规定谁来实现遍历算法,好像理所当然的要在迭代器角色中实现。因为既便于一个容器上使用不同的遍历算法,也便于将一种遍历算法应用于不同的容器。但是这样就破坏掉了容器的封装 —— 容器角色就要公开自己的私有属性,在 Java 中便意味着向其他类公开了自己的私有属性;
那我们把它放到容器角色里来实现好了,这样,迭代器角色就被架空为仅仅存放一个遍历当前位置的功能。但是遍历算法便和特定的容器紧紧绑在一起了。而在 Java Collection 框架中,提供的具体迭代器角色是定义在容器角色中的 内部类,这样便保护了容器的封装。但是同时容器也提供了遍历算法接口,并且你可以扩展自己的迭代器。
我们来看下 Java Collection 中的迭代器的实现:
//迭代器角色,仅仅定义了遍历接口
public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}
//容器角色,这里以 List 为例,间接实现了 Iterable 接口
public interface Collection<E> extends Iterable<E> {
...
Iterator<E> iterator();
...
}
public interface List<E> extends Collection<E> {}
//具体容器角色,便是实现了 List 接口的 ArrayList 等类。为了突出重点这里指罗列和迭代器相关的内容
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
……
//这个便是负责创建具体迭代器角色的工厂方法
public Iterator<E> iterator() {
return new Itr();
}
//具体迭代器角色,它是以内部类的形式出来的。 AbstractList 是为了将各个具体容器角色的公共部分提取出来而存在的。
//作为内部类的具体迭代器角色
private class Itr implements Iterator<E> {
int cursor = 0;
int lastRet = -1;
//集合迭代中的一种“快速失败”机制,这种机制提供迭代过程中集合的安全性. ArrayList 中存在 modCount 对象,增删操作都会使 modCount++ ,通过两者的对比,迭代器可以快速的知道迭代过程中是否存在 list.add() 类似的操作,存在的话快速失败!
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(); //抛出异常,迭代终止
}
}
迭代器模式的使用
客户程序要先得到具体容器角色,然后再通过具体容器角色得到具体迭代器角色。这样便可以使用具体迭代器角色来遍历容器了……
3、适用情况
我们可以看出迭代器模式给容器的应用带来以下好处:
1) 支持以不同的方式遍历一个容器角色。根据实现方式的不同,效果上会有差别(例如,List 中的 iterator 和 listIterator)。
2) 简化了容器的接口。但是在 Java Collection 中为了提高可扩展性,容器还是提供了遍历的接口。
3) 简化了遍历方式。对于对象集合的遍历,还是比较麻烦的,对于数组或者有序列表,我们尚可以通过游标来取得,但用户需要在对集合了解很清楚的前提下,自行遍历对象,但是对于 哈希表 来说,用户遍历起来就比较麻烦了。而引入了迭代器方法后,用户用起来就简单的多了。
4) 可以提供多种遍历方式。比如,对于有序列表,我们可以根据需要提供正序遍历,倒序遍历两种迭代器,用户用起来只需要得到我们实现好的迭代器,就可以方便的对集合进行遍历了。
5) 对同一个容器对象,可以同时进行多个遍历。因为遍历状态是保存在每一个迭代器对象中的。
6) 封装性良好,用户只需要得到迭代器就可以遍历,而对于遍历算法则不用去关心。
7) 在 Java Collection 中,迭代器提供一种快速失败机制 ( ArrayList是线程不安全的,在ArrayList类创建迭代器之后,除非通过迭代器自身remove或add对列表结构进行修改,否则在其他线程中以任何形式对列表进行修改,迭代器马上会抛出异常,快速失败),防止多线程下迭代的不安全操作。
由此,也可以得出迭代器模式的适用范围:
1) 访问一个容器对象的内容而无需暴露它的内部表示;
2) 支持对容器对象的多种遍历;
3) 为遍历不同的容器结构提供一个统一的接口(多态迭代)。
三、Iterator 迭代器与 Iterable 接口
1、Iterator 迭代器接口 : java.util 包
Java 提供一个专门的迭代器接口 Iterator,我们可以对某个容器实现该 Interface,来提供标准的 Java 迭代器。
用 Iterator 模式实现遍历集合
Iterator 模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来,从而避免向客户端暴露集合的内部结构。
例如,如果没有使用 Iterator,遍历一个数组 的方法是使用索引:
for(int i=0; i<array.size(); i++) { ... get(i) ... }
而 遍历一个HashSet 又 必须使用 while 循环或 foreach,但不能使用for循环:
while((e=e.next())!=null) { ... e.data() ... }
对以上两种方法,客户端都必须事先知道集合的类型(内部结构),访问代码和集合本身是紧耦合的,无法将访问逻辑从集合类和客户端代码中分离出来,从而导致每一种集合对应一种遍历方法,客户端代码无法复用。更恐怖的是,如果以后需要把 ArrayList 更换为 LinkedList,则原来的客户端代码必须全部重写。
为解决以上问题,Iterator模式总是用同一种逻辑来遍历集合:
for(Iterator it = c.iterater(); it.hasNext(); ) { ... }
奥秘在于 客户端自身不维护遍历集合的”指针”,所有的内部状态(如当前元素位置,是否有下一个元素)都由 Iterator 来维护,而这个 Iterator 由集合类通过工厂方法生成,因此,它知道如何遍历整个集合。而且,客户端从不直接和集合类打交道,它总是控制Iterator,向它发送”向前”,”向后”,”取当前元素”的指令,就可以间接遍历整个集合。
首先看看 java.util.Iterator 接口的定义:
public interface Iterator {
boolean hasNext();
Object next();
void remove(); // 可选操作
}
依赖前两个方法就能完成遍历,典型的代码如下:
for(Iterator it = c.iterator(); it.hasNext(); ) { Object o = it.next(); // 对o的操作... }
多态迭代 : 每一种集合类返回的 Iterator 具体类型可能不同,Array 可能返回 ArrayIterator,Set 可能返回 SetIterator,Tree 可能返回 TreeIterator,但是它们都实现了 Iterator 接口,因此,客户端不关心到底是哪种 Iterator,它只需要获得这个 Iterator 接口即可,这就是面向对象的威力。
2、Iterable 接口 : java.lang 包
Java 中还提供了一个 Iterable 接口,Iterable接口实现后的功能是“返回”一个迭代器 。我们常用的实现了该接口的子接口有: Collection<E>系列,包括 List<E>, Queue<E>, Set<E> 在内。特别值得一提的是,Map 接口没有实现 Iterable 接口。该接口的 iterator() 方法返回一个标准的 Iterator 实现。
实现 Iterable 接口来实现适用于 foreach 遍历的自定义类
Iterable 接口包含一个能够产生 Iterator 的 iterator() 方法,并且 Iterable 接口被 foreach 用来在序列中实现移动。因此,实现这个接口允许对象成为 foreach 语句的目标,也就可以通过 foreach语法遍历你的底层序列。
在 JDK1.5 以前,用 Iterator 遍历序列的语法:
for(Iterator it = c.iterator(); it.hasNext(); ) { Object o = it.next(); // 对o的操作... }
在 JDK1.5 以及以后的版本中,引进了 foreach,对上面的代码在语法上作了简化 ( 但是限于只读,如果需要remove,还是直接使用 Iterator ):
for(Type t : collection) { ... }
3、思辨
为什么一定要去实现 Iterable 这个接口呢? 为什么不直接实现 Iterator接口 呢?
看一下 JDK 中的集合类,比如 List一族或者Set一族,都是实现了 Iterable 接口,但并不直接实现 Iterator 接口。仔细想一下这么做是有道理的:因为 Iterator接口的核心方法 next() 或者 hasNext() 是依赖于迭代器的当前迭代位置的。若 Collection 直接实现 Iterator 接口,势必导致集合对象中包含当前迭代位置的数据(指针)。当集合在不同方法间被传递时,由于当前迭代位置不可预置,那么 next() 方法的结果会变成不可预知。除非再为 Iterator接口 添加一个 reset() 方法,用来重置当前迭代位置。但即使这样,Collection 也只能同时存在一个当前迭代位置(不能同时多次迭代同一个序列:必须要等到当前次迭代完成并reset后,才能再一次从头迭代)。 而序列实现 Iterable 接口则不然,每次调用都会返回一个从头开始计数的迭代器(Iterator),因此,多个迭代器间是互不干扰的。
四、foreach,Iterator,for
foreach 和 Iterator 的关系
foreach 是 jdk5.0 新增加的一个循环结构,可以用来处理集合中的每个元素而不用考虑集合的下标。
格式如下 :
for(variable:collection){ statement; }
定义一个变量用于暂存集合中的每一个元素,并执行相应的语句(块)。Collection 必须是一个数组或者是一个实现了 lterable 接口的类对象。
可以看出,使用 foreach 循环语句的优势在于更加简洁,更不容易出错,不必关心下标的起始值和终止值。forEach 不是关键字,关键字还是 for ,语句是由 iterator 实现的,它们最大的不同之处就在于 remove() 方法上。
特别地,一般调用删除和添加方法都是具体集合的方法,例如:
List list = new ArrayList();
list.add(...);
list.remove(...);
...
但是,如果在循环的过程中调用集合的 remove() 方法,就会导致循环出错,因为循环过程中 list.size() 的大小变化了,就导致了错误(Iterator的快速失败机制
)。 所以,如果想在循环语句中删除集合中的某个元素,就要用迭代器 iterator 的 remove() 方法,因为它的 remove() 方法不仅会删除元素,还会维护一个标志,用来记录目前是不是可删除状态,例如,你不能连续两次调用它的remove()方法,调用之前至少有一次 next() 方法的调用。因此,foreach 就是为了让用 iterator 循环访问的形式简单,写起来更方便。当然功能不太全,所以若是需要使用删除操作,那么还是要用它原来的形式。
使用for循环与使用迭代器iterator的对比
从效率角度分析:
采用 ArrayList 对随机访问比较快,而for循环中的get()方法,采用的即是随机访问的方法,因此在ArrayList里,for循环较快;
采用 LinkedList 则是顺序访问比较快,iterator 中的next()方法,采用的即是顺序访问的方法,因此在LinkedList里,使用iterator较快。
从数据结构角度分析:
使用 for循环 适合访问有序结构,可以根据下标快速获取指定元素;而 Iterator 适合访问无序结构,因为迭代器是通过 next() 和 Pre() 来定位的,可以访问没有顺序的集合.
使用 Iterator 的好处在于可以使用相同方式去遍历集合中元素,而不用考虑集合类的内部实现(只要它实现了 java.lang.Iterable 接口),如果使用 Iterator 来遍历集合中元素,一旦不再使用 List 转而使用 Set 来组织数据,那遍历元素的代码不用做任何修改,如果使用 for 来遍历,那所有遍历此集合的算法都得做相应调整,因为List有序,Set无序,结构不同,他们的访问算法也不一样.
五、ListIterator 简述
1、简述
ListIterator 系列表迭代器,实现了Iterator<E>接口。该迭代器允许程序员按任一方向遍历列表、迭代期间修改列表,并获得迭代器在列表中的当前位置。ListIterator 没有当前元素;它的光标位置始终位于调用 previous() 所返回的元素和调用 next() 所返回的元素之间。长度为 n 的列表的迭代器有 n+1 个可能的指针位置,如下面的插入符举例说明:
注意,remove() 和 set(Object) 方法不是根据光标位置定义的;它们是根据对调用 next() 或 previous() 所返回的最后一个元素的操作定义的。
2、与 Iterator 区别
Iterator 和 ListIterator 主要区别有:
ListIterator 有 add()方法,可以向 List 中添加对象,而 Iterator 不能 ;
ListIterator 和 Iterator 都有 hasNext()和next()方法,可以实现顺序向后遍历。但是 ListIterator 有 hasPrevious() 和 previous() 方法,可以实现逆向(顺序向前)遍历,而 Iterator 就不可以 ;
ListIterator 可以利用 nextIndex() 和 previousIndex() 定位当前的索引位置,而 Iterator 没有此功能 ;
ListIterator 可以通过 listIterator() 方法和 listIterator(int index) 方法获得,而 Iterator 只能由 iterator() 方法获得 ;
二者都可以实现删除对象,但是ListIterator可以使用set()方法实现对象的修改。Iterator 仅能遍历,不能修改。因为ListIterator的这些功能,可以实现对LinkedList, ArrayList等List数据结构的操作。
引用:
JDK APK 1.6.0
深入浅出Java设计模式之迭代器模式
23种设计模式(13):迭代器模式
Java程序员从笨鸟到菜鸟之(四十五)大话设计模式(九)迭代器模式和命令模式
Java迭代器深入理解及使用
Java迭代器
iterator与iterable
java Iterable接口和Iterator迭代器
Iterator和ListIterator
Java 迭代器综述