摘要生成中...

AI 摘要

Hunyuan-lite

迭代器模式（Iterator Design Pattern），也叫作游标模式（Cursor Design Pattern），用于遍历集合对象。集合对象，又叫容器或聚合对象，实际上就是包含一组对象的对象，如数组、链表、树、图、跳表。迭代器模式将集合对象的遍历操作从集合类中拆分出来，放到迭代器类中，让两者的职责更加单一。

我们在 Java 中写一个 for 循环是这样的：

1
2
3

for(int i=0;i<arr.length;i++){
	System.out.println(arr[i]);
}

把 i 的作用抽象化、通用化后形成的模式称为迭代器模式。

登场角色：

Iterator（迭代器）：负责定义按这个顺序逐个遍历元素的接口（API）。比如定义了 hasNext 和 next 两个方法。
Concretelterator（具体的迭代器）：负责实现 Iterator 角色所定义的接口（API）。该角色包含了遍历集合所必须的信息。
Aggregate（集合）：负责定义创建 Iterator 角色的接口（API）。这个接口（API）是一个方法，会创建出「按顺序访问保存在我内部元素的人」。
ConcreteAggregate（具体的集合）：负责实现 Aggregate 角色所定义的接口（API）。他会创建出具体的 Iterator 角色，即 ConcreteIterator 角色。

// Aggregate接口：
public interface Aggregate{
	public Iterator Iterator();
}

// Iterator接口：
public interface Iterator{
	public boolean hasNext();
	public Object next();// 返回集合中的一个元素。
}

Iterator 接口方法解析：

hasNext 方法理解成：确认接下来是否可以调用 next 方法
next 方法指的是「返回当前元素，并指向下一个元素」。为了下次调用 next 能正确返回下一个元素，一般在 next 中隐含实现了将迭代器移动到下一个元素的逻辑。由于这里接口中的定义，使用 next 方法记得强制类型转换。

从上面的 UML 图我们发现，迭代器本身需要聚合一个 Aggregate 容器。为了封装迭代器的创建细节，ConcreteAggregate 的创建迭代器 Iterator() 中会把自身作为参数，作为迭代器的构造函数：

public class ConcreteAggregate implements Aggregate {
  public Iterator iterator() {
    return new ConcreteIterator(this);
  }
  //...省略其他代码
}

使用迭代器模式：

ConcreteAggregate foos = new ConcreAggregate(/* params */);// 创建一个集合
Iterator it = foos.iterator();
while(it.hasNext()){
    Foo foo = (Foo) it.next(); // 记得强制类型转换
   // do something
}

上面的 while 循环中不依赖于聚合类的具体实现。

例子

BookShelfIterator 类知道 BookShelf 是如何实现的。也就是说，如果 BookShelf 的实现发生了改变，即 getBookAt 方法这个接口（API）发生变化时，我们必须修改 BookshelfIterator 类。正如 Aggregate 和 Iterator 这两个接口是对应的一样，concreteAggregate 和 concreteIterator 这两个类也是对应的。

优点	缺点
单一职责原则。通过将体积庞大的遍历算法代码抽取为独立的类，可对客户端代码和集合进行整理。	如果你的程序只与简单的集合进行交互，应用该模式可能会矫枉过正。
开闭原则。可实现新型的集合和迭代器并将其传递给现有代码，无需修改现有代码。	对于某些特殊集合，使用迭代器可能比直接遍历的效率低。
可以并行遍历同一集合，因为每个迭代器对象都包含其自身的遍历状态。
可以暂停遍历并在需要时继续。

引入迭代器的目的

引入迭代器这一复杂的设计模式在于可以将遍历和实现分离开，提高代码的可复用性。

应对复杂性

对于类似数组和链表这样的数据结构，遍历方式比较简单，直接使用 for 循环来遍历就足够了。但是，对于复杂的数据结构（比如树、图）来说，有各种复杂的遍历方式。比如，树有站内文章前中后序、按层遍历，图有深度优先、广度优先遍历等等。如果由客户端代码来实现这些遍历算法，势必增加开发成本，而且容易写错。如果将这部分遍历的逻辑写到容器类中，也会导致容器类代码的复杂性。

应对复杂性的方法就是拆分。我们可以将遍历操作拆分到迭代器类中。比如，针对图的遍历，我们就可以定义 DFSIterator、BFSIterator 两个迭代器类，让它们分别来实现深度优先遍历和广度优先遍历。

游标信息存储

将游标指向的当前位置等信息，存储在迭代器类中，每个迭代器独享游标信息。这样，我们就可以创建多个不同的迭代器，同时对同一个容器进行遍历而互不影响。

易于切换迭代器

