设计模式学习笔记 - 设计模式与范式 -行为型：11.迭代器模式（下）：如何设计实现一个支持“快照”功能的Iterator

概述

前两篇文章，学习了迭代器模式的原理、实现，并分析了在遍历集合的同时增删元素集合，产生不可预期结果的原因及应对策略。

本章，再来看这样一个问题： 如何实现一个支持 “快照” 功能的迭代器？

这个问题算是上一篇文章内容的延升思考，为的是帮助你加深对迭代器模式的理解。

---

问题描述

先介绍下问题的背景：如何实现一个支持 “快照” 功能的迭代器？

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

接下来，通过一个例子来解释下。具体代码如下所示，容器 list 中初始存储了 3、8、2 三个元素。尽管在创建迭代器 iter1 之后，容器删除了元素 3，只剩剩下 8、2，但是，通过 iter1 遍历的对象是快照，而非容器 list 本身。所以，遍历的结果仍然是 3、8、2。同理，iter2、iter3 也是在各占的快照上遍历，输出的结果如注释所示。

List<Integer> list = new ArrayList<>();
list.add(3);
list.add(8);
list.add(2);

Iterator<Integer> iter1 = list.iterator(); // snapshot: 3,8,2
list.remove(3); // list: 8,2;
Iterator<Integer> iter2 = list.iterator(); // snapshot: 8,2
list.remove(2); // list: 8;
Iterator<Integer> iter3 = list.iterator(); // snapshot: 8

// 输出：3,8,2
while (iter1.hasNext()) {
    System.out.print(iter1.next() + " ");
}
System.out.println();

// 输出：8,2
while (iter2.hasNext()) {
    System.out.print(iter2.next() + " ");
}
System.out.println();

// 输出：8
while (iter3.hasNext()) {
    System.out.print(iter3.next() + " ");
}
System.out.println();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

如果让你实现上面的功能？你会如何做？

下面是针对这个功能需求的骨架代码，其中包含 ArrayList、SnapshotArrayIterator 两个类。对于这两个类，文章只定义了几个关键接口，你可以自行尝试完善下，然后再看下面的讲解。

public class ArrayList<E> implements List<E> {
    // 成员变量、私有属性...

    @Override
    public void add(E e) {
        // ...
    }

    @Override
    public void remove(E e) {
        // ...
    }

    @Override
    public Iterator<E> iterator() {
        return null;
    }
}

public class SnapshotArrayIterator<E> implements Iterator<E> {
    // 成员变量、私有属性...

    @Override
    public boolean hasNext() {
        // ...
    }

    @Override
    public E next() {
        // ...
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

解决方案一

先看最简单的一种解决办法。在迭代器类中定义一个成员变量 snapshot 来存储快照。每当创建迭代器的时候，都拷贝一份容器中的元素到快照中，后续的遍历操作都基于这个迭代自己持有的快照来进行。

public class SnapshotArrayIterator<E> implements Iterator<E> {
    private int cursor;
    private ArrayList<E> snapshot;

    public SnapshotArrayIterator(ArrayList<E> arrayList) {
        this.cursor = 0;
        this.snapshot = new ArrayList<>();
        this.snapshot.addAll(arrayList);
    }

    @Override
    public boolean hasNext() {
        return cursor < snapshot.size();
    }

    @Override
    public E next() {
        E currentItem = snapshot.get(cursor);
        cursor++;
        return currentItem;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这种解决方式虽然简单，但代价也有点高。每次创建迭代器时，都要拷贝一份数据到快照中，会增加内存的消耗。如果一个容器同时有多个迭代器正在遍历元素，就会导致数据在内存中重复存储多分。不过，庆幸的是，Java 中的拷贝属于浅拷贝，也就是说，容器中的对象并非真的拷贝了多份，而只是拷贝了对象的引用而已。关于深拷贝、浅拷贝，我们在《创建型：7.原型模式》中有详细的讲解，你可以回头去看一下。

解决方案二

可以在容器中，为每个元素保存两份时间戳，一个是添加时间戳 addTimestamp，一个是删除时间戳 delTimestamp。当元素被加入到集合中时，将 addTimestamp 设置问当前时间，将 delTimestamp 设置为 Long.MAX_VALUE。当元素被删除时，我们将 delTimestamp 更新为当前时间，表示已被删除。

注意，这里只是标记删除，而非真正将它从容器中删除。

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

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

这样就在不拷贝容器的情况下，在容器身上借助时间戳实现了快照的功能。具体的代码实现如下所示。注意，这里没有考虑 ArrayList 的扩容问题，感兴趣的话，可以自己完善一下。

public class ArrayList<E> implements List<E> {
    private static final int DEFAULT_CAPACITY = 10;

    private int actualSize; //不包含标记删除元素
    private int totalSize; // 包含标记删除元素

    private Object[] elements;
    private long[] addTimestamps;
    private long[] delTimestamps;

    public ArrayList() {
        this.elements = new Object[DEFAULT_CAPACITY];
        this.addTimestamps = new long[DEFAULT_CAPACITY];
        this.delTimestamps = new long[DEFAULT_CAPACITY];
        this.actualSize = 0;
        this.totalSize = 0;
    }

    @Override
    public void add(E e) {
        elements[totalSize] = e;
        addTimestamps[totalSize] = System.currentTimeMillis();
        delTimestamps[totalSize] = Long.MAX_VALUE;
        totalSize++;
        actualSize++;
    }

    @Override
    public void remove(E e) {
        for (int i = 0; i < totalSize; i++) {
            if (elements[i].equals(e)) {
                delTimestamps[i] = System.currentTimeMillis();
                actualSize--;
            }
        }
    }

    public int actualSize() {
        return actualSize;
    }

    public int totalSize() {
        return totalSize;
    }
    
    @Override
    public E get(int i) {
        if (i > totalSize) {
            throw new IndexOutOfBoundsException();
        }
        return (E)elements[i];
    }
    
    public long getAddTimestamp(int i) {
        if (i > totalSize) {
            throw new IndexOutOfBoundsException();
        }
        return addTimestamps[i];
    }

    public long getDelTimestamp(int i) {
        if (i > totalSize) {
            throw new IndexOutOfBoundsException();
        }
        return delTimestamps[i];
    }
}

public class SnapshotArrayIterator<E> implements Iterator<E> {
    private long snapshotTimestamp;
    private int cursorInAll; // 在整个容器中的下标，而非快照中的下标
    private int leftCount; // 快照中还有几个元素未被遍历
    private ArrayList<E> arrayList;

    public SnapshotArrayIterator(ArrayList<E> arrayList) {
        this.snapshotTimestamp = System.currentTimeMillis();
        this.cursorInAll = 0;
        this.leftCount = arrayList.actualSize();
        this.arrayList.addAll(arrayList);

        justNext(); // 先跳到这个迭代器快照的第一个元素
    }

    @Override
    public boolean hasNext() {
        return this.leftCount >= 0;
    }

    @Override
    public E next() {
        E currentItem = arrayList.get(cursorInAll);
        justNext();
        return currentItem;
    }

    private void justNext() {
        while (cursorInAll < arrayList.totalSize()) {
            long addTimestamp = arrayList.getAddTimestamp(cursorInAll);
            long delTimestamp = arrayList.getDelTimestamp(cursorInAll);
            if (snapshotTimestamp > addTimestamp && snapshotTimestamp < delTimestamp) {
                leftCount--;
                break;
            }
            cursorInAll++;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

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

那如何让容器既支持快照遍历，又支持随机访问呢？

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