Design-Pattern-Iterator

迭代器模式是一种行为设计模式，让你能在不暴露集合底层表现形式 （列表、 栈和树等） 的情况下遍历集合中所有的元素。

场景

迭代器实在是太常见了，已经成为了很多现代编程语言本身的一部分。

在日常开发过程中，处理同类型的多个数据对象的场景太常见了。我们通常会用集合表示这些同类型的一组对象。为了了解集合构成，需要不重复地访问元素，这个过程称为遍历。

学过算法和数据结构，或者刷过leetcode的朋友，应该也写过某些集合的遍历算法。比如数组、链表、树的遍历。遍历也有不同的算法，对数组可以顺序，逆序遍历；对于树可以广度优先，深度优先遍历。不同的遍历算法决定哪些元素会被访问，访问顺序。

如果使用C语言作为刷题语言，由于C语言本身没有内置容器，每道题都需要自己实现遍历算法。实现的次数多了就会觉得繁琐，同样的遍历算法会被反复实现。从可复用性角度来讲，反复使用的集合数据结构，和其遍历算法应该在某个类中实现，以便后续直接使用。

值得思考的是遍历算法应该在哪里实现。

可以在客户端中实现，例如客户端获取数组的长度，再使用一个递增的索引逐个获取元素。这样写的好处是灵活性高，客户端可以按照需求自定义遍历的方式。但也会导致代码重复，封装性差等问题。客户端需要了解集合的详细结构，导致代码更加耦合。上例中提到的使用C语言刷题，反复编写遍历算法，就是在客户端实现遍历算法的例子。

for (int i = 0; i < list.size(); i++) {
    // 通过 数组[i] 访问当前元素
}

又或者是实现在数据结构的类中。在同一个类中实现的优点是，封装性好，使用简单，遍历的代码会更加简洁。

// 实现在数据结构类中，更简洁
collection.forEach(...)

// 实现在数据结构类外
for_each(collection.begin(), collection.end(), ...)

但这某种程度也违反了单一职责原则：集合类既负责存储数据，又负责遍历逻辑，承担了多个职责。当遍历方式需要扩展或变化时（例如支持多种遍历方式：正向、反向、过滤等），集合类可能会变得臃肿，难以维护。

迭代器模式

迭代器模式，则是将集合对象的遍历行为抽象出来，封装成独立的迭代器对象，从而使得遍历逻辑与集合本身解耦，提供统一、灵活、可扩展的访问方式，同时隐藏集合的内部结构。

不同的迭代器对象，都包含一个获取元素的方法用于遍历，通常还有一个用于表示是否遍历结束的方法，这些共性的方法会被声明在迭代器接口中。客户端通过迭代器接口与不同的具体迭代器交互，而不需要直接依赖具体的集合类，降低了代码对集合类的耦合。

迭代器对象不仅包含了遍历算法，也包含了遍历过程中的状态。例如遍历了多少元素，一共有多少元素，剩余多少元素等。因此在不修改集合元素的情况下，不同的迭代器对象可以互相独立地遍历同一个集合。

至此可以给出迭代器的大致设计。

// 迭代器接口
interface Iterator {
    boolean hasNext();
    Object next();
}

// 具体迭代器
class ConcreteIterator implements Iterator {
    // 遍历集合的状态
    int cursor;
    // 待遍历的集合
    Collection concreteCollection;
    
    public ConcreteIterator(Collection collection) {
        this.concreteCollection = collection;
        this.cursor = 0;
    }
    
    // 实现迭代方法
    @Override
    public boolean hasNext() {
        return cursor < concreteCollection.size();
    }
    @Override
    public Object next() {
        ...
    }
}

// 其他算法的具体迭代器实现
class DeepFirstIterator implements Iterator

由于集合中存放的元素不确定是哪种具体类型，因此在迭代器接口中的next方法中，使用了Object作为了方法的返回值。实际在Java中，可以使用泛型，在编译期提供类型检查，这样就不需要在客户端中重复执行类型转换的操作。

// 使用泛型的迭代器接口
interface Iterator<E> {
    boolean hasNext();
    E next();
}

