设计模式之美
王争
前 Google 工程师,《数据结构与算法之美》专栏作者
123425 人已学习
新⼈⾸单¥98
登录后,你可以任选6讲全文学习
课程目录
已完结/共 113 讲
设计模式与范式:行为型 (18讲)
设计模式之美
15
15
1.0x
00:00/00:00
登录|注册

66 | 迭代器模式(中):遍历集合的同时,为什么不能增删集合元素?

LinkedList底层基于链表的不可预期行为
多个迭代器同时操作集合
限制:只能删除游标指向的前一个元素
Java迭代器的remove()方法
fail-fast解决方式
增删元素后让遍历报错
遍历时不允许增删元素
遍历过程中添加元素
遍历过程中删除元素
ArrayList迭代器实现
有时运行正确,有时运行错误
遍历过程中增删元素可能导致元素重复遍历或遍历不到
应用设计模式的主要目的是解耦
解耦容器代码和遍历代码
课堂讨论
安全地删除集合元素
如何应对未决行为
示例代码
结果不可预期行为
迭代器模式
遍历集合的同时增删元素

该思维导图由 AI 生成,仅供参考

上一节课中,我们通过给 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");
}
}
我们知道,ArrayList 底层对应的是数组这种数据结构,在执行完第 55 行代码的时候,数组中存储的是 a、b、c、d 四个元素,迭代器的游标 cursor 指向元素 a。当执行完第 56 行代码的时候,游标指向元素 b,到这里都没有问题。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入探讨了在遍历集合时增删元素可能带来的不可预期问题,并提出了解决方案。在遍历过程中增删元素可能导致某些元素被重复遍历或遍历不到,这种行为称为未决行为。文章指出Java语言采用fail-fast解决方式,即在遍历时检查集合的修改次数,如果发生了修改则抛出ConcurrentModificationException异常。此外,文章还详细解释了迭代器的remove()方法如何安全地删除集合元素,并通过代码示例展示了其实现原理。最后,文章提出了课堂讨论问题,引发读者思考。整体而言,本文对于理解迭代器模式的原理和设计意图具有很好的指导意义。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《设计模式之美》
新⼈⾸单¥98
立即购买
登录 后留言

全部留言(35)

  • 最新
  • 精选
  • 小晏子
    思考题: 1. iterator1 和 iterator2是两个不同的迭代器对象,修改一个不会影响另外一个,所以执行iterator1.remove()后,再执行iterator2.next时,会执行checkForComodification();检查,可是检查条件“arrayList.modCount != expectedModCount”中arrayList的modCount已经变成了5,而此时iterator2的expectedModCount还是4,所以触发ConcurrentModificationException异常。 2. LinkedList和ArrayList不同是LinkedList底层基于链表实现,增加删除元素不需要移动元素的位置,所以不会出现跟ArrayList不同的情况,比如增加元素时,不论增加的元素时在迭代器前还是后,都能通过指针寻址到下一个元素。
    2020-04-03
    13
    81
  • kyle
    迭代器中删除元素那一段,执行完第57行(删除a以后),游标应该指向c,图中指向d了
    2020-04-03
    6
    21
  • Ken张云忠
    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异常. 都不支持迭代器里添加元素.
    2020-04-03
    4
    18
  • 1.ConcurrentModificationException是在调用迭代器的next方法时产生,因为迭代器2并没有使用,所以不会报错,如果在第13行调用的是iterator2.next()则会报错(原因:expectedModCount在新建迭代器的时候初始化,调用iterator1.remove()只修改iterator1的expectedModCount,不会修改iterator2的,所以在调用iterator2.next()时会报错) 2.使用迭代器遍历的同时,使用容器的方法进行增删操作也会触发ConcurrentModificationException,行为和ArrayList是一样的 我有一个问题想问老师,我是培训班出身,而且学历不好,自觉基础不行,所以从工作以来,基本每天都坚持学习,如今已经工作一年多了.可是我每天学习两三个钟头就觉得很累了,脑子像浆糊一样,没办法继续学新东西了,有时学习一整天,从上班开始学,一直学到下班,下班的时候感觉脑子都要扭曲了,好长时间缓解不过来,前几天听说去哪网的前端架构师去世了,年龄才30岁出头,我感觉我保持当下这个状态的话,到不了他的水平就得猝死,我想知道老师是怎么平衡日常生活的?真的有人能坚持每天学习十几个小时吗?这让我觉得特别累,喘不过气来
    2020-04-03
    13
    15
  • 忆水寒
    第一个问题,由于modcount不一样了,所以会出现异常。 第二个问题,LinkedList和ArrayList行为一致。
    2020-04-05
    6
  • Jackie
    终于明白报ConcurrentModificationException的真正原因了
    2020-04-03
    5
  • Monday
    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不一致了。
    2020-04-03
    4
  • Liam
    1 第二个迭代器会报错,modCount发生变化 2 链表增删不影响游标,不会出现意外
    2020-04-03
    4
  • xzy
    看了ArrayList和LinkedList的源码,来回答思考题: 1,会抛出 ConcurrentModificationException 异常 2,添加元素分为两种情况:添加元素在游标前、添加元素在游标后 游标前:nextIndex = next元素实际的下标 - 1,所以hasNext()函数在next()返回链表的最后一个元素后仍然成立 游标后:无影响 删除元素也分为三种情况:删除元素在游标前、删除元素在游标后、删除游标元素 游标前:nextIndex = next元素的实际下标 + 1,所有hasNext()函数在next()返回链表末尾第二个元素后便不在成立 游标后:无影响 删除游标元素:访问当前游标元素后面的元素时会报空指针异常 /** * LinkedList 迭代器的部分源码 * / private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } }
    2020-04-14
    3
  • 东征
    问题一,因为每个iterator都会保留自己的expectModCount,而modCount是全局的,所以会抛错。 问题二,因为底层实现是链表,所以若在游标前新增删除,会导致整体遍历漏处理或多处理。在游标上删除,导致后面的内容无法遍历。在游标后新增删除无影响
    2020-04-09
    3
收起评论
显示
设置
留言
35
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部