概述
前两篇文章,学习了迭代器模式的原理、实现,并分析了在遍历集合的同时增删元素集合,产生不可预期结果的原因及应对策略。
本章,再来看这样一个问题: 如何实现一个支持 “快照” 功能的迭代器?
这个问题算是上一篇文章内容的延升思考,为的是帮助你加深对迭代器模式的理解。
问题描述
先介绍下问题的背景:如何实现一个支持 “快照” 功能的迭代器?
理解这个问题的关键是理解 “快照”。 所谓 “快照” ,指我们为容器创建迭代器时,相当于给容器拍了一张快照(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();
如果让你实现上面的功能?你会如何做?
下面是针对这个功能需求的骨架代码,其中包含 ArrayList
、SnapshotArrayIterator
两个类。对于这两个类,文章只定义了几个关键接口,你可以自行尝试完善下,然后再看下面的讲解。
public class ArrayList<E> implements List<E> {// 成员变量、私有属性...@Overridepublic void add(E e) {// ...}@Overridepublic void remove(E e) {// ...}@Overridepublic Iterator<E> iterator() {return null;}
}public class SnapshotArrayIterator<E> implements Iterator<E> {// 成员变量、私有属性...@Overridepublic boolean hasNext() {// ...}@Overridepublic E next() {// ...}}
解决方案一
先看最简单的一种解决办法。在迭代器类中定义一个成员变量 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);}@Overridepublic boolean hasNext() {return cursor < snapshot.size();}@Overridepublic E next() {E currentItem = snapshot.get(cursor);cursor++;return currentItem;}
}
这种解决方式虽然简单,但代价也有点高。每次创建迭代器时,都要拷贝一份数据到快照中,会增加内存的消耗。如果一个容器同时有多个迭代器正在遍历元素,就会导致数据在内存中重复存储多分。不过,庆幸的是,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;}@Overridepublic void add(E e) {elements[totalSize] = e;addTimestamps[totalSize] = System.currentTimeMillis();delTimestamps[totalSize] = Long.MAX_VALUE;totalSize++;actualSize++;}@Overridepublic 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;}@Overridepublic 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(); // 先跳到这个迭代器快照的第一个元素}@Overridepublic boolean hasNext() {return this.leftCount >= 0;}@Overridepublic 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++;}}
}
实际上,上面的解决方案相当于解决了一个问题,又引入另一个问题。 ArrayList
底层依赖数组这种数据结构,原本可以支持快速地随机查询,在 O(1)
时间复杂内获取下标为 i 的元素,但现在,删除数据并非真正的删除,只是通过时间戳来标记,这就导致无法支持按照下标快速随机访问了。
那如何让容器既支持快照遍历,又支持随机访问呢?
解决的方法也不难。我们可以在 ArrayList
中存储两个数组。一个支持标记删除,用来实现快照遍历功能;一个不支持标记删除,用来支持随机访问(也就是将要删除的数据直接从数组中删除)。具体的代码就不实现了,感兴趣的话,可以自己实现下。