迭代器模式(中):遍历集合的同时,为什么不能增删集合元素?
# 66 | 迭代器模式(中):遍历集合的同时,为什么不能增删集合元素?
上一节课中,我们通过给ArrayList、LinkedList容器实现迭代器,学习了迭代器模式的原理、实现和设计意图。迭代器模式主要作用是解耦容器代码和遍历代码,这也印证了我们前面多次讲过的应用设计模式的主要目的是解耦。
上一节课中讲解的内容都比较基础,今天,我们来深挖一下,如果在使用迭代器遍历集合的同时增加、删除集合中的元素,会发生什么情况?应该如何应对?如何在遍历的同时安全地删除集合元素?
话不多说,让我们正式开始今天的内容吧!
# 在遍历的同时增删集合元素会发生什么?
在通过迭代器来遍历集合元素的同时,增加或者删除集合中的元素,有可能会导致某个元素被重复遍历或遍历不到。不过,并不是所有情况下都会遍历出错,有的时候也可以正常遍历,所以,这种行为称为结果不可预期行为或者未决行为,也就是说,运行结果到底是对还是错,要视情况而定。
怎么理解呢?我们通过一个例子来解释一下。我们还是延续上一节课实现的ArrayList迭代器的例子。为了方便你查看,我把相关的代码都重新拷贝到这里了。
public interface Iterator<E> {
boolean hasNext();
void next();
E currentItem();
}
public class ArrayIterator<E> implements Iterator<E> {
private int cursor;
private ArrayList<E> arrayList;
public ArrayIterator(ArrayList<E> arrayList) {
this.cursor = 0;
this.arrayList = arrayList;
}
@Override
public boolean hasNext() {
return cursor < arrayList.size();
}
@Override
public void next() {
cursor++;
}
@Override
public E currentItem() {
if (cursor >= arrayList.size()) {
throw new NoSuchElementException();
}
return arrayList.get(cursor);
}
}
public interface List<E> {
Iterator iterator();
}
public class ArrayList<E> implements List<E> {
//...
public Iterator iterator() {
return new ArrayIterator(this);
}
//...
}
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");
}
}
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
我们知道,ArrayList底层对应的是数组这种数据结构,在执行完第55行代码的时候,数组中存储的是a、b、c、d四个元素,迭代器的游标cursor指向元素a。当执行完第56行代码的时候,游标指向元素b,到这里都没有问题。
为了保持数组存储数据的连续性,数组的删除操作会涉及元素的搬移(详细的讲解你可以去看我的另一个专栏《数据结构与算法之美》)。当执行到第57行代码的时候,我们从数组中将元素a删除掉,b、c、d三个元素会依次往前搬移一位,这就会导致游标本来指向元素b,现在变成了指向元素c。原本在执行完第56行代码之后,我们还可以遍历到b、c、d三个元素,但在执行完第57行代码之后,我们只能遍历到c、d两个元素,b遍历不到了。
对于上面的描述,我画了一张图,你可以对照着理解。
不过,如果第57行代码删除的不是游标前面的元素(元素a)以及游标所在位置的元素(元素b),而是游标后面的元素(元素c和d),这样就不会存在任何问题了,不会存在某个元素遍历不到的情况了。
所以,我们前面说,在遍历的过程中删除集合元素,结果是不可预期的,有时候没问题(删除元素c或d),有时候就有问题(删除元素a或b),这个要视情况而定(到底删除的是哪个位置的元素),就是这个意思。
在遍历的过程中删除集合元素,有可能会导致某个元素遍历不到,那在遍历的过程中添加集合元素,会发生什么情况呢?还是结合刚刚那个例子来讲解,我们将上面的代码稍微改造一下,把删除元素改为添加元素。具体的代码如下所示:
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");
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
在执行完第10行代码之后,数组中包含a、b、c、d四个元素,游标指向b这个元素,已经跳过了元素a。在执行完第11行代码之后,我们将x插入到下标为0的位置,a、b、c、d四个元素依次往后移动一位。这个时候,游标又重新指向了元素a。元素a被游标重复指向两次,也就是说,元素a存在被重复遍历的情况。
跟删除情况类似,如果我们在游标的后面添加元素,就不会存在任何问题。所以,在遍历的同时添加集合元素也是一种不可预期行为。
同样,对于上面的添加元素的情况,我们也画了一张图,如下所示,你可以对照着理解。
# 如何应对遍历时改变集合导致的未决行为?
当通过迭代器来遍历集合的时候,增加、删除集合元素会导致不可预期的遍历结果。实际上,“不可预期”比直接出错更加可怕,有的时候运行正确,有的时候运行错误,一些隐藏很深、很难debug的bug就是这么产生的。那我们如何才能避免出现这种不可预期的运行结果呢?
有两种比较干脆利索的解决方案:一种是遍历的时候不允许增删元素,另一种是增删元素之后让遍历报错。
实际上,第一种解决方案比较难实现,我们要确定遍历开始和结束的时间点。遍历开始的时间节点我们很容易获得。我们可以把创建迭代器的时间点作为遍历开始的时间点。但是,遍历结束的时间点该如何来确定呢?
你可能会说,遍历到最后一个元素的时候就算结束呗。但是,在实际的软件开发中,每次使用迭代器来遍历元素,并不一定非要把所有元素都遍历一遍。如下所示,我们找到一个值为b的元素就提前结束了遍历。
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")) {
break;
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
你可能还会说,那我们可以在迭代器类中定义一个新的接口finishIteration(),主动告知容器迭代器使用完了,你可以增删元素了,示例代码如下所示。但是,这就要求程序员在使用完迭代器之后要主动调用这个函数,也增加了开发成本,还很容易漏掉。
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;
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
实际上,第二种解决方法更加合理。Java语言就是采用的这种解决方案,增删元素之后,让遍历报错。接下来,我们具体来看一下如何实现。
怎么确定在遍历时候,集合有没有增删元素呢?我们在ArrayList中定义一个成员变量modCount,记录集合被修改的次数,集合每调用一次增加或删除元素的函数,就会给modCount加1。当通过调用集合上的iterator()函数来创建迭代器的时候,我们把modCount值传递给迭代器的expectedModCount成员变量,之后每次调用迭代器上的hasNext()、next()、currentItem()函数,我们都会检查集合上的modCount是否等于expectedModCount,也就是看,在创建完迭代器之后,modCount是否改变过。
如果两个值不相同,那就说明集合存储的元素已经改变了,要么增加了元素,要么删除了元素,之前创建的迭代器已经不能正确运行了,再继续使用就会产生不可预期的结果,所以我们选择fail-fast解决方式,抛出运行时异常,结束掉程序,让程序员尽快修复这个因为不正确使用迭代器而产生的bug。
上面的描述翻译成代码就是下面这样子。你可以结合着代码一起理解我刚才的讲解。
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异常
}
}
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
# 如何在遍历的同时安全地删除集合元素?
像Java语言,迭代器类中除了前面提到的几个最基本的方法之外,还定义了一个remove()方法,能够在遍历集合的同时,安全地删除集合中的元素。不过,需要说明的是,它并没有提供添加元素的方法。毕竟迭代器的主要作用是遍历,添加元素放到迭代器里本身就不合适。
我个人觉得,Java迭代器中提供的remove()方法还是比较鸡肋的,作用有限。它只能删除游标指向的前一个元素,而且一个next()函数之后,只能跟着最多一个remove()操作,多次调用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异常
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
现在,我们一块来看下,为什么通过迭代器就能安全的删除集合中的元素呢?源码之下无秘密。我们来看下remove()函数是如何实现的,代码如下所示。稍微提醒一下,在Java实现中,迭代器类是容器类的内部类,并且next()函数不仅将游标后移一位,还会返回当前的元素。
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();
}
}
}
}
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
在上面的代码实现中,迭代器类新增了一个lastRet成员变量,用来记录游标指向的前一个元素。通过迭代器去删除这个元素的时候,我们可以更新迭代器中的游标和lastRet值,来保证不会因为删除元素而导致某个元素遍历不到。如果通过容器来删除元素,并且希望更新迭代器中的游标值来保证遍历不出错,我们就要维护这个容器都创建了哪些迭代器,每个迭代器是否还在使用等信息,代码实现就变得比较复杂了。
# 重点回顾
好了,今天的内容到此就讲完了。我们一块来总结回顾一下,你需要重点掌握的内容。
在通过迭代器来遍历集合元素的同时,增加或者删除集合中的元素,有可能会导致某个元素被重复遍历或遍历不到。不过,并不是所有情况下都会遍历出错,有的时候也可以正常遍历,所以,这种行为称为结果不可预期行为或者未决行为。实际上,“不可预期”比直接出错更加可怕,有的时候运行正确,有的时候运行错误,一些隐藏很深、很难debug的bug就是这么产生的。
有两种比较干脆利索的解决方案,来避免出现这种不可预期的运行结果。一种是遍历的时候不允许增删元素,另一种是增删元素之后让遍历报错。第一种解决方案比较难实现,因为很难确定迭代器使用结束的时间点。第二种解决方案更加合理。Java语言就是采用的这种解决方案。增删元素之后,我们选择fail-fast解决方式,让遍历操作直接抛出运行时异常。
像Java语言,迭代器类中除了前面提到的几个最基本的方法之外,还定义了一个remove()方法,能够在遍历集合的同时,安全地删除集合中的元素。
# 课堂讨论
- 基于文章中给出的 Java 迭代器的实现代码,如果一个容器对象同时创建了两个迭代器,一个迭代器调用了 remove() 方法删除了集合中的一个元素,那另一个迭代器是否还可用?或者,我换个问法,下面代码中的第 13 行的运行结果是什么?
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> iterator1 = names.iterator();
Iterator<String> iterator2 = names.iterator();
iterator1.next();
iterator1.remove();
iterator2.next(); // 运行结果?
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- LinkedList 底层基于链表,如果在遍历的同时,增加删除元素,会出现哪些不可预期的行为呢?
欢迎留言和我分享你的想法。如果有收获,欢迎你把这篇文章分享给你的朋友。
# 精选评论
点击查看
思考题:
1. iterator1 和 iterator2是两个不同的迭代器对象,修改一个不会影响另外一个,所以执行iterator1.remove()后,再执行iterator2.next时,会执行checkForComodification();检查,可是检查条件“arrayList.modCount != expectedModCount”中arrayList的modCount已经变成了5,而此时iterator2的expectedModCount还是4,所以触发ConcurrentModificationException异常。
2. LinkedList和ArrayList不同是LinkedList底层基于链表实现,增加删除元素不需要移动元素的位置,所以不会出现跟ArrayList不同的情况,比如增加元素时,不论增加的元素时在迭代器前还是后,都能通过指针寻址到下一个元素。
2
3
关于问题2 LinkedList的思考,既然LinkedList是基于链表实现,那在前or后新增删除元素都不会涉及到数据整体的搬移,也就不会出现数据遗漏或者重复处理的情况,咋一看在原集合进行增删操作不会对迭代器的遍历产生影响,那为何LinkedList在有迭代器实例的情况下不允许在原集合进行增删操作呢?源码中hasNext是通过nextIndex < size来判断是否还有元素,在新增删除的情况下对size都有改变;从集合前面删除元素,size减小,迭代器中尾部部分元素无法遍历到;从集合前面新增元素,size增大,迭代器尾部元素hasNext判断中,返回true 但实际已没有可遍历的元素
hpublic 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> iterator1 = names.iterator();
Iterator<String> iterator2 = names.iterator();
iterator1.next();
iterator1.remove();
iterator1.next(); // 运行结果?
}
}
哈哈老师的题目笔误了吧。
运行结果那行应该是iterator2.next()。
然后结果应该是会抛异常,因为modifyCount不一致了。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1.ConcurrentModificationException是在调用迭代器的next方法时产生,因为迭代器2并没有使用,所以不会报错,如果在第13行调用的是iterator2.next()则会报错(原因:expectedModCount在新建迭代器的时候初始化,调用iterator1.remove()只修改iterator1的expectedModCount,不会修改iterator2的,所以在调用iterator2.next()时会报错)
2.使用迭代器遍历的同时,使用容器的方法进行增删操作也会触发ConcurrentModificationException,行为和ArrayList是一样的
我有一个问题想问老师,我是培训班出身,而且学历不好,自觉基础不行,所以从工作以来,基本每天都坚持学习,如今已经工作一年多了.可是我每天学习两三个钟头就觉得很累了,脑子像浆糊一样,没办法继续学新东西了,有时学习一整天,从上班开始学,一直学到下班,下班的时候感觉脑子都要扭曲了,好长时间缓解不过来,前几天听说去哪网的前端架构师去世了,年龄才30岁出头,我感觉我保持当下这个状态的话,到不了他的水平就得猝死,我想知道老师是怎么平衡日常生活的?真的有人能坚持每天学习十几个小时吗?这让我觉得特别累,喘不过气来
2
3
4
第一个问题,由于modcount不一样了,所以会出现异常。
第二个问题,LinkedList和ArrayList行为一致。
2
1.基于文章中给出的 Java 迭代器的实现代码,如果一个容器对象同时创建了两个迭代器,一个迭代器调用了 remove() 方法删除了集合中的一个元素,那另一个迭代器是否还可用?或者,我换个问法,下面代码中的第 13 行的运行结果是什么?
Exception in thread "main" java.util.ConcurrentModificationException
因为iterator2.expectedModCount的值与names.modCount的值不相等,expectedModCount比modCount小1.
2.LinkedList 底层基于链表,如果在遍历的同时,增加删除元素,会出现哪些不可预期的行为呢?
当在游标及游标之前增删元素时会使有的元素遍历不到;当在游标之后增删元素时无问题.
LinkedList与ArrayList一样,因为都是集成抽象类java.util.AbstractList,
在遍历的同时调用两次remove()都会抛出异常,都会抛出的是java.lang.IllegalStateException异常.
两个迭代器遍历的同时,其中一个迭代器删除元素都会使另一个迭代器抛出java.util.ConcurrentModificationException异常.
都不支持迭代器里添加元素.
2
3
4
5
6
7
8
9
10
小争哥后面是不是还有门系统设计的课,要是再有这门课,我觉得就此生无憾了。答应我,一定要出,好不好?
老师的题目是不是
iterator1.next();
iterator1.remove();
iterator2.next(); // 运行结果?
如果是iterator1,能正常运行;
如果是iterator2.next();就报错了
2
3
4
5
6
不会报错
1、会报错。虽然迭代器自身的没有变,但是arraylist的变了,导致不相等,因此会仍然报错。
1、会存在未觉行为。例如新增的元素在cursor之前会遍历不到新增的元素,假如情况2,新增的元素恰好在当前cursor之后所指的元素,也遍历不到新增的元素,如果不考虑新增的元素后续不再遍历的话,增加元素就不存在未觉行为。删除的元素为cursor所指的元素时,后续元素遍历不到。为了统一增加和删除,应该是会报错。具体待查看代码验证。
2
`基于文章中给出的 Java 迭代器的实现代码,如果一个容器对象同时创建了两个迭代器,一个迭代器调用了 remove() 方法删除了集合中的一个元素,那另一个迭代器是否还可用?或者,我换个问法,下面代码中的第 13 行的运行结果是什么?`
后调用remove的迭代器会出错,即iterator2.next()会抛出ConcurrentModificationException异常
2
`LinkedList 底层基于链表,如果在遍历的同时,增加删除元素,会出现哪些不可预期的行为呢`
1. 增加元素:如果在当前元素之前添加新元素,那么新增的元素不会被遍历到;如果在当前元素之后添加元素则会被遍历到,存在未决行为。
2. 删除元素:如果删除当前元素之前的元素,那么这个被删除的元素其实之前已经被遍历过了;如果是删除当前元素之后的元素,则被删除元素将不会被遍历到;如果正好是删除当前元素,那么当前元素之后的元素将不会被遍历到,同样存在未决行为。
2
3
1、因为modCount和expectModCount不一致,iterator2在遍历时会抛出异常; 2、如果是单链表,如果在游标对应的元素之前增加元素,可能会导致新增加的元素遍历不到;如果删除的恰好是游标对应的元素,可能会导致无效指针错误。
思考题1,会报错,iterator2中的 expectedModCount 是最开始的 4,而 names 中的 modCount 是 5,所以报错
1.基于文章中给出的 Java 迭代器的实现代码,如果一个容器对象同时创建了两个迭代器,一个迭代器调用了 remove() 方法删除了集合中的一个元素,那另一个迭代器是否还可用?或者,我换个问法,下面代码中的第 13 行的运行结果是什么?
Exception in thread "main" java.util.ConcurrentModificationException
因为iterator2.expectedModCount的值与names.modCount的值不相等,expectedModCount比modCount小1.
2.LinkedList 底层基于链表,如果在遍历的同时,增加删除元素,会出现哪些不可预期的行为呢?
LinkedList与ArrayList一样,因为都是集成抽象类java.util.AbstractList,
在遍历的同时调用两次remove()都会抛出异常,都会抛出的是java.lang.IllegalStateException异常.
两个迭代器遍历的同时,其中一个迭代器删除元素都会使另一个迭代器抛出java.util.ConcurrentModificationException异常.
都不支持迭代器里添加元素.
2
3
4
5
6
7
8
9
设计模式_66:
# 作业
1. (代码有错误: 13行应该是`iterator2.next()`), 在`checkForComodification`方法抛出异常。因为`iterator1`remove会导致`iterator2`的`expectedModCount`与集合的`modCount`就不一致。
2.
- 删除游标之前元素,会导致遍历了已删除的元素。
- 增加游标之前的元素,会导致新增元素不被遍历。
# 感想
对于“不可预期直接出错更加可怕”感触比较深,因为直接出错的问题一般会在自测(或单元测试)或提测后暴露出来,线上产品不会有问题。于是,“不可预期”的问题更多地会暴露在线上,最终牺牲了用户体验。
2
3
4
5
6
7
8
9
无论是ArrayList还是LinkedList,使用iterator的remove方法来remove元素后再遍历,都是不会报错的,使用list中的remove都会报错。因为expectedModCount != modCount
但是LinkedList删除元素,并不会移动后面的元素,所以不存在文中说的遍历不到的问题
2