阅读薄｜设计模式之美 设计模式与范例（行为迭代器模式）

这是我参与8月更文挑战的第5天，活动详情查看： 8月更文挑战

0x0、引言

???? 早上困困，啃下设计模式之美提提神，本文对应设计模式与范式：行为型(65-67)，迭代器模式 (Iterator Pattern)，又称 游标模式，用于 解耦容器代码和遍历代码。

不过，很多编程语言都将迭代器作为一个基础类库，直接提供出来了。日常业务开发，很少自己实现一个迭代器，当然，弄懂原理能帮助我们更好地使用这些工具类~

Tips：二手知识加工难免有所纰漏，感兴趣有时间的可自行查阅原文，谢谢。

---

0x1、定义

原始定义

迭代器提供一种对容器对象中各个元素进行访问的方法，而又不需要暴露该对象的内部细节。

定义很好理解，上构成该模式的四个角色：

• Iterator (抽象迭代器类) → 定义统一的迭代器方法hasNext()和next()，用于判断当前集合是否还有其他对象及按顺序读取集合中的当前对象；
• ConcreteIterator (具体迭代器) → 实现抽象迭代器声明的方法，处理具体集合对象中对对象位置的偏移及具体对象数据的传输；
• Container (抽象容器类) → 抽象及创建迭代器类关联的方法，同时可添加其他集合类需要的方法；
• ConcreteContainer (具体容器类) → 实现抽象容器类中声明的方法，创建对应具体的迭代器类；

其实就是两类角色：容器 和 迭代器，写个简单示例帮助理解~

0x2、写个简单例子

// 歌曲实体
public class Music {
    private String name;
    private String singer;
    private long createTime;

    public Music(String name, String singer, long createTime) {
        this.name = name;
        this.singer = singer;
        this.createTime = createTime;
    }

    public String getName() { return name; }
    public String getSinger() { return singer; }
    public long getCreateTime() { return createTime; }
    
    @Override
    public String toString() { 
        return "【" + name + "】- " + singer + " - " + createTime; 
    }
}

// 抽象迭代器
public interface Iterator {
    // 最基本的两个方法
    Music next();
    boolean hasNext();
    // 按需添加
    Music currentItem();
    Music first();
}

// 抽象容器
public interface Container {
    Iterator createIterator();
}

// 具体迭代器
public class ConcreteIterator implements Iterator {
    private Music[] musics;
    private int pos = 0;

    // 待遍历容器通过依赖注入传递到具体迭代器类中
    public ConcreteIterator(Music[] musics) { this.musics = musics; }

    @Override public Music next() { return musics[pos++]; }
    @Override public boolean hasNext() { return pos < musics.length; }
    @Override public Music currentItem() { return musics[pos]; }
    @Override public Music first() { return musics[0]; }
}

// 具体容器
public class ConcreteContainer implements Container {
    private Music[] musics;

    public ConcreteContainer(Music[] musics) { this.musics = musics; }

    @Override public Iterator createIterator() { return new ConcreteIterator(musics); }
}


// 测试用例
public class IteratorTest {
    public static void main(String[] args) {
        Music[] musics = new Music[5];
        musics[0] = new Music("We Sing. We Dance. We Steal Things.", "Jason Mraz", 20080513);
        musics[1] = new Music("Viva La Vida Death And All His Friends", "Coldplay", 20080617);
        musics[2] = new Music("华丽的冒险 ", "陈绮贞", 20050923);
        musics[3] = new Music("范特西 Fantasy", "周杰伦", 20010914);
        musics[4] = new Music("後。青春期的詩 后青春期的诗", "五月天", 20081023);
        Container container = new ConcreteContainer(musics);
        Iterator iterator = container.createIterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.currentItem());
            iterator.next();
        }
    }
}

代码运行结果如下：

代码非常简单：

• 具体迭代器实现next()、hasNext()方法；
• 待遍历容器对象通过依赖注入传递到迭代器中；
• 容器通过createIterator()方法创建迭代器；

