迭代器模式的原理和实现
迭代器模式（Iterator Design Pattern），也叫作游标模式（Cursor Design Pattern）。
在开篇中我们讲到，它用来遍历集合对象。这里说的“集合对象”也可以叫“容器”“聚合对象”，实际上就是包含一组对象的对象，比如数组、链表、树、图、跳表。迭代器模式将集合对象的遍历操作从集合类中拆分出来，放到迭代器类中，让两者的职责更加单一。
迭代器是用来遍历容器的，所以，一个完整的迭代器模式一般会涉及容器和容器迭代器两部分内容。为了达到基于接口而非实现编程的目的，容器又包含容器接口、容器实现类，迭代器又包含迭代器接口、迭代器实现类。
现在，我们针对 ArrayList 和 LinkedList 两个线性容器，设计实现对应的迭代器。按照之前给出的迭代器模式的类图，我们定义一个迭代器接口 Iterator，以及针对两种容器的具体的迭代器实现类 ArrayIterator 和 ListIterator。
我们先来看下 Iterator 接口的定义。具体的代码如下所示：
// 接口定义方式一 public interface Iterator<E> { boolean hasNext(); void next(); E currentItem(); } // 接口定义方式二 public interface Iterator<E> { boolean hasNext(); E next(); }
Iterator 接口有两种定义方式。
在第一种定义中，next() 函数用来将游标后移一位元素，currentItem() 函数用来返回当前游标指向的元素。在第二种定义中，返回当前元素与后移一位这两个操作，要放到同一个函数 next() 中完成。
第一种定义方式更加灵活一些，比如我们可以多次调用 currentItem() 查询当前元素，而不移动游标。所以，在接下来的实现中，我们选择第一种接口定义方式。
现在，我们再来看下 ArrayIterator 的代码实现，具体如下所示。代码实现非常简单，不需要太多解释。你可以结合着我给出的 demo，自己理解一下。
public class ArrayIterator<E> implements Iterator<E> { private int cursor; private ArrayList<E> arrayList; public ArrayIterator(ArrayList<E> arrayList) { this.cursor = 0; this.arrayList = arrayList; } @Override public boolean hasNext() { //注意这里，cursor在指向最后一个元素的时候，hasNext()仍旧返回true。 return cursor != arrayList.size(); } @Override public void next() { cursor++; } @Override public E currentItem() { if (cursor >= arrayList.size()) { throw new NoSuchElementException(); } return arrayList.get(cursor); } } public class Demo { public static void main(String[] args) { ArrayList<String> names = new ArrayList<>(); names.add("xzg"); names.add("wang"); names.add("zheng"); Iterator<String> iterator = new ArrayIterator(names); while (iterator.hasNext()) { System.out.println(iterator.currentItem()); iterator.next(); } } }
在上面的代码实现中，我们需要将待遍历的容器对象，通过构造函数传递给迭代器类。实际上，为了封装迭代器的创建细节，我们可以在容器中定义一个 iterator() 方法，来创建对应的迭代器。为了能实现基于接口而非实现编程，我们还需要将这个方法定义在 List 接口中。具体的代码实现和使用示例如下所示：
public interface List<E> { Iterator iterator(); //...省略其他接口函数... } public class ArrayList<E> implements List<E> { //... public Iterator iterator() { return new ArrayIterator(this); } //...省略其他代码 }
对于 LinkedIterator，它的代码结构跟 ArrayIterator 完全相同，我这里就不给出具体的代码实现了，你可以参照 ArrayIterator 自己去写一下。
待补充
遍历集合一般有三种方式：for 循环、foreach 循环、迭代器遍历。后两种本质上属于一种，都可以看作迭代器遍历。相对于 for 循环遍历，利用迭代器来遍历有下面三个优势：
- 迭代器模式封装集合内部的复杂数据结构，开发者不需要了解如何遍历，直接使用容器提供的迭代器即可；
- 迭代器模式将集合对象的遍历操作从集合类中拆分出来，放到迭代器类中，让两者的职责更加单一；
- 迭代器模式让添加新的遍历算法更加容易，更符合开闭原则。除此之外，因为迭代器都实现自相同的接口，在开发中，基于接口而非实现编程，替换迭代器也变得更加容易。
遍历集合的同时，为什么不能增删集合元素？
在通过迭代器来遍历集合元素的同时，增加或者删除集合中的元素，有可能会导致某个元素被重复遍历或遍历不到。不过，并不是所有情况下都会遍历出错，有的时候也可以正常遍历，所以，这种行为称为结果不可预期行为或者未决行为，也就是说，运行结果到底是对还是错，要视情况而定。
添加跟删除情况类似，如果我们在游标的后面添加元素，就不会存在任何问题。所以，在遍历的同时添加集合元素也是一种不可预期行为。
实际上，“不可预期”比直接出错更加可怕，有的时候运行正确，有的时候运行错误，一些隐藏很深、很难 debug 的 bug 就是这么产生的。
如何应对遍历时改变集合导致的未决行为？
有两种比较干脆利索的解决方案：一种是遍历的时候不允许增删元素，另一种是增删元素之后让遍历报错。第一种解决方案比较难实现，因为很难确定迭代器使用结束的时间点。第二种解决方案更加合理。Java 语言就是采用的这种解决方案。增删元素之后，我们选择 fail-fast 解决方式，让遍历操作直接抛出运行时异常。
怎么确定在遍历时候，集合有没有增删元素呢？我们在 ArrayList 中定义一个成员变量 modCount，记录集合被修改的次数，集合每调用一次增加或删除元素的函数，就会给 modCount 加 1。当通过调用集合上的 iterator() 函数来创建迭代器的时候，我们把 modCount 值传递给迭代器的 expectedModCount 成员变量，之后每次调用迭代器上的 hasNext()、next()、currentItem() 函数，我们都会检查集合上的 modCount 是否等于 expectedModCount，也就是看，在创建完迭代器之后，modCount 是否改变过。
public class ArrayIterator implements Iterator { private int cursor; private ArrayList arrayList; private int expectedModCount; public ArrayIterator(ArrayList arrayList) { this.cursor = 0; this.arrayList = arrayList; this.expectedModCount = arrayList.modCount; } @Override public boolean hasNext() { checkForComodification(); return cursor < arrayList.size(); } @Override public void next() { checkForComodification(); cursor++; } @Override public Object currentItem() { checkForComodification(); return arrayList.get(cursor); } private void checkForComodification() { if (arrayList.modCount != expectedModCount) throw new ConcurrentModificationException(); } } //代码示例 public class Demo { public static void main(String[] args) { List<String> names = new ArrayList<>(); names.add("a"); names.add("b"); names.add("c"); Iterator<String> iterator = names.iterator(); iterator.next(); names.remove("a"); iterator.next();//抛出ConcurrentModificationException异常 } }
如何在遍历的同时安全地删除集合元素
像 Java 语言，迭代器类中除了前面提到的几个最基本的方法之外，还定义了一个 remove() 方法，能够在遍历集合的同时，安全地删除集合中的元素。不过，需要说明的是，它并没有提供添加元素的方法。毕竟迭代器的主要作用是遍历，添加元素放到迭代器里本身就不合适。我个人觉得，Java 迭代器中提供的 remove() 方法还是比较鸡肋的，作用有限。它只能删除游标指向的前一个元素，而且一个 next() 函数之后，只能跟着最多一个 remove() 操作，多次调用 remove() 操作会报错。我还是通过一个例子来解释一下。
为什么通过迭代器就能安全的删除集合中的元素呢？源码之下无秘密。我们来看下 remove() 函数是如何实现的，代码如下所示。稍微提醒一下，在 Java 实现中，迭代器类是容器类的内部类，并且 next() 函数不仅将游标后移一位，还会返回当前的元素。
public class ArrayList<E> { transient Object[] elementData; private int size; public Iterator<E> iterator() { return new 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; Itr() {} 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(); } } } }
在上面的代码实现中，迭代器类新增了一个 lastRet 成员变量，用来记录游标指向的前一个元素。通过迭代器去删除这个元素的时候，我们可以更新迭代器中的游标和 lastRet 值，来保证不会因为删除元素而导致某个元素遍历不到。如果通过容器来删除元素，并且希望更新迭代器中的游标值来保证遍历不出错，我们就要维护这个容器都创建了哪些迭代器，每个迭代器是否还在使用等信息，代码实现就变得比较复杂了。
如何实现一个支持“快照”功能的迭代器？
这个问题算是对上一节课内容的延伸思考，为的是帮你加深对迭代器模式的理解，也是对你分析、解决问题的一种锻炼。你可以把它当作一个面试题或者练习题，在看我的讲解之前，先试一试自己能否顺利回答上来。
问题描述我们先来介绍一下问题的背景：如何实现一个支持“快照”功能的迭代器模式？理解这个问题最关键的是理解“快照”两个字。所谓“快照”，指我们为容器创建迭代器的时候，相当于给容器拍了一张快照（Snapshot）。之后即便我们增删容器中的元素，快照中的元素并不会做相应的改动。而迭代器遍历的对象是快照而非容器，这样就避免了在使用迭代器遍历的过程中，增删容器中的元素，导致的不可预期的结果或者报错。接下来，我举一个例子来解释一下上面这段话。具体的代码如下所示。容器 list 中初始存储了 3、8、2 三个元素。尽管在创建迭代器 iter1 之后，容器 list 删除了元素 3，只剩下 8、2 两个元素，但是，通过 iter1 遍历的对象是快照，而非容器 list 本身。所以，遍历的结果仍然是 3、8、2。同理，iter2、iter3 也是在各自的快照上遍历，输出的结果如代码中注释所示。
List<Integer> list = new ArrayList<>(); list.add(3); list.add(8); list.add(2); Iterator<Integer> iter1 = list.iterator();//snapshot: 3, 8, 2 list.remove(new Integer(2));//list：3, 8 Iterator<Integer> iter2 = list.iterator();//snapshot: 3, 8 list.remove(new Integer(3));//list：8 Iterator<Integer> iter3 = list.iterator();//snapshot: 3 // 输出结果：3 8 2 while (iter1.hasNext()) { System.out.print(iter1.next() + " "); } System.out.println(); // 输出结果：3 8 while (iter2.hasNext()) { System.out.print(iter1.next() + " "); } System.out.println(); // 输出结果：8 while (iter3.hasNext()) { System.out.print(iter1.next() + " "); } System.out.println();
解决方案
public class ArrayList<E> implements List<E> { private static final int DEFAULT_CAPACITY = 10; private int actualSize; //不包含标记删除元素 private int totalSize; //包含标记删除元素 private Object[] elements; private long[] addTimestamps; private long[] delTimestamps; public ArrayList() { this.elements = new Object[DEFAULT_CAPACITY]; this.addTimestamps = new long[DEFAULT_CAPACITY]; this.delTimestamps = new long[DEFAULT_CAPACITY]; this.totalSize = 0; this.actualSize = 0; } @Override public void add(E obj) { elements[totalSize] = obj; addTimestamps[totalSize] = System.currentTimeMillis(); delTimestamps[totalSize] = Long.MAX_VALUE; totalSize++; actualSize++; } @Override public void remove(E obj) { for (int i = 0; i < totalSize; ++i) { if (elements[i].equals(obj)) { delTimestamps[i] = System.currentTimeMillis(); actualSize--; } } } public int actualSize() { return this.actualSize; } public int totalSize() { return this.totalSize; } public E get(int i) { if (i >= totalSize) { throw new IndexOutOfBoundsException(); } return (E)elements[i]; } public long getAddTimestamp(int i) { if (i >= totalSize) { throw new IndexOutOfBoundsException(); } return addTimestamps[i]; } public long getDelTimestamp(int i) { if (i >= totalSize) { throw new IndexOutOfBoundsException(); } return delTimestamps[i]; } } public class SnapshotArrayIterator<E> implements Iterator<E> { private long snapshotTimestamp; private int cursorInAll; // 在整个容器中的下标，而非快照中的下标 private int leftCount; // 快照中还有几个元素未被遍历 private ArrayList<E> arrayList; public SnapshotArrayIterator(ArrayList<E> arrayList) { this.snapshotTimestamp = System.currentTimeMillis(); this.cursorInAll = 0; this.leftCount = arrayList.actualSize();; this.arrayList = arrayList; justNext(); // 先跳到这个迭代器快照的第一个元素 } @Override public boolean hasNext() { return this.leftCount >= 0; // 注意是>=, 而非> } @Override public E next() { E currentItem = arrayList.get(cursorInAll); justNext(); return currentItem; } private void justNext() { while (cursorInAll < arrayList.totalSize()) { long addTimestamp = arrayList.getAddTimestamp(cursorInAll); long delTimestamp = arrayList.getDelTimestamp(cursorInAll); if (snapshotTimestamp > addTimestamp && snapshotTimestamp < delTimestamp) { leftCount--; break; } cursorInAll++; } } }
参考
设计模式之美设计模式代码重构-极客时间
https://time.geekbang.org/column/intro/250