容器和迭代器都提供了抽象的接口，方便我们在开发的时候，基于接口而非具体的实现编程。当需要切换新的遍历算法的时候，比如，从前往后遍历链表切换成从后往前遍历链表，客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可，其他代码都不需要修改。除此之外，添加新的遍历算法，我们只需要扩展新的迭代器类，也更符合开闭原则。

拓展思路与相关设计模式

拓展思路：

难以理解抽象类和接口的人常常使用 ConcreteAggregate 角色和 ConcreteIterator 角色编程，而不使用 Aggregate 接口和 Iterator 接口，他们总想用具体的类来解决所有的问题。但是如果只使用具体的类来解决问题，很容易导致类之间的强耦合，这些类也难以作为组件被再次利用。为了弱化类之间的耦合，进而使得类更加容易作为组件被再次利用，我们需要引入抽象类和接口。（面向抽象编程）
「将遍历功能置于 Aggregate 角色之外」是 Iterator 模式的一个特征。根据这个特征，可以针对一个 ConcreteAggregate 角色编写多个 ConcreteIterator 角色。
自己写多种迭代器，比如从最后向前遍历，前后遍历，跳跃式遍历等。

Java 中的迭代器

很多编程语言都将迭代器作为一个基础的类库，直接提供，比如 Java。

Java 中遍历集合的方式：

// for
for (int i = 0, len = strings.size(); i < len; i++) {
    System.out.println(strings.get(i));
}

// foreach（实际为语法糖，底层基于迭代器实现，即下面的 Iterator 方法）
for (String var : strings) {
    System.out.println(var);
}

// Iterator
Iterator iterator = strings.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

此外还有使用站内文章函数式编程与 Java 中的 Lambda 表达式遍历的方法，详看下面的 Iterable 接口中的 forEach 的默认实现。

Java 中有垃圾回收（GC），不需要 deleteIterator 方法。

Java 迭代器是一种单向遍历机制，即只能从前往后遍历集合中的元素，不能往回遍历。

使用迭代器遍历集合时，如果在遍历过程中对集合进行了修改（例如添加或删除元素），可能会导致 ConcurrentModificationException 异常，为了避免这个问题，可以使用迭代器自身的 remove() 方法进行删除操作。

Iterable 接口

实现 Iterable 接口可以为集合类提供 for-each 循环的支持。源代码中，Iterable 接口定义了三个方法，其中两个提供了默认实现，只有 iterator() 是要求实现类必须实现的方法。那么当某个类实现了 Iterable 接口就可以使用 foreach 进行迭代。同时 Iterable 中又封装了 Iterator 接口，那么这个类也可以使用 Iterator 迭代器。

