如何实现一个支持“快照”功能的迭代器？

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

方案一

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
    }
}

缺点：这个解决方案虽然简单，但代价也有点高。每次创建迭代器的时候，都要拷贝一份数据到快 照中，会增加内存的消耗。如果一个容器同时有多个迭代器在遍历元素，就会导致数据在内 存中重复存储多份。不过，庆幸的是，Java 中的拷贝属于浅拷贝，也就是说，容器中的对 象并非真的拷贝了多份，而只是拷贝了对象的引用而已。

方案二

我们可以在容器中，为每个元素保存两个时间戳，一个是添加时间戳 addTimestamp，一 个是删除时间戳 delTimestamp。

当元素被加入到集合中的时候，我们将 addTimestamp 设置为当前时间，将 delTimestamp 设置成最大长整型值。当元素被删除时，我们将 delTimestamp 更新为当前时间，表示已经被删除。

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

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

可以将元素删除时间以及创建时间与迭代器的创建时间进行比较，来判断该元素是否是当前快照中的元素，这样就在不复制的情况下做到了快照，同时因为删除是标记删除，也不会造成影响，而且添加新的元素也不会被遍历到。

参考

《设计模式之美》