客户端如何获取迭代器，最简单的方式是客户端直接new一个具体迭代器的实例，但这样会导致客户端和具体迭代器耦合。

另一个简单的做法是直接在集合类中直接提供迭代器的获取方法。由于迭代是集合最基础的功能，因此可以把这个方法定义在集合接口中。

// 集合接口
interface IterableCollection<E> {
    Iterator<E> createIterator();
}

// 具体集合
class ConcreteCollection<E> implements IterableCollection<E> {
    @Override
    public Iterator<E> createIterator() {
        return new ConcreteIterator<>(this);
    }
}

但这样的问题是只能创建一种具体迭代器，当某个集合需要支持多种算法的迭代器就不行了。一种方案是声明多种迭代器创建方法，不同的算法通过不同的方法名区分，例如createDeepFirstIterator和createBreadthFristIterator。显然这些方法不该声明在集合接口中，因为不是所有的集合都支持深度和广度优先的遍历。定义在集合接口会导致其他具体集合被迫实现不需要的方法，这违背了接口隔离原则。因此只能定义在具体集合中。对这些方法的调用需要客户端依赖具体集合类。

另一种方案是创建迭代器的方法增加一个入参，可以是字符串或者枚举类。并在实现代码中根据入参，通过if或switch语句返回对应的具体迭代器。

再复杂点可以将创建迭代器的代码封装到一个工厂类中。并采用 枚举 来表示不同的迭代算法类型，同时将 集合类作为参数传入，由工厂根据不同的枚举值，返回对应算法的迭代器实现。

至此可以给出迭代器模式的全貌。

classDiagram
    direction LR
    class Iterator {
        << interface >>
        +hasNext(): boolean
        +next(): E
    }

    class IterableCollection {
        << interface >>
        +createIterator(): Iterator
    }

    class ConcreteCollection {
        -items: E[]
        -size: int
        +createIterator(): Iterator
        +get(index: int): E
        +size(): int
    }

    class ConcreteIterator {
        -collection: ConcreteCollection
        -cursor: int
        +hasNext(): boolean
        +next(): E
    }
    
    class client
    
    IterableCollection <|-- ConcreteCollection
    Iterator <|-- ConcreteIterator
    ConcreteCollection --> ConcreteIterator
    client --> Iterator
    client --> IterableCollection

Java中的迭代器模式

在实际开发中，好像没有专门编码过迭代器模式。但其实大部分Java开发程序员已经在无形中频繁使用迭代器模式了，例如我们在Java中使用增强for循环。

List<String> list = Arrays.asList("A", "B", "C");

// 增强 for 循环（for-each）
for (String item : list) {
    System.out.println(item);
}

但这种写法实际是编译器提供的一种语法糖，底层会被转换为使用 Iterator的普通for循环。

List<String> list = Arrays.asList("A", "B", "C");
Iterator<String> iterator = list.iterator(); // 获取迭代器
while (iterator.hasNext()) {
    String item = iterator.next(); // 取出元素
    System.out.println(item);
}

集合允许被增强for循环遍历，需要集合实现Java.lang.Iterable。这个Iterable接口，对应的是上文提到的集合接口IterableCollection。在Java中更常见的是Java.util.Collection接口，而Collection接口扩展了Iterable接口。

至此可以给出上文提到的迭代器模式概念和Java中的迭代器模式的关系。

迭代器模式概念	Java中的迭代器模式
迭代器接口	Java.util.Iterator
具体迭代器	Java.util.ArrayList.Itr等
集合接口	Java.lang.Iterable、Java.util.Collection
具体集合	Java.util.ArrayList等

由于Java标准库已经为几乎所有集合实现了迭代器模式，集合框架功能非常完善，覆盖了大部分遍历需求。因此作为Java开发者，很少需要自己手动实现迭代器模式。

此外，一些看似实现在集合类中的遍历算法，例如forEach方法，可能最终也会调用迭代器的遍历算法。

// java.lang.Iterable
default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}

总结

1. 迭代器模式可以用一种统一且简单的方式遍历集合，而不用关心集合具体是怎么存储的。
2. 迭代器接口通常包含next和hasNext方法。
3. 获取迭代器的方法通常由集合类提供。