重修设计模式-行为型-迭代器模式
提供一种方法访问一个容器对象中各个元素，而又不需暴露该对象的内部细节。
迭代器模式（Iterator Pattern）将容器的遍历操作从容器类中拆分出来，放到迭代器类中，让两者的职责更加单一。容器对象的遍历与其内部表示分离，可以更好的支持对容器对象的多种遍历算法，并且可以在不修改容器对象本身的前提下增加新的遍历方式。
迭代器是用来遍历容器的，一个完整的迭代器模式包含容器和迭代器两部分内容。基于面向接口而非细节的编程思想，集合又分为容器接口、容器实现类；迭代器又包含迭代器接口、迭代器实现类，它们的关系如下所示：
迭代器角色介绍如下：
- 容器（Collection）：它持有一组对象，可以是一个列表、数组或其他数据结构。这个对象实现了一个创建迭代器（Iterator）的接口。
- 迭代器（Iterator）：它是一个定义了遍历集合元素的接口。迭代器对象从集合对象中获取元素，并遍历这些元素。迭代器的典型方法包括
hasNext()（判断是否有下一个元素）和next()（返回下一个元素）。 - 具体容器（Concrete Collection）：它实现了容器接口，以存储和管理对象集合，并返回一个实现了迭代器接口的具体迭代器实例。
- 具体迭代器（Concrete Iterator）：它实现了迭代器接口，并持有对具体容器的引用，通过遍历集合中的元素来实现迭代器的核心方法。
大部分编程语言都提供了遍历容器的迭代器类，在平时开发中直接拿来用即可，不大可能从零编写一个迭代器，所以迭代器模式的应用场景也非常少见。不过为了理解迭代器模式的原理，还是举个例子，从头来实现迭代器模式。
例如，在开发中线性数据结构会经常使用，实现的方式又包括数组和链表，下面为这个容器来实现一个迭代器。
首先是容器部分，数组和链表对应 ArrayList 和 LinkedList 两个类。基于接口而非实现编程的思想，再从两个类中抽象出公共的接口 List，容器部分代码如下：
//容器接口
interface List<E> {//1.封装的迭代器方法fun iterator(): Iterator<E> //2.容器相关的抽象方法fun add(e: E)fun remove(e: E)fun size(): Intfun get(index: Int): E
}//具体容器1
class ArrayList<E>(): List<E> {private val arrayList = java.util.ArrayList<E>()//3.返回对应的迭代器override fun iterator(): Iterator<E> {return ArrayListIterator(this)}override fun size(): Int {//...return arrayList.size}override fun get(index: Int): E {return arrayList.get(index)}override fun remove(e: E) {//...}override fun add(e: E) {//...}
}//具体容器2
class LinkedList<E>(): List<E> {//...
}
至此容器部分已经定义好了，接下来再定义迭代器部分。
//抽象迭代器
interface Iterator<E> {operator fun hasNext(): Booleanoperator fun next(): E?
}//ArrayList的具体迭代器
class ArrayListIterator<E>(val list: ArrayList<E>) : Iterator<E> {private var cursor = 0 //游标override fun hasNext(): Boolean {return cursor < list.size()}override fun next(): E? {if (cursor >= list.size()) {throw NoSuchElementException()}return list.get(cursor)}
}
至此一个完整的迭代器模式已经完整定义出来了，下面是调用方需要迭代容器元素时的代码：
fun main() {val arrayList = ArrayList<String>()arrayList.add("人生")arrayList.add("得意")arrayList.add("须尽欢")val iterator = arrayList.iterator()while (iterator.hasNext()) {val element = iterator.next()println("e:${element}")}
}
//输出：
人生
得意
须尽欢
以上就是迭代器的原理和代码实现。其实集合的遍历还可以通过 for 循环的方式，那么迭代器模式和 for 循环相比有哪些优势呢？
fun main() {//通过for循环遍历：for (i in 0 until list.size()) {println("e:${list.get(i)}")}
}
首先，对于类似数组和链表这样的数据结构，遍历方式比较简单，直接使用 for 循环来遍历就足够了。但是，对于复杂的数据结构（比如树、图）来说，有各种复杂的遍历方式。比如，树有前中后序、按层遍历；图有深度优先、广度优先遍历等等。如果由客户端代码来实现这些遍历算法，势必增加开发成本，且容易写错。如果将这部分遍历的逻辑写到容器类中，也会导致容器类代码的复杂性。
foreach 循环只是一个语法糖，底层是基于迭代器实现的。
所以面对复杂数据结构时，就需要使用迭代器模式，将容器代码和遍历代码进行解耦，将容器的遍历操作从容器类中拆分出来。比如，针对图的深度优先遍历和广度优先遍历，就可以定义 DFSIterator 和 BFSIterator 两个迭代器类来实现不同的遍历算法，在添加新的遍历算法时，只需要扩展新的迭代器类即可，非常符合开闭原则。而且每个迭代器独享自己的游标信息，就可以创建多个迭代器，同时对一个容器进行遍历。
至此我们可以总结出迭代器模式的优缺点：
优点：
职责分离：容器代码和遍历代码解耦，让两者职责更加单一，从而可以灵活的增加和修改遍历算法，符合开闭原则。简化集合的遍历：迭代器提供了一个统一的接口来遍历集合对象，不需要调用者了解集合的内部结构。使用灵活：迭代器之间相互独立，多个迭代器可同时遍历同一个容器。安全性：由于集合对象的内部表示被封装起来，外部代码只能通过迭代器接口访问集合元素，这有助于保护集合对象的数据安全。
缺点：
增加复杂性：对于简单的集合，使用迭代器模式可能会增加额外的类和方法，从而增加代码的复杂性。性能考虑：在某些情况下，使用迭代器可能比直接访问集合元素要慢，因为迭代器需要在每次调用next()方法时检查是否有下一个元素。
如何在迭代器中修改元素
通过迭代器来遍历集合元素的同时，如果增加或者删除集合中的元素，有可能会导致某个元素被重复遍历或遍历不到，也有可能正常遍历（运行结果的对错，要视情况而定），这种情况称为结果不可预期行为。
举个例子：
fun main() {val list = java.util.ArrayList<String>()list.add("a")list.add("b")list.add("c")list.add("d")val iterator = list.iterator()list.remove("b")println(iterator.next())
}
集合中存在 a、b、c、d 四个元素，在进行迭代器遍历时，如果其他地方删除了容器内的元素 b，此时对容器继续遍历就会产生不可预期的行为：正常遍历或漏掉某个元素。
原因是为了保持数组存储数据的连续性，数组的删除操作会涉及元素的搬移，从而导致迭代器中游标和数组元素不匹配了，流程如下：
同样，遍历过程中外部对容器添加元素也会造成未决行为：
虽然我们知道游标前删除或添加元素，会导致遍历漏掉或重复遍历元素；游标后删除或添加元素则遍历结果正常，但不知道的是外部会在什么时机对容器元素进行修改，所以是未决行为。
要解决迭代器遍历集合时，增加、删除集合元素导致的不可预期行为有两个方案：
- 迭代器遍历时，禁止增删元素（
困难） - 遵循fail-first思想，在增删元素之后立即让迭代器遍历报错，将错误尽早抛出（
合理）
第一种解决方案比较难实现，需要确定遍历开始和结束的时间点。遍历开始的时间节点很容易获得，比如迭代器的创建时间。但遍历结束的时间点无法确认，毕竟存在遍历到一半就结束的情况，如果调用方主动通知结束遍历，又会增加调用成本，所以该方案pass。
第二种解决方案比较合理，Java 中的迭代器使用的就是该方案，增删元素后，让迭代器报错。具体实现步骤如下：
首先容器内维护一个成员变量 modCount，记录容器被修改的次数。每次容器增加或删除元素时候，都让 modCount + 1。其次迭代器也维护一个成员变量 expectedModCount，用来记录迭代器创建时，容器的修改次数。当通过 iterator() 函数创建迭代器时，将容器 modCount 赋值给迭代器 expectedModCount 变量，每次调用迭代器方法（如 hasNext()、next()）时，都校验一下当前容器的修改次数 modCount，是否等于迭代器创建时容器的修改次数 expectedModCount，也就是看迭代器创建后 modCount 是否修改过。如果两个值不同，则说明容器修改过了，迭代器继续运行会产生不可预期的结果，此时选择 fail-fast 方式，抛出异常，尽早终止迭代流程。
//容器：
class ArrayList<E>(): List<E> {var modCount: Int = 0 //1.记录容器修改次数...override fun remove(e: E) {modCount++//...}override fun add(e: E) {modCount++//...}
}//迭代器：
class ArrayListIterator<E>(val list: ArrayList<E>) : Iterator<E> {private var cursor = 0 //游标private var expectedModCount: Int = list.modCount //2.记录初始修改次数override fun hasNext(): Boolean {checkForComodification()return cursor < list.size()}override fun next(): E? {checkForComodification()if (cursor >= list.size()) {throw NoSuchElementException()}return list.get(cursor)}//3.校验并抛出异常private fun checkForComodification() {if (list.modCount != expectedModCount) throw ConcurrentModificationException()}
}//调用时：
fun main() {val arrayList = ArrayList<String>()arrayList.add("人生")arrayList.add("得意")arrayList.add("须尽欢")val iterator = arrayList.iterator()arrayList.add("。")iterator.next() //报错：ConcurrentModificationException异常！
}
为什么 Java 的迭代器可以安全的删除元素？
在 Java 中，迭代器还定义了一个 remove() 方法，用于在遍历集合的同时，安全地删除集合中的元素。那么它是怎么做到的？下面分析一下 Java 迭代器的源码：
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 returnint lastRet = -1; // index of last element returned; -1 if no suchint 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();//1. 调用next时，cursor加1，lastRet被赋值为游标的上一个元素cursor = i + 1;return (E) elementData[lastRet = i];}public void remove() {if (lastRet < 0) //3.调用remove后lastRet为-1，再调用就会抛出异常throw new IllegalStateException();checkForComodification();try {//2.删除时，只能删除游标的上一个元素，并将游标回退一个位置ArrayList.this.remove(lastRet);cursor = lastRet;lastRet = -1;expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}}
}
在上面的代码实现中，迭代器类新增了一个 lastRet 成员变量，用来记录游标指向的前一个元素。迭代器的 remove 方法也只能删除 lastRet 指向的元素。在删除这个元素时，会将迭代器的游标回退一位，从而避免游标前删除元素导致的某个元素遍历不到。流程如下：
分析源码后可以发现，虽然 Java 中的迭代器提供了删除方法，但使用上也有一定限制：只能删除游标指向的前一个元素，且一个 next() 函数之后，只能跟着最多一个 remove() 操作，多次调用 remove() 操作会报错。
至于 Java 为什么不提供增加元素的方法，个人觉得迭代器的主要作用毕竟是遍历，添加元素的逻辑放到迭代器里本来就不太合适。
总结
迭代器模式提供了一种方法，访问一个容器对象中各个元素，而又不需暴露该对象的内部细节。目的是将容器对象的遍历与其内部表示分离，可以更好的支持对容器对象的多种遍历算法，并且可以在不修改容器对象本身的前提下增加新的遍历方式。
迭代器模式工作原理如下：
- 创建容器对象：首先，创建一个具体容器对象，并添加一些元素。
- 获取迭代器：通过容器对象的迭代器创建方法（通常是
iterator()），获取一个具体迭代器对象。 - 遍历集合：使用迭代器对象的
hasNext()方法检查是否还有元素可以遍历，如果有，则使用next()方法获取下一个元素，直到遍历完所有元素。