// Java Iterable 接口源代码
public interface Iterable<T> {
    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

Iterator 接口

Iterator 主要是为了方便遍历集合中的所有元素（相当于是定义了遍历元素的范式）。

// Java Iterator 接口源代码
public interface Iterator<E> {
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

遍历集合的同时不能删改集合元素

在通过迭代器来遍历集合元素的同时，增加或者删除集合中的元素，有可能会导致某个元素被重复遍历或遍历不到。不过，并不是所有情况下都会遍历出错，有的时候也可以正常遍历。这种行为称为结果不可预期行为或者未决行为。

应对遍历时改变集合所导致的未决行为

「不可预期」比直接出错更加可怕。为了避免出现不可预期的结果，有两种直接的解决方案：

遍历的时候不允许增删元素
增删元素之后让遍历报错。Java 语言采用了这种解决方案。

Java 的 ArrayList 中定义一个成员变量 modCount，记录集合被修改的次数，集合每调用一次增加或删除元素的函数，就会给 modCount 加 1。当通过调用集合上的 iterator() 函数来创建迭代器的时候，我们把 modCount 值传递给迭代器的 expectedModCount 成员变量，之后每次调用迭代器上的 hasNext()、next()、currentItem() 函数，我们都会检查集合上的 modCount 是否等于 expectedModCount，也就是看，在创建完迭代器之后，modCount 是否改变过。

在遍历的同时安全地删除集合元素

像 Java 语言 ArrayList，迭代器类中除了前面提到的几个最基本的方法之外，还定义了一个 remove() 方法，能够在遍历集合的同时，安全地删除集合中的元素。但是作用有限，它只能删除游标指向的前一个元素，而且一个 next() 函数之后，只能跟着最多一个 remove() 操作，多次调用 remove() 操作会报错。

Java ArrayList 并没有提供遍历过程中添加元素的方法。

部分源码如下：

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 值，来保证不会因为删除元素而导致某个元素遍历不到。

实现一个支持「快照」功能的 `iterator`

本节仅供发散思考，当作一个小小的思维训练。

所谓「快照」，指我们为容器创建迭代器的时候，相当于给容器拍了一张快照（Snapshot）。之后即便我们增删容器中的元素，快照中的元素并不会做相应的改动。而迭代器遍历的对象是快照而非容器，这样就避免了在使用迭代器遍历的过程中，增删容器中的元素，导致的不可预期的结果或者报错。

一种简单的解决方案为在迭代器类中定义一个成员变量 snapshot 来存储快照。每当创建迭代器的时候，都拷贝一份容器中的元素到快照中，后续的遍历操作都基于这个迭代器自己持有的快照来进行。这个解决方案虽然简单，但代价也有点高。每次创建迭代器的时候，都要拷贝一份数据到快照中，会增加内存的消耗。如果一个容器同时有多个迭代器在遍历元素，就会导致数据在内存中重复存储多份。不过，庆幸的是，Java 中的拷贝属于站内文章浅拷贝，也就是说，容器中的对象并非真的拷贝了多份，而只是拷贝了对象的引用而已。

第二种解决方案为，我们可以在容器中为每个元素保存两个时间戳，一个是添加时间戳 addTimestamp，一个是删除时间戳 delTimestamp。当元素被加入到集合中的时候，我们将 addTimestamp 设置为当前时间，将 delTimestamp 设置成最大长整型值（Long.MAX_VALUE）。当元素被删除时，我们将 delTimestamp 更新为当前时间，表示已经被删除。注意，这里只是标记删除，而非真正将它从容器中删除。

同时，每个迭代器也保存一个迭代器创建时间戳 snapshotTimestamp，也就是迭代器对应的快照的创建时间戳。当使用迭代器来遍历容器的时候，只有满足 addTimestamp<snapshotTimestamp<delTimestamp 的元素，才是属于这个迭代器的快照。

如果元素的 addTimestamp>snapshotTimestamp，说明元素在创建了迭代器之后才加入的，不属于这个迭代器的快照；如果元素的 delTimestamp<snapshotTimestamp，说明元素在创建迭代器之前就被删除掉了，也不属于这个迭代器的快照。

这样就在不拷贝容器的情况下，在容器本身上借助时间戳实现了快照功能。注意，这里我们没有考虑 ArrayList 的扩容问题。

实际上，上面的解决方案相当于解决了一个问题，又引入了另外一个问题。ArrayList 底层依赖数组这种数据结构，原本可以支持快速的随机访问，在 $O(1)$ 时间复杂度内获取下标为 i 的元素，但现在，删除数据并非真正的删除，只是通过时间戳来标记删除，这就导致无法支持按照下标快速随机访问了。

解决随机访问的方法也不难，我们可以在 ArrayList 中存储两个数组。一个支持标记删除的，用来实现快照遍历功能；一个不支持标记删除的（也就是将要删除的数据直接从数组中移除），用来支持随机访问。

本文 PlantUML 归档

interface Aggregate{
	{method} {abstract} iterator
}

interface Iterator{
	{method} {abstract} hasNext
	{method} {abstract} next
}

class ConcreteAggregate{
	{method} iterator
}

class ConcreteIterator{
	aggregate
	{method} hasNext
	{method} next
}

Aggregate -> Iterator : Creates
Aggregate <|.. ConcreteAggregate
ConcreteAggregate -o ConcreteIterator
Iterator <|.. ConcreteIterator

本文参考

《图解设计模式》第 1 章 Iterator 模式
本科生课程笔记《程序设计中级实践＆设计模式》 - TJU 🍐⚱️
极客时间专栏 - 设计模式之美 - 王争
Java Iterator（迭代器） | 菜鸟教程 (runoob.com)
【Java】Iterable接口的使用-CSDN博客
Java集合系列 Iterable、Iterator这俩兄弟细致解读（超通俗易懂）_java iterable-CSDN博客
迭代器设计模式

迭代器模式：游标

引入迭代器的目的

应对复杂性

游标信息存储

易于切换迭代器

拓展思路与相关设计模式

Java 中的迭代器

Iterable 接口

Iterator 接口

遍历集合的同时不能删改集合元素

应对遍历时改变集合所导致的未决行为

在遍历的同时安全地删除集合元素

实现一个支持「快照」功能的 `iterator`

本文 PlantUML 归档

本文参考

开始

快速链接

法律声明

联系本站

迭代器模式：游标

引入迭代器的目的

应对复杂性

游标信息存储

易于切换迭代器

拓展思路与相关设计模式

Java 中的迭代器

Iterable 接口

Iterator 接口

遍历集合的同时不能删改集合元素

应对遍历时改变集合所导致的未决行为

在遍历的同时安全地删除集合元素

实现一个支持「快照」功能的 iterator

本文 PlantUML 归档

本文参考

实现一个支持「快照」功能的 `iterator`