第十八章 迭代器模式
迭代器模式（Iterator Pattern）是一种行为型设计模式，它提供了一种访问集合对象元素的方式，而无需暴露集合的内部表示。迭代器模式将遍历集合的行为封装到独立的迭代器对象中，使得客户端代码可以在不了解集合的结构的情况下，遍历集合中的元素。
迭代器模式通常包括以下几个角色：
迭代器（Iterator）：迭代器是一个接口或抽象类，定义了可以遍历集合元素的方法。这包括移动到下一个元素、获取当前元素等操作。
具体迭代器（Concrete Iterator）：具体迭代器是迭代器接口的实现，它维护了对集合的引用，并跟踪当前遍历的位置。
集合（Collection）：集合是包含元素的数据结构，它提供了一个创建迭代器对象的方法，用于客户端获取迭代器对象。
具体集合（Concrete Collection）：具体集合是集合接口的实现，它通常包含集合内部的数据结构，如数组、列表等。
客户端（Client）：客户端是使用迭代器模式的代码，它通过迭代器对象遍历集合中的元素，而不需要知道集合的内部结构。
下面是一个简单的示例，演示了迭代器模式的应用：
// 迭代器接口
interface Iterator {
boolean hasNext();
Object next();
}
// 集合接口
interface Collection {
Iterator createIterator();
}
// 具体集合类
class ConcreteCollection implements Collection {
private String[] elements;
public ConcreteCollection(String[] elements) {
this.elements = elements;
}
@Override
public Iterator createIterator() {
return new ConcreteIterator();
}
//内部类
private class ConcreteIterator implements Iterator {
private int index;
@Override
public boolean hasNext() {
return index < elements.length;
}
@Override
public Object next() {
if (hasNext()) {
return elements[index++];
}
return null;
}
}
}
// 客户端代码
public class Client {
public static void main(String[] args) {
String[] elements = {"A", "B", "C", "D", "E"};
Collection collection = new ConcreteCollection(elements);
Iterator iterator = collection.createIterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " "); // 输出: A B C D E
}
}
}
在这个示例中，ConcreteCollection 实现了 Collection 接口，并提供了一个内部的具体迭代器 ConcreteIterator。客户端代码通过集合对象获取迭代器，然后使用迭代器遍历集合中的元素。客户端代码无需了解集合内部的数据结构，因为它通过迭代器对象访问元素。这种方式使得集合和遍历逻辑分离，提高了代码的可维护性和可扩展性。
今天，我们学习另外一种行为型设计模式，迭代器模式。它用来遍历集合对象。不过，很多编程语言都将迭代器作为一个基础的类库，直接提供出来了。在平时开发中，特别是业务开发，我们直接使用即可，很少会自己去实现一个迭代器。不过，知其然知其所以然，弄懂原理能帮助我们更好的使用这些工具类，所以，我觉得还是有必要学习一下这个模式。
我们知道，大部分编程语言都提供了多种遍历集合的方式，比如 for 循环、foreach 循环、迭代器等。所以，今天我们除了讲解迭代器的原理和实现之外，还会重点讲一下，相对于其他遍历方式，利用迭代器来遍历集合的优势。
1. 迭代器模式的原理和实现
迭代器模式（Iterator Design Pattern），也叫作游标模式（Cursor Design Pattern）。
在开篇中我们讲到，它用来遍历集合对象。这里说的“集合对象”也可以叫“容器”“聚合对象”，实际上就是包含一组对象的对象，比如数组、链表、树、图、跳表。迭代器模式将集合对象的遍历操作从集合类中拆分出来，放到迭代器类中，让两者的职责更加单一。
迭代器是用来遍历容器的，所以，一个完整的迭代器模式一般会涉及容器和容器迭代器两部分内容。为了达到基于接口而非实现编程的目的，容器又包含容器接口、容器实现类，迭代器又包含迭代器接口、迭代器实现类。对于迭代器模式，我画了一张简单的类图，你可以看一看，先有个大致的印象。
接下来，我们通过一个例子来具体讲，如何实现一个迭代器。
开篇中我们有提到，大部分编程语言都提供了遍历容器的迭代器类，我们在平时开发中，直接拿来用即可，几乎不大可能从零编写一个迭代器。不过，这里为了讲解迭代器的实现原理，我们假设某个新的编程语言的基础类库中，还没有提供线性容器对应的迭代器，需要我们从零开始开发。现在，我们一块来看具体该如何去做。
我们知道，线性数据结构包括数组和链表，在大部分编程语言中都有对应的类来封装这两种数据结构，在开发中直接拿来用就可以了。假设在这种新的编程语言中，这两个数据结构分别对应 ArrayList 和 LinkedList 两个类。除此之外，我们从两个类中抽象出公共的接口，定义为 List 接口，以方便开发者基于接口而非实现编程，编写的代码能在两种数据存储结构之间灵活切换。
现在，我们针对 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() {
return cursor != arrayList.size(); //注意这里，cursor在指向最后一个元素的时候，还是返回true
}
@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);
}
//...省略其他代码
}
public class Demo {
public static void main(String[] args) {
List<String> names = new ArrayList<>();
names.add("xzg");
names.add("wang");
names.add("zheng");
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.currentItem());
iterator.next();
}
}
}
对于 LinkedIterator，它的代码结构跟 ArrayIterator 完全相同，我这里就不给出具体的代码实现了，你可以参照 ArrayIterator 自己去写一下。结合刚刚的例子，我们来总结一下迭代器的设计思路。
总结下来就三句话：迭代器中需要定义 hasNext()、currentItem()、next() 三个最基本的方法。待遍历的容器对象通过依赖注入传递到迭代器类中。容器通过iterator()方法来创建迭代器。
这里我画了一张类图，如下所示。实际上就是对上面那张类图的细化，你可以结合着一块看。
2. 迭代器模式的优势
迭代器的原理和代码实现讲完了。接下来，我们来一块看一下，使用迭代器遍历集合的优势。一般来讲，遍历集合数据有三种方法：for 循环、foreach 循环、iterator 迭代器。对于这三种方式，我拿 Java 语言来举例说明一下。具体的代码如下所示：
List<String> names = new ArrayList<>();
names.add("xzg");
names.add("wang");
names.add("zheng");
// 第一种遍历方式：for循环
for (int i = 0; i < names.size(); i++) {
System.out.print(names.get(i) + ",");
}
// 第二种遍历方式：foreach循环
for (String name : names) {
System.out.print(name + ",")
}
// 第三种遍历方式：迭代器遍历
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + ",");//Java中的迭代器接口是第二种定义方式
}
实际上，foreach 循环只是一个语法糖而已，底层是基于迭代器来实现的。也就是说，上面代码中的第二种遍历方式（foreach 循环代码）的底层实现，就是第三种遍历方式（迭代器遍历代码）。这两种遍历方式可以看作同一种遍历方式，也就是迭代器遍历方式。
从上面的代码来看，for 循环遍历方式比起迭代器遍历方式，代码看起来更加简洁。那我们为什么还要用迭代器来遍历容器呢？为什么还要给容器设计对应的迭代器呢？原因有以下三个。
首先，对于类似数组和链表这样的数据结构，遍历方式比较简单，直接使用 for 循环来遍历就足够了。但是，对于复杂的数据结构（比如树、图）来说，有各种复杂的遍历方式。比如，树有前中后序、按层遍历，图有深度优先、广度优先遍历等等。如果由客户端代码来实现这些遍历算法，势必增加开发成本，而且容易写错。如果将这部分遍历的逻辑写到容器类中，也会导致容器类代码的复杂性。前面也多次提到，应对复杂性的方法就是拆分。我们可以将遍历操作拆分到迭代器类中。比如，针对图的遍历，我们就可以定义 DFSIterator、BFSIterator 两个迭代器类，让它们分别来实现深度优先遍历和广度优先遍历。
其次，将游标指向的当前位置等信息，存储在迭代器类中，每个迭代器独享游标信息。这样，我们就可以创建多个不同的迭代器，同时对同一个容器进行遍历而互不影响。
最后，容器和迭代器都提供了抽象的接口，方便我们在开发的时候，基于接口而非具体的实现编程。当需要切换新的遍历算法的时候，比如，从前往后遍历链表切换成从后往前遍历链表，客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可，其他代码都不需要修改。除此之外，添加新的遍历算法，我们只需要扩展新的迭代器类，也更符合开闭原则。
3. 在遍历的同时增删集合元素会发生什么？
在通过迭代器来遍历集合元素的同时，增加或者删除集合中的元素，有可能会导致某个元素被重复遍历或遍历不到。不过，并不是所有情况下都会遍历出错，有的时候也可以正常遍历，所以，这种行为称为结果不可预期行为或者未决行为，也就是说，运行结果到底是对还
是错，要视情况而定。
怎么理解呢？我们通过一个例子来解释一下。我们还是延续上一节课实现的 ArrayList 迭代器的例子。为了方便你查看，我把相关的代码都重新拷贝到这里了。
public interface Iterator<E> {
boolean hasNext();
void next();
E currentItem();
}
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() {
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 interface List<E> {
Iterator iterator();
}
public class ArrayList<E> implements List<E> {
//...
public Iterator iterator() {
return new ArrayIterator(this);
}
//...
}
public class Demo {
public static void main(String[] args) {
List<String> names = new ArrayList<>();
names.add("a");
names.add("b");
names.add("c");
names.add("d");
Iterator<String> iterator = names.iterator(); //55行
iterator.next();//56行
names.remove("a");//57行
}
}
我们知道，ArrayList 底层对应的是数组这种数据结构，在执行完第 55 行代码的时候，数组中存储的是 a、b、c、d 四个元素，迭代器的游标 cursor 指向元素 a。当执行完第 56行代码的时候，游标指向元素 b，到这里都没有问题。
为了保持数组存储数据的连续性，数组的删除操作会涉及元素的搬移。当执行到第 57 行代码的时候，我们从数组中将元素 a 删除掉，b、c、d 三个元素会依次往前搬移一位，这就会导致游标本来指向元素 b，现在变成了指向元素 c。原本在执行完第 56 行代码之后，我们还可以遍历到 b、c、d 三个元素，但在执行完第 57 行代码之后，我们只能遍历到 c、d 两个元素，b 遍历不到了。
对于上面的描述，我画了一张图，你可以对照着理解。
不过，如果第 57 行代码删除的不是游标前面的元素（元素 a）以及游标所在位置的元素（元素 b），而是游标后面的元素（元素 c 和 d），这样就不会存在任何问题了，不会存在某个元素遍历不到的情况了。
所以，我们前面说，在遍历的过程中删除集合元素，结果是不可预期的，有时候没问题（删除元素 c 或 d），有时候就有问题（删除元素 a 或 b），这个要视情况而定（到底删除的是哪个位置的元素），就是这个意思。
在遍历的过程中删除集合元素，有可能会导致某个元素遍历不到，那在遍历的过程中添加集合元素，会发生什么情况呢？还是结合刚刚那个例子来讲解，我们将上面的代码稍微改造一下，把删除元素改为添加元素。具体的代码如下所示：
public class Demo {
public static void main(String[] args) {
List<String> names = new ArrayList<>();
names.add("a");
names.add("b");
names.add("c");
names.add("d");
Iterator<String> iterator = names.iterator();
iterator.next();//10行
names.add(0, "x");//11行
}
}
在执行完第 10 行代码之后，数组中包含 a、b、c、d 四个元素，游标指向 b 这个元素，已经跳过了元素 a。在执行完第 11 行代码之后，我们将 x 插入到下标为 0 的位置，a、b、c、d 四个元素依次往后移动一位。这个时候，游标又重新指向了元素 a。元素 a 被游标重复指向两次，也就是说，元素 a 存在被重复遍历的情况。跟删除情况类似，如果我们在游标的后面添加元素，就不会存在任何问题。所以，在遍历的同时添加集合元素也是一种不可预期行为。
同样，对于上面的添加元素的情况，我们也画了一张图，如下所示，你可以对照着理解。
4. 如何应对遍历时改变集合导致的未决行为？
当通过迭代器来遍历集合的时候，增加、删除集合元素会导致不可预期的遍历结果。实际上，“不可预期”比直接出错更加可怕，有的时候运行正确，有的时候运行错误，一些隐藏很深、很难 debug 的 bug 就是这么产生的。那我们如何才能避免出现这种不可预期的运行结果呢？
有两种比较干脆利索的解决方案：一种是遍历的时候不允许增删元素，另一种是增删元素之后让遍历报错。
实际上，第一种解决方案比较难实现，我们要确定遍历开始和结束的时间点。遍历开始的时间节点我们很容易获得。我们可以把创建迭代器的时间点作为遍历开始的时间点。但是，遍历结束的时间点该如何来确定呢？
你可能会说，遍历到最后一个元素的时候就算结束呗。但是，在实际的软件开发中，每次使用迭代器来遍历元素，并不一定非要把所有元素都遍历一遍。
你可能还会说，那我们可以在迭代器类中定义一个新的接口 finishIteration()，主动告知容器迭代器使用完了，你可以增删元素了，但是，这就要求程序员在使用完迭代器之后要主动调用这个函数，也增加了开发成本，还很容易漏掉。
实际上，第二种解决方法更加合理。Java 语言就是采用的这种解决方案，增删元素之后，让遍历报错。接下来，我们具体来看一下如何实现。
怎么确定在遍历时候，集合有没有增删元素呢？我们在 ArrayList 中定义一个成员变量modCount，记录集合被修改的次数，集合每调用一次增加或删除元素的函数，就会给modCount 加 1。当通过调用集合上的 iterator() 函数来创建迭代器的时候，我们把modCount 值传递给迭代器的 expectedModCount 成员变量，之后每次调用迭代器上的hasNext()、next()、currentItem() 函数，我们都会检查集合上的 modCount 是否等于expectedModCount，也就是看，在创建完迭代器之后，modCount 是否改变过。
如果两个值不相同，那就说明集合存储的元素已经改变了，要么增加了元素，要么删除了元素，之前创建的迭代器已经不能正确运行了，再继续使用就会产生不可预期的结果，所以我们选择 fail-fast 解决方式，抛出运行时异常，结束掉程序，让程序员尽快修复这个因为不正确使用迭代器而产生的 bug。
上面的描述翻译成代码就是下面这样子。你可以结合着代码一起理解我刚才的讲解。
我们详细来看看next：
5. 如何在遍历的同时安全地删除集合元素？
像 Java 语言，迭代器类中除了前面提到的几个最基本的方法之外，还定义了一个remove() 方法，能够在遍历集合的同时，安全地删除集合中的元素。不过，需要说明的是，它并没有提供添加元素的方法。毕竟迭代器的主要作用是遍历，添加元素放到迭代器里本身就不合适。
我个人觉得，Java 迭代器中提供的 remove() 方法还是比较鸡肋的，作用有限。它只能删除游标指向的前一个元素，而且一个 next() 函数之后，只能跟着最多一个 remove() 操作，多次调用 remove() 操作会报错。我还是通过一个例子来解释一下。
public class Demo {
public static void main(String[] args) {
List<String> names = new ArrayList<>();
names.add("a");
names.add("b");
names.add("c");
names.add("d");
Iterator<String> iterator = names.iterator();
iterator.next();
iterator.remove();
iterator.remove(); //报错，抛出IllegalStateException异常
}
}
现在，我们一块来看下，为什么通过迭代器就能安全的删除集合中的元素呢？源码之下无秘密。我们来看下 remove() 函数是如何实现的，代码如下所示。稍微提醒一下，在 Java 实现中，迭代器类是容器类的内部类，并且 next() 函数不仅将游标后移一位，还会返回当前的元素。
在上面的代码实现中，迭代器类新增了一个 lastRet 成员变量，用来记录游标指向的前一个元素。通过迭代器去删除这个元素的时候，我们可以更新迭代器中的游标和 lastRet 值，来保证不会因为删除元素而导致某个元素遍历不到。如果通过容器来删除元素，并且希望更新迭代器中的游标值来保证遍历不出错，我们就要维护这个容器都创建了哪些迭代器，每个迭代器是否还在使用等信息，代码实现就变得比较复杂了。