你可能或说过度设计了，上面的遍历操作，自己通过 for循环 或 foreach循环 都可以实现。

的确如此，那为啥还要给容器设计对应的迭代器呢？三个原因：

• ① 复杂数据结构(如图、树)，有各种复杂的遍历方式(树的前中后序遍历、图的深广度优先遍历等)，如果让客户端来实现这些遍历算法，势必会增加开发成本，而且容易出错；
• ② 把遍历逻辑放容器类里无疑增加了容器类的复杂性，应对复杂性的方法就是 拆分，可把遍历操作拆分到迭代类中；
• ③ 每个迭代器独享游标信息，创建多个不同迭代器，同时对同一个容器遍历而不互相影响；

在举个例子，现在需要按照歌曲时间升序遍历，只需要实现一个迭代器类：

public class OrderTimeIterator implements Iterator {
    private final Music[] musics;
    private int pos;

    public OrderTimeIterator(Music[] musics) {
        this.musics = new Music[musics.length];
        System.arraycopy(musics, 0, this.musics, 0, musics.length);
        sortByTimeAsc(this.musics, 0, this.musics.length - 1);
        this.pos = 0;
    }

    // 快速排序
    private void sortByTimeAsc(Music[] arr, int low, int high) {
        if(low > high) return;
        int i = low;
        int j = high;
        Music temp;
        Music anchor = arr[low];
        while (i < j) {
            while (arr[j].getCreateTime() >= anchor.getCreateTime() && i < j) {
                j--;
            }
            while (arr[i].getCreateTime() <= anchor.getCreateTime() && i < j) {
                i++;
            }
            if(i < j) {
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        arr[low] = arr[i];
        arr[i] = anchor;
        sortByTimeAsc(arr, low, j -1);
        sortByTimeAsc(arr, j + 1, high);
    }
    ... // 其他实现方法同ConcreteIterator
}

具体容器类返回迭代器createIterator()方法，改成new OrderTimeIterator()即可，输出结果如下：

不懂快排的童鞋不需要了解具体细节，直接换迭代器即可，还可以按照自己的需求自定义迭代器，妙啊。

对了foreach循环语法糖，其实也是基于迭代器实现的，接着带出UML类图、使用场景和优缺点：

使用场景

• 希望对客户端隐藏遍历算法复杂性时；
• 需为容器(聚合)对象提供多种遍历方式时；

优点

• 满足单一职责原则和开闭原则；
• 更好的封装性，简化客户端调用，可以用不同的变量方式来遍历一个集合；

缺点

• 子类增加；
• 对于简单遍历，略显繁琐，如ArrayList直接用for循环+get()遍历即可；
• 抽象迭代器的设计难度大，需要充分考虑到系统将来的扩展，如JDK内置迭代器Iterator就无法实现逆向遍历。如果需要实现逆向遍历，只能通过其子类ListIterator等来实现，而ListIterator迭代器无法用于操作Set类型的聚合对象。在自定义迭代器时，创建一个考虑全面的抽象迭代器并不是件很容易的事情

---

0x3、加餐1：fail-first 快速机制

问题来了 → 当遍历的同时增删集合元素会怎么样？

答：可能会导致重复遍历或遍历不到某个元素。

是可能，并不会所有情况下都遍历出错，有时还可以正常遍历，这种行为称为 结果不可预期行为 或 未决行为，即运行的结果是对是错，得是情况而定。

比如原列表长度为5，迭代的时候插入了一个元素，但迭代器length还是之前的5，会漏掉新插入的元素； 又比如迭代时删掉了最后一个元素，但迭代器length还是之前的5，会引发数组越界；

如何应对这种遍历时改变集合导致的未决行为？

• ① 遍历时不允许增删元素；
• ② 遍历时增删元素直接报错；

方法一比较难实现，得确定遍历开始与结束的时间点，开始好拿(如创建迭代器时)，结束不好拿，因为遍历不一定把所有元素都走一遍，比如找到满足条件的元素，提前结束遍历。

在迭代器内定义一个接口finishIteration()，主动告知容器迭代器使用完毕，但这就要求调用者在使用完迭代器后要主动调用此函数，增加了开发成本之余还容易漏掉。

Java语言中采用的方法二，如ArrayList中定义了一个成员变量modCount，记录集合被修改的次数，调用增删函数都会加1。

创建迭代器的时候传入，然后每次调用迭代器的next()、hasNext()函数时都检查集合中的modCount是否等于一开始传入的modCount，不等说明集合存储的元素已经发生改变，之前创建的迭代器已不能正确运行，直接抛出运行时异常，结束程序。

另外，在单线程情况下，ArrayList使用迭代器进行迭代，通过迭代器增删元素，不会引发异常，原理是：

内部类Itr 实现Iterator接口，定义了两个变量cursor (下一个元素下标) 和 lastRet (上一个元素下标) 当发生元素增删时，更新迭代器中的游标及这两个值，保证遍历不出错。

而对于多线程的情况，除了在iterator使用处加锁外，还可以用 并发容器。

原理是：采用的是 fail-safe(安全失败) 机制：迭代时不是直接在集合内容*问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。所以遍历期间原集合发生的修改迭代器是不知道的，原迭代器也不能访问修改后的内容。Java的并发容器放在java.util.concurrent包中，如使用 CopyOnWriteArrayList 来代替ArrayList。

0x4、加餐2：实现一个支持快照功能的迭代器

所谓的 "快照" 就是创建迭代器时相当于给容器拍了张快照(Snapshot)，之后增删容器元素，快照中的元素都不会发生改变，即迭代器遍历的对象是快照而非容器。通过一个例子来解释这段话：

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
ListIterator<String> it1 = list.listIterator();
while (it1.hasNext()) System.out.print(it1.next()); // 输出: abcd

System.out.println();
list.remove("a");
ListIterator<String> it2 = list.listIterator();
while (it2.hasNext()) System.out.print(it2.next()); // 输出：bcd

System.out.println();
list.remove("c");
ListIterator<String> it3 = list.listIterator();
while (it3.hasNext()) System.out.print(it3.next()); // 输出：bd

第一种解法：迭代器类中定义一个存储快照的成员变量，构造迭代器时复制原集合引用进行初始化，后续遍历都基于持有的快照进行。(我上面定义的OrderTimeIterator就是这种)。

当然，缺点明显，每次创建迭代器，都要拷贝一份数据到快照中，增加内存消耗，当有多个迭代器在遍历元素，还会导致重复存储多份。不过，好在Java中的拷贝属于浅拷贝，所以只是拷贝了对象的引用而已。

第二种解法：容器中为每个元素保存两个时间戳，添加时间 及 删除时间 (初始化为最大长整型值)，添加时将添加时间设置为当前时间，删除时将时间设置为当前时间，记住只是 标记删除，并非真的从容器中将其删除。

然后每个迭代器保存一个 创建时间，即快照创建时间戳，当使用迭代器遍历容器时，只有满足：

添加时间 < 创建时间 < 删除时间

的元素才属于这个迭代器的快照：

• 添加时间 > 创建时间 → 说明元素在创建迭代器后才加入，不属于这个迭代器的快照；
• 删除时间 < 创建事件 → 说明元素在创建迭代器前就被删除了，同样不属于这个迭代器的快照；

在不拷贝容器的情况下，在容器本身借助时间戳实现快照功能，妙啊！

这种方式解决了一个问题，又引入了一个问题：

ArrayList底层依赖数组这种存储结构，原本支持快速随机访问，在O(1)时间复杂度内获取下标为i的元素。但现在删除元素并没有真正删除，这就导致无法支持按照下标快速随机访问了。

解法：

在ArrayList中存储两个数组，一个支持标记删除，用来实现快照遍历，一个不支持标记删除(删除数据直接从数组中删除)，用来支持随机访问。

---

以上内容就是本节的全部内容，谢谢~