我们学习了ArrayList和LinkedList容器实现了迭代器,学习了迭代器的原理 实现 设计意图,迭代器模式主要就是解耦容器代码和遍历容器.其实大部分的设计模式都是为了解耦代码
那么,如果在迭代器遍历集合的同时 增加和删除集合中的元素,会发生什么情况呢?会如何应对呢?
使用迭代器来遍历集合元素的同时 增加或者删除元素,会导致这个元素被重复遍历或者遍历不到,不过,并非所有的情况下都会出错,也可能有正常的情况出现,所以无法确定是否真正的出现异常,这种行为被称为 结果不可预期行为或者未决行为,视情况而定
那么为何,在迭代器中进行遍历时候,增加或者删除
| public class Demo {
public static void main(String[] args) { List<String> names = new ArrayList<>(); names.add(“a”); names.add(“b”); names.add(“c”); names.add(“d”); Iterator<String> iterator = names.iterator(); iterator.next(); names.remove(“a”); } } |
在执行完成add之后,集合内部有着4个元素,而且在第一次next的时候,指向了b
但是如果这时候remove了a,会导致指向b的指向了c的游标,导致只能遍历到了c,d两个元素,b遍历不到了
但是,如果删除的不是前面的元素 a或者当前指向的元素b,而是c d,就没有什么问题了
也就是视情况而定
在遍历的时候删除元素,会导致某个元素遍历不到,如果添加元素,会怎么样呢?
我们将删除元素改为添加元素
| public class Demo {
public static void main(String[] args) { List<String> names = new ArrayList<>(); names.add(“a”); names.add(“b”); names.add(“c”); names.add(“d”); Iterator<String> iterator = names.iterator(); iterator.next(); names.add(0, “x”); } } |
在执行完成add之后,数组中包含了a b c d四个元素,然后next后,游标指向了b,然后第一位处添加了一个元素,导致a b c d都后移了一位,导致元素重新指向了 a,也就是a被遍历了两次
同理,在后面添加元素,不会出现任何的问题,所以添加元素也有着不可预期的行为
如何应对遍历时候改变集合导致的未决行为
当通过迭代器去遍历集合的时候,对于删除和增加这两个未决行为,如果不去限制,是不会出现bug的,也就是一些隐藏很深,很难debug的问题的原因所在,为此我们要解决这个问题,有两种解决方案
(1)遍历的时候不能删除或者修改元素,(2)修改后,再遍历直接报错
第一种实现起来很难,无法去明确的得知开始遍历和结束遍历的事件,如果将创建迭代器的时间作为了开始时间,遍历结束的时间无法去确定,虽然可以将遍历到最后一个元素作为结束点,但是往往遍历并不是每次都遍历到最后一个,我们可能找到了一个值为x的元素后就停止了遍历
那么,或者实现一个结束方法,在每次停止遍历的时候,调用这个结束方法?
这也不靠谱,因为万一又一次没有调用,就麻烦了,而且也增加了开发成本,很容易去漏掉
使用起来可能如下
| public class Demo {
public static void main(String[] args) { List<String> names = new ArrayList<>(); names.add(“a”); names.add(“b”); names.add(“c”); names.add(“d”); Iterator<String> iterator = names.iterator(); while (iterator.hasNext()) { String name = iterator.currentItem(); if (name.equals(“b”)) { iterator.finishIteration();//主动告知容器这个迭代器用完了 break; } } } } |
所以,我们一般去使用第二种的解决方案,让增删后,遍历出错,Java采用的亦是如此
具体的实现是,在ArrayList中添加一个成员变量 modCount,记录了修改次数,每次修改都会增加1
那么再常见吊带器的时候,就会将这个modCount值传递给这个迭代器中作为一个成员变量,每次调用遍历操作,都会检查是否有别人改变过这个modCount,如果有了改变,就说明了存储的元素已经改变了,要么增加了元素,要么删除了元素,之前的迭代器已经不能正确的运行了,所以直接抛出异常,使用了fail-fast解决方式,抛出了运行时异常
上面的思路这样总结为如下的代码:
| public class ArrayIterator implements Iterator {
private int cursor; private ArrayList arrayList; private int expectedModCount; public ArrayIterator(ArrayList arrayList) { this.cursor = 0; this.arrayList = arrayList; this.expectedModCount = arrayList.modCount; } @Override public boolean hasNext() { checkForComodification(); return cursor < arrayList.size(); } @Override public void next() { checkForComodification(); cursor++; } @Override public Object currentItem() { checkForComodification(); return arrayList.get(cursor); } private void checkForComodification() { if (arrayList.modCount != expectedModCount) throw new ConcurrentModificationException(); } } //代码示例 public class Demo { public static void main(String[] args) { List<String> names = new ArrayList<>(); names.add(“a”); names.add(“b”); names.add(“c”); names.add(“d”); Iterator<String> iterator = names.iterator(); iterator.next(); names.remove(“a”); iterator.next();//抛出ConcurrentModificationException异常 } } |
那么,如何在遍历的时候安全的删除一个元素呢?
其实在Java提供的Iterator方法中,还提供了一个remove()方法,可以在遍历集合的时候,删除集合的元素,虽然迭代器理论上只是遍历元素的,将删除放在迭代器中不合适,但是提供了就去看看吧
其实内部实现很简单,就是删除游标指向的前一个元素,而且一个next(),只能对应一个remove操作,调用多了会报错
| public class Demo {
public static void main(String[] args) { List<String> names = new ArrayList<>(); names.add(“a”); names.add(“b”); names.add(“c”); names.add(“d”); Iterator<String> iterator = names.iterator(); iterator.next(); iterator.remove(); iterator.remove(); //报错，抛出IllegalStateException异常 } } |
现在,看一下,是这么删除的集合的元素的
| public class ArrayList<E> {
transient Object[] elementData; private int size; public Iterator<E> iterator() { return new Itr(); } private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; Itr() {} public boolean hasNext() { return cursor != size; } @SuppressWarnings(“unchecked”) public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } } } |
可以看出,新增加了一个lastRet成员变量,用于记录游标指向的前一个元素,通过删除这个元素的时候,我们将其重置为了-1,二次删除直接报错,导致只能删除一次
重点回顾
在通过迭代器去遍历集合元素的时候,增加或者删除集合中的元素,可能导致某个元素被重复遍历或者遍历不到,但是并非,所有的情况都会遍历出错,有时候可能也正常遍历,这就是未决行为
而为了避免未决问题,我们常见的就方案就是,让遍历的时候无法进行修改,或者修改后再次遍历,直接报错,我们使用的是第二种解决方案,遍历时候修改过再操作直接报错
课后思考
1.文章给出的Java迭代器的实现代码,如果一个容器对象同时创建了两个迭代器,一个迭代器调用了remove删除了集合中一个元素,那么另一个迭代器是否还可以用?
2.LinkedList底层是基于链表的,进行增删的话,会出现什么不可预期的行为吗?
1.实现中,remove方法中,会在调用集合的remove方法后,将当前的修改量赋值到这个迭代器的内部的修改量属性上,但是对于其他迭代器调用的remove无法感知,自然无法修改本迭代器内部的修改量属性,导致next()会在调用checkForComodification()函数的时候发生报错
2.LinkedList,在增删的时候,由于双向链表的特性,只能感知到上一位和下一位,所以并不会导致异常情况的发生