设计模式之美
王争
前Google工程师,《数据结构与算法之美》专栏作者
立即订阅
21708 人已学习
课程目录
已更新 73 讲 / 共 102 讲
0/6登录后,你可以任选6讲全文学习。
开篇词 (1讲)
开篇词 | 一对一的设计与编码集训,让你告别没有成长的烂代码!
免费
设计模式学习导读 (3讲)
01 | 为什么说每个程序员都要尽早地学习并掌握设计模式相关知识?
02 | 从哪些维度评判代码质量的好坏?如何具备写出高质量代码的能力?
03 | 面向对象、设计原则、设计模式、编程规范、重构,这五者有何关系?
设计原则与思想:面向对象 (11讲)
04 | 理论一:当谈论面向对象的时候,我们到底在谈论什么?
05 | 理论二:封装、抽象、继承、多态分别可以解决哪些编程问题?
06 | 理论三:面向对象相比面向过程有哪些优势?面向过程真的过时了吗?
07 | 理论四:哪些代码设计看似是面向对象,实际是面向过程的?
08 | 理论五:接口vs抽象类的区别?如何用普通的类模拟抽象类和接口?
09 | 理论六:为什么基于接口而非实现编程?有必要为每个类都定义接口吗?
10 | 理论七:为何说要多用组合少用继承?如何决定该用组合还是继承?
11 | 实战一(上):业务开发常用的基于贫血模型的MVC架构违背OOP吗?
12 | 实战一(下):如何利用基于充血模型的DDD开发一个虚拟钱包系统?
13 | 实战二(上):如何对接口鉴权这样一个功能开发做面向对象分析?
14 | 实战二(下):如何利用面向对象设计和编程开发接口鉴权功能?
设计原则与思想:设计原则 (12讲)
15 | 理论一:对于单一职责原则,如何判定某个类的职责是否够“单一”?
16 | 理论二:如何做到“对扩展开放、修改关闭”?扩展和修改各指什么?
17 | 理论三:里式替换(LSP)跟多态有何区别?哪些代码违背了LSP?
18 | 理论四:接口隔离原则有哪三种应用?原则中的“接口”该如何理解?
19 | 理论五:控制反转、依赖反转、依赖注入,这三者有何区别和联系?
20 | 理论六:我为何说KISS、YAGNI原则看似简单,却经常被用错?
21 | 理论七:重复的代码就一定违背DRY吗?如何提高代码的复用性?
22 | 理论八:如何用迪米特法则(LOD)实现“高内聚、松耦合”?
23 | 实战一(上):针对业务系统的开发,如何做需求分析和设计?
24 | 实战一(下):如何实现一个遵从设计原则的积分兑换系统?
25 | 实战二(上):针对非业务的通用框架开发,如何做需求分析和设计?
26 | 实战二(下):如何实现一个支持各种统计规则的性能计数器?
设计原则与思想:规范与重构 (11讲)
27 | 理论一:什么情况下要重构?到底重构什么?又该如何重构?
28 | 理论二:为了保证重构不出错,有哪些非常能落地的技术手段?
29 | 理论三:什么是代码的可测试性?如何写出可测试性好的代码?
30 | 理论四:如何通过封装、抽象、模块化、中间层等解耦代码?
31 | 理论五:让你最快速地改善代码质量的20条编程规范(上)
32 | 理论五:让你最快速地改善代码质量的20条编程规范(中)
33 | 理论五:让你最快速地改善代码质量的20条编程规范(下)
34 | 实战一(上):通过一段ID生成器代码,学习如何发现代码质量问题
35 | 实战一(下):手把手带你将ID生成器代码从“能用”重构为“好用”
36 | 实战二(上):程序出错该返回啥?NULL、异常、错误码、空对象?
37 | 实战二(下):重构ID生成器项目中各函数的异常处理代码
设计原则与思想:总结课 (3讲)
38 | 总结回顾面向对象、设计原则、编程规范、重构技巧等知识点
39 | 运用学过的设计原则和思想完善之前讲的性能计数器项目(上)
40 | 运用学过的设计原则和思想完善之前讲的性能计数器项目(下)
设计模式与范式:创建型 (7讲)
41 | 单例模式(上):为什么说支持懒加载的双重检测不比饿汉式更优?
42 | 单例模式(中):我为什么不推荐使用单例模式?又有何替代方案?
43 | 单例模式(下):如何设计实现一个集群环境下的分布式单例模式?
44 | 工厂模式(上):我为什么说没事不要随便用工厂模式创建对象?
45 | 工厂模式(下):如何设计实现一个Dependency Injection框架?
46 | 建造者模式:详解构造函数、set方法、建造者模式三种对象创建方式
47 | 原型模式:如何最快速地clone一个HashMap散列表?
设计模式与范式:结构型 (8讲)
48 | 代理模式:代理在RPC、缓存、监控等场景中的应用
49 | 桥接模式:如何实现支持不同类型和渠道的消息推送系统?
50 | 装饰器模式:通过剖析Java IO类库源码学习装饰器模式
51 | 适配器模式:代理、适配器、桥接、装饰,这四个模式有何区别?
52 | 门面模式:如何设计合理的接口粒度以兼顾接口的易用性和通用性?
53 | 组合模式:如何设计实现支持递归遍历的文件系统目录树结构?
54 | 享元模式(上):如何利用享元模式优化文本编辑器的内存占用?
55 | 享元模式(下):剖析享元模式在Java Integer、String中的应用
设计模式与范式:行为型 (14讲)
56 | 观察者模式(上):详解各种应用场景下观察者模式的不同实现方式
57 | 观察者模式(下):如何实现一个异步非阻塞的EventBus框架?
58 | 模板模式(上):剖析模板模式在JDK、Servlet、JUnit等中的应用
59 | 模板模式(下):模板模式与Callback回调函数有何区别和联系?
60 | 策略模式(上):如何避免冗长的if-else/switch分支判断代码?
61 | 策略模式(下):如何实现一个支持给不同大小文件排序的小程序?
62 | 职责链模式(上):如何实现可灵活扩展算法的敏感信息过滤框架?
63 | 职责链模式(下):框架中常用的过滤器、拦截器是如何实现的?
64 | 状态模式:游戏、工作流引擎中常用的状态机是如何实现的?
65 | 迭代器模式(上):相比直接遍历集合数据,使用迭代器有哪些优势?
66 | 迭代器模式(中):遍历集合的同时,为什么不能增删集合元素?
67 | 迭代器模式(下):如何设计实现一个支持“快照”功能的iterator?
68 | 访问者模式(上):手把手带你还原访问者模式诞生的思维过程
69 | 访问者模式(下):为什么支持双分派的语言不需要访问者模式?
不定期加餐 (3讲)
加餐一 | 用一篇文章带你了解专栏中用到的所有Java语法
加餐二 | 设计模式、重构、编程规范等相关书籍推荐
春节特别加餐 | 王争:如何学习《设计模式之美》专栏?
免费
设计模式之美
登录|注册

