Java 迭代器介绍
迭代器模式
迭代器模式是一个典型的设计模式，提供一种方法访问一个容器对象中各个元素，而又不暴露该对象的内部细节。因为屏蔽了细节，可以针对不同实现的容器，提供一致的标准化的访问方法。
迭代器模式有四个部分组成：
- 抽象容器 Aggregate
- 具体容器 ConcreteAggregate
- 抽象迭代器 Iterator
- 迭代器实现 ConcreteIterator
迭代器模式类图
Java 迭代器
框架
Java 中的容器接口 Collection 继承了迭代器接口 Iterable，迭代器接口中的 iterator() 方法返回 Iterator 类型对象。这里 Collection 相当于迭代器模式中的抽象容器 Aggregate；Iterator 相当于迭代器模式中的抽象迭代器 Iterator。
public interface Collection<E> extends Iterable<E> {
Iterator<E> iterator();
// 省略其他
}
public interface Iterable<T> {
Iterator<T> iterator();
}
public interface Iterator<E> {
// 判断是否还有下一个元素
boolean hasNext();
// 获取下一个元素
E next();
// 移除一个元素
default void remove() {
throw new UnsupportedOperationException("remove");
}
}
java 中 List 、Set、Queue 容器都会继承实现 Collection 类，提供迭代器接口，我们以 List 为例看一下迭代器的实现。
List 容器框架
List 的迭代器实现
我们可以看一下 ArrayList 中迭代器的实现：
- Itr 实现了 hasNext、next、remove 三个方法
- 遍历靠下标 cursor 的递增，其实现和我们自己遍历数组一样（迭代器好处是屏蔽细节、标准化）
- remove 之后 lastRet 置为 -1，调用一次 next 后只能调用一次 remove，否则会抛异常
- 调用 next 之前也要调用 hasNext 判断，否则 cursor 大于等于 size 会抛异常
- 迭代器遍历过程中，只能使用其 remove 方法移除元素，如果使用了 List 本身的 add、remove 方法，会导致下次调用 next 方法时抛出异常。原因是迭代器 Itr 里保存了 List 修改次数 modCount 的值到局部变量 expectedModCount 里，不通过迭代器的修改会导致两者不一致，导致 checkForComodification 方法抛异常。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
}
ArrayList 中的迭代器在容器变更后会失效，那么有没有不失效的呢？我们可以看看 CopyOnWriteArrayList 的迭代器实现：
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
private static class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array **/
private final Object[] snapshot;
/** Index of element to be returned by subsequent call to next. */
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
public boolean hasNext() {
return cursor < snapshot.length;
}
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
}
}
CopyOnWriteArrayList 迭代器 COWIterator 遍历的是创建迭代器时的数据快照，这样后续容器的元素增加和减少，就不会导致迭代器的失效了。请注意这里并没有记录容器元素的实际大小，容器元素数目完全取决于数组 snapshot 的长度。我们知道在 ArrayList 中，为了减少扩容次数，扩容时数组长度会比实际所需的长，导致数组长度和容器元素个数不一致。CopyOnWriteArrayList 没有这个问题吗？确实是的，我们看一下其添加元素时，扩容的源代码：
- 每次扩容，新数组长度等于老数组长度加1，长度刚刚好。
- 每次添加元素，都需要扩容，效率低下。
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
扩展迭代器 ListIterator
List 容器中，不仅提供了普通迭代器 Iterator 的实现，还有一个功能更强的迭代器 ListIterator：
- 除了正向遍历之外，还提供了反向遍历的功能
- 除了 remove 之外，提供了 set 和 add，当然通过迭代器的这些方法修改数据，都不应该导致迭代器失效
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove();
void set(E e);
void add(E e);
}
总结
迭代器模式，体现了标准化遍历容器，屏蔽内部实现细节的编程思想。
普通迭代器在遇到容器修改时会失效，但是一些线程安全类实现的迭代器比如 COWIterator 是不会因容器修改而失效的。
