迭代器
一、 引言
迭代这个名词对于熟悉Java的人来说绝对不陌生。我们常常使用JDK提供的迭代接口进行java Collection的遍历：
List<String> list = new ArrayList<String>();
list.add("abc");
list.add("xyz");
for (Iterator<String> it = list.iterator(); it.hasNext();) {
String s = (String) it.next();
System.out.println(s);
}
而这就是关于迭代器模式应用很好的例子。本文讲到的“容器”“聚合”“集合”是同一个意思。
概述
迭代器模式(Iterator)：提供一种方法顺序一个聚合对象中各个元素，而又不暴露该对象内部表示。
适用场合
1.访问一个聚合对象的内容而无需暴露它的内部表示。
2.支持对聚合对象的多种遍历。
3.为遍历不同的聚合结构提供一个统一的接口(即，多态迭代)。
二、 定义与结构
迭代器（Iterator）模式，又叫做游标（Cursor）模式。迭代器提供一种对容器对象中的各个元素进行访问的方法，而又不需暴露该对象的内部细节。从定义可见，迭代器模式是为容器而生。
很明显，对容器对象的访问必然涉及到遍历算法。你可以将遍历方法写到容器对象中去（内部迭代器）；或者根本不去提供什么遍历算法，让使用容器的人自己去实现去吧（外部迭代器）。这两种情况好像都能够解决问题。
然而在前一种情况，容器承受了过多的功能，它不仅要负责自己“容器”内的元素维护（添加、删除等等），而且还要提供遍历自身的接口；而且由于遍历状态保存的问题，不能对同一个容器对象同时进行多个遍历。第二种方式倒是省事，却又将容器的内部细节暴露无遗。而迭代器模式的出现，很好的解决了上面两种情况的弊端。先来看下迭代器模式的真面目吧。
迭代器模式的类图如下：
迭代器模式的四个参与者：
1) 迭代器角色（Iterator）：迭代器角色负责定义访问和遍历元素的接口。
2) 具体迭代器角色（Concrete Iterator）：具体迭代器角色要实现迭代器接口，并要记录遍历中的当前位置。
3) 容器角色（Container或Aggregate）：容器角色负责提供创建具体迭代器角色的接口。
4) 具体容器角色（Concrete Container）：具体容器角色实现创建具体迭代器角色的接口——这个具体迭代器角色于该容器的结构相关。
三、代码结构
迭代器角色（Iterator）：
/// 迭代器抽象类
interface Iterator {
public abstract Object First();// 得到的开始对象
public abstract Object next();// 下一个对象
public abstract boolean IsDone();// 是否到结尾
public abstract Object CurrentItem();// 当前对象方法
}
具体迭代器角色（Concrete Iterator）
class ConcreteIterator implements Iterator {
// 定义了一个具体聚集对象
private Aggregate aggregate;
private int current = 0;
// 初始化对象将具体聚集类传入
public ConcreteIterator(Aggregate aggregate) {
this.aggregate = aggregate;
}
// 第一个对象
public Object First() {
return aggregate.get(0);
}
// 得到聚集的下一对象
public Object next() {
Object ret = null;
current++;
if (current < aggregate.getSize()) {
ret = aggregate.get(current);
}
return ret;
}
// 是否到结尾
public boolean IsDone() {
return current >= aggregate.getSize() ? true : false;
}
// 返回当前聚集对象
public Object CurrentItem() {
return aggregate.get(current);
}
}
容器角色（Container或Aggregate）：
// 聚集抽象类
abstract interface Aggregate {
// 创建迭代器
public abstract Iterator CreateIterator();
// 返回聚集总个数
public abstract int getSize();
// 声明一个索引器
public abstract Object get(int index);
// 声明一个索引器
public abstract void set(int index, Object value);
}
具体容器角色（Concrete Container）：本例直接使用的线性表的代码
class ConcreteAggregate implements Aggregate {
private final int LEN = 8; // 数组的默认大小
private int size; // 线性表中数据元素的个数
private Object[] elements; // 数据元素数组
public ConcreteAggregate() {
size = 0;
elements = new Object[LEN];
}
@Override
// 返回线性表中序号为i的数据元素
public Object get(int i) throws OutOfBoundaryException {
if (i < 0 || i >= size)
throw new OutOfBoundaryException("错误，指定的序号越界。");
return elements[i];
}
@Override
public int getSize() {
return size;
}
@Override
// 将数据元素e插入到线性表中i号位置
public void set(int i, Object e) throws OutOfBoundaryException {
if (i < 0 || i > size)
throw new OutOfBoundaryException("错误，指定的插入序号越界。");
if (size >= elements.length)
expandSpace();
for (int j = size; j > i; j--)
elements[j] = elements[j - 1];
elements[i] = e;
size++;
return;
}
private void expandSpace() {
Object[] a = new Object[elements.length * 2];
for (int i = 0; i < elements.length; i++)
a[i] = elements[i];
elements = a;
}
@Override
public Iterator CreateIterator() {
return new ConcreteIterator(this);
}
}
Client
public class Client {
public static void main(String[] args) {
// 聚集对象
Aggregate a = new ConcreteAggregate();
a.set(0, "张三");
a.set(1, "李四");
a.set(2, "王五");
// 声明迭代器对象
Iterator i = a.CreateIterator();
while (!i.IsDone()) {
System.out.println(i.CurrentItem());
i.next();
}
}
}
其中具体容器角色出现的越界异常定义如下
//线性表中出现序号越界时抛出该异常
public class OutOfBoundaryException extends RuntimeException {
public OutOfBoundaryException(String err) {
super(err);
}
}
四、Java对迭代器模式的支持
由于迭代器模式本身的规定比较松散，所以具体实现也就五花八门。我们在此仅举一例，根本不能将实现方式一一呈现。因此在举例前，我们先来列举下迭代器模式的实现方式。
1．迭代器角色定义了遍历的接口，但是没有规定由谁来控制迭代。在Java Collection的应用中，是由客户程序来控制遍历的进程，被称为外部迭代器；还有一种实现方式便是由迭代器自身来控制迭代，被称为内部迭代器。外部迭代器要比内部迭代器灵活、强大，而且内部迭代器在java语言环境中，可用性很弱。
2．在迭代器模式中没有规定谁来实现遍历算法。好像理所当然的要在迭代器角色中实现。因为既便于一个容器上使用不同的遍历算法，也便于将一种遍历算法应用于不同的容器。但是这样就破坏掉了容器的封装——容器角色就要公开自己的私有属性，在java中便意味着向其他类公开了自己的私有属性。
那我们把它放到容器角色里来实现好了。这样迭代器角色就被架空为仅仅存放一个遍历当前位置的功能。但是遍历算法便和特定的容器紧紧绑在一起了。
而在Java Collection的应用中，提供的具体迭代器角色是定义在容器角色中的内部类。这样便保护了容器的封装。但是同时容器也提供了遍历算法接口，你可以扩展自己的迭代器。
Iterator接口
package java.util;
public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}
容器角色，这里以List为例。它也仅仅是一个接口，就不罗列出来了，在此CreateIterator()方法被新的名称iterator()方法替代，都是返回当前容器对象的迭代器对象。
具体容器角色，便是实现了List接口的ArrayList等类。iterator()方法的定义如下，返回一个Itr实例
public abstract class AbstractList extends AbstractCollection implements List {
// 这个便是负责创建具体迭代器角色的工厂方法
public Iterator iterator() {
return new Itr();
}
}
具体迭代器角色，它是以内部类的形式给出来的(一般代码结构中有参数，return new Itr()没有参数，因为它是内部类，可以访问外部类AbstractList)。每一种集合类返回的Iterator具体类型可能不同，Array可能返回ArrayIterator，Set可能返回 SetIterator，Tree可能返回TreeIterator，但是它们都实现了Iterator接口，因此，客户端不关心到底是哪种 Iterator，它只需要获得这个Iterator接口即可，这就是面向对象的威力。AbstractList是为了将各个具体容器角色的公共部分提取出来而存在的。
AbstractList$Itr
Itr类依靠3个int变量（还有一个隐含的AbstractList的引用）来实现遍历，
-
cursor是下一次next()调用时元素的位置，第一次调用next()将返回索引为0的元素。
-
lastRet记录上一次游标所在位置，因此它总是比cursor少1。
- expectedModCount表示期待的modCount值，用来判断在遍历过程中集合是否被修改过。AbstractList包含一个 modCount变量，它的初始值是0，当集合每被修改一次时（调用add，remove等方法），modCount加1。因此，modCount如果不变，表示集合内容未被修改。
Itr初始化时用expectedModCount记录集合的modCount变量，此后在必要的地方它会检测modCount的值：
private class Itr implements Iterator<E> {
int cursor = 0;
int lastRet = -1;
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size();
}
public E next() {
checkForComodification();
try {
E 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();
}
}
参考：http://www.cnblogs.com/jqbird/archive/2011/08/31/2160653.html
http://www.cnblogs.com/forlina/archive/2011/06/22/2086845.html