67 | 迭代器模式(下):如何设计实现一个支持“快照”功能的iterator?

王争 2020-04-06
上两节课,我们学习了迭代器模式的原理、实现,并且分析了在遍历集合的同时增删集合元素,产生不可预期结果的原因以及应对策略。
今天,我们再来看这样一个问题:如何实现一个支持“快照”功能的迭代器?这个问题算是对上一节课内容的延伸思考,为的是帮你加深对迭代器模式的理解,也是对你分析、解决问题的一种锻炼。你可以把它当作一个面试题或者练习题,在看我的讲解之前,先试一试自己能否顺利回答上来。
话不多说,让我们正式开始今天的学习吧!

问题描述

我们先来介绍一下问题的背景:如何实现一个支持“快照”功能的迭代器模式?
理解这个问题最关键的是理解“快照”两个字。所谓“快照”,指我们为容器创建迭代器的时候,相当于给容器拍了一张快照(Snapshot)。之后即便我们增删容器中的元素,快照中的元素并不会做相应的改动。而迭代器遍历的对象是快照而非容器,这样就避免了在使用迭代器遍历的过程中,增删容器中的元素,导致的不可预期的结果或者报错。
接下来,我举一个例子来解释一下上面这段话。具体的代码如下所示。容器 list 中初始存储了 3、8、2 三个元素。尽管在创建迭代器 iter1 之后,容器 list 删除了元素 3,只剩下 8、2 两个元素,但是,通过 iter1 遍历的对象是快照,而非容器 list 本身。所以,遍历的结果仍然是 3、8、2。同理,iter2、iter3 也是在各自的快照上遍历,输出的结果如代码中注释所示。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《设计模式之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(32)

  • LJK
    思考题感觉像是数据库的MVCC?
    - 容器中维护一个每个迭代器创建时间的列表
    - 每次有迭代器创建时就在这个列表中加入自己的创建时间
    - 迭代器迭代完成后将列表中对应时间点删除
    - 清理容器时,对于容器中每个元素,如果addTime小于这个列表中的最小时间点就可以进行删除
    2020-04-06
    4
    6
  • 辣么大
    课后思考题:类似数组动态扩容和缩容,删除元素时可以比较被删除元素的总数,在被删除元素总数 < 总数的 1/2 时, 进行resize数组,清空被删除的元素,回收空间。
    2020-04-06
    1
    5
  • 辉哥
    课堂讨论:可以创建一个object类型的常量,删除数组元素时,可以将被删除数组元素的引用指向该常量。Android中的SparseArray就是采用此方式实现的
    2020-04-07
    4
  • Monday
    在阅读本节代码实现就想到了第二种方案存在类似思考题的问题
    解决方案可以在合适的时候清理带删除标记的元素。本想使用数据库的多版本控制(MVCC)的方案,把所有的迭代器对象存起来,并添加创建时间。但是冒出一个新问题,数据库事务有commit来表示事务已完成,而迭代器的使用完成无法知晓,还在思考方案中……
    2020-04-06
    4
  • eason2017
    定时清理里面的数据,做一次同步。期间可能会加锁来保证数据的有效性。
    2020-04-06
    2
  • smartjia
    感觉代码有两个小问题,若理解有误,请帮指正:

    问题1. 重复删除同一个元素时,actualSize 应该保持不变。
    以下是修改后的代码:
    @Override
    public void remove(E obj)
    {
     for (int i = 0; i < totalSize; ++i) {
     if (elements[i].equals(obj) && delTimestamps[i] == Long.MAX_VALUE) { // 防止重复删除
     delTimestamps[i] = System.currentTimeMillis();
     actualSize--; }
     }
    }

    问题2: 遍历完一个元素后需要让 cursorInAll 自增,否则 cursorInAll 一直指向第一个待遍历的元素。同时hasNext() 恒为true, 也需要修改。
    以下是修改后的代码:

    @Override
    public E next() {
     E currentItem = arrayList.get(cursorInAll);
     cursorInAll++; //自增,否则 cursorInAll 一直不变
     justNext();
     return currentItem;
    }

    @Override
    public boolean hasNext() {
          return this.leftCount >= 0; // 注意是>=, 而非> ( 修改后 leftCount >= 0 恒成立, 总是返回 true)
          改为:
          return cursorInAll < arrayList.totalSize();
    }
    2020-04-07
    1
  • 守拙
    课堂讨论:
    在调用List#iterator()之前, 删除deltimestamp < 当前时间的元素.
    2020-04-07
    1
  • 马以
    记录一个迭代变量,每迭代一次,计数加一,迭代完一次减一,当为0的时候就可以删除标记为delete的元素了
    2020-04-06
    1
  • 马以
    是的,这个是和数据库的事务隔离差不多,老师这里用的是时间戳,我们还可以利用一个自增的序列号来控制,都是一样的;
    2020-04-06
    1
  • Ken张云忠
    在集合增加一个数组field,专门用来记录引用该元素的迭代器个数,当迭代器个数为0且该元素已经标记为删除元素时才真正的删除元素,当需要迭代器使用者在使用完迭代器后需要显示得调用迭代器注销该元素的函数,对于使用者不太友好了。
    2020-04-06
    1
  • webmin
    可以参考GC的算法,弄一个减化版的优化方法:
    1. 被删除的元素是否还有可能被已经创建的iterator所访问,即被删除的元素还被引用着;(iterator使用完需要有调用关闭动作)
    2. 被删除的元素达到一定量时,按照删除时间清理掉效早删除的元素,清理掉的最晚的被删除元素的删除时间放置在清理标识字段,iterator迭代时检查清理标识字段,如果iterator创建时间早于清理标识字段中的时间丢出异常;
    2020-04-06
    1
    1
  • 筱乐乐哦
    老师,有个问题:你在文章中说到:让容器既支持快照遍历,又支持随机访问?我们可以在 ArrayList 中存储两个数组。一个支持标记删除的,用来实现快照遍历功能;一个不支持标记删除的(也就是将要删除的数据直接从数组中移除),用来支持随机访问
    如果是这样操作,那和浅拷贝的那个比较,没发现有优势呀,老师可以说下这块吗
    2020-04-06
    1
    1
  • Jxin
    1.给元素打时间截实现快照,空间成本会比较大。这里其实采用复制状态机一样能起到效果,只是空间成本就变成了时间成本。

    2.至于栏主的课后题,这已经是从实现快照,变成快照操作在多线程可见了。那么当前的实现是不严谨的,并发会有数据不符合预期的情况。

    3.不考虑并发问题,仅看如何释放内存这个问题。复制状态机可以将一段时间的log整合,实现快照往前移动(比如redis)。放在这里也一样,定时对元素做整合,将被删除的元素移除即可。(遗憾的时,基于时间截这种,无法在某个快照(状态),结合log,做往后倒退的操作)
    2020-04-06
    2
    1
  • 子豪sirius
    第二个问题,我想可不可用个数组记录当前有多少个迭代器。每调用一次iterrator方法,迭代器加一;有元素删除时,记录这个时间点的迭代器的数量;当迭代器访问到该元素时,减一,减到0,说明不再有删除该元素时间点之前生成的迭代器来访问了,就可以实际删除该元素。
    2020-04-06
    1
  • 徐凯
    容器可以放指向元素的指针,当不用时直接将指针释放并置为空
    2020-04-06
    1
  • zj
    我有个想法,当迭代器创建后,容器元素如果被删除了,则在迭代器创建强引用指向这个容器元素,容器中元素将之前元素的强引用变为弱引用。
     当迭代器不再使用后,会被gc掉,从而删除的元素只剩下弱引用了,那下一次gc,这个删除的元素就会被gc掉。
    2020-04-06
    1
  • 秋风画扇
    容器维护一个最早迭代器创建时间lastIterator,可以用一个线程定期清理delTime < lastIterator的元素。

    为了提升性能,也可以不用定期扫描。在对集合进行遍历的时候顺带删除
    2020-04-11
  • www.xnsms.com小鸟接码
    感觉迭代器模式在工作中没什么应用场景啊
    2020-04-09
  • 岁月
    有好多算法题想了很久都没想出来, 很打击信心的呀........而且一般能想出来的解法, 代码都基本能写出来, 而写具体的代码要消耗很多时间, 还是挺难抉择的, 我之前学的数据结构和算法, 就基本把全部涉及到的代码都自己实现一遍.花了好几个月....不过后来还是忘记了..........
    2020-04-08
  • 岁月
    思考题
    在容器类里面使用一个计数, 标记当前迭代器被创建了多少个, 然后在迭代器内存要被释放的时候, 对容器的计数-1, 每次迭代器被创建的时候, 计数+1; 当计数=0的时候, 容器就负责把那个快照数组整个都删除掉
    2020-04-08
收起评论
32
返回
顶部