重修设计模式-行为型-迭代器模式

ops/2024/10/25 15:28:17/

重修设计模式-行为型-迭代器模式

提供一种方法访问一个容器对象中各个元素，而又不需暴露该对象的内部细节。

迭代器模式（Iterator Pattern）将容器的遍历操作从容器类中拆分出来，放到迭代器类中，让两者的职责更加单一。容器对象的遍历与其内部表示分离，可以更好的支持对容器对象的多种遍历算法，并且可以在不修改容器对象本身的前提下增加新的遍历方式。

迭代器是用来遍历容器的，一个完整的迭代器模式包含容器和迭代器两部分内容。基于面向接口而非细节的编程思想，集合又分为容器接口、容器实现类；迭代器又包含迭代器接口、迭代器实现类，它们的关系如下所示：
在这里插入图片描述

迭代器角色介绍如下：

  1. 容器（Collection）：它持有一组对象，可以是一个列表、数组或其他数据结构。这个对象实现了一个创建迭代器（Iterator）的接口。
  2. 迭代器（Iterator）：它是一个定义了遍历集合元素的接口。迭代器对象从集合对象中获取元素，并遍历这些元素。迭代器的典型方法包括 hasNext()（判断是否有下一个元素）和 next()（返回下一个元素）。
  3. 具体容器（Concrete Collection）：它实现了容器接口，以存储和管理对象集合，并返回一个实现了迭代器接口的具体迭代器实例。
  4. 具体迭代器（Concrete Iterator）：它实现了迭代器接口，并持有对具体容器的引用，通过遍历集合中的元素来实现迭代器的核心方法。

大部分编程语言都提供了遍历容器的迭代器类，在平时开发中直接拿来用即可，不大可能从零编写一个迭代器，所以迭代器模式的应用场景也非常少见。不过为了理解迭代器模式的原理，还是举个例子，从头来实现迭代器模式。

例如，在开发中线性数据结构会经常使用，实现的方式又包括数组和链表，下面为这个容器来实现一个迭代器。

首先是容器部分，数组和链表对应 ArrayList 和 LinkedList 两个类。基于接口而非实现编程的思想，再从两个类中抽象出公共的接口 List，容器部分代码如下：

//容器接口
interface List<E> {//1.封装的迭代器方法fun iterator(): Iterator<E>	//2.容器相关的抽象方法fun add(e: E)fun remove(e: E)fun size(): Intfun get(index: Int): E
}//具体容器1
class ArrayList<E>(): List<E> {private val arrayList = java.util.ArrayList<E>()//3.返回对应的迭代器override fun iterator(): Iterator<E> {return ArrayListIterator(this)}override fun size(): Int {//...return arrayList.size}override fun get(index: Int): E {return arrayList.get(index)}override fun remove(e: E) {//...}override fun add(e: E) {//...}
}//具体容器2
class LinkedList<E>(): List<E> {//...
}

至此容器部分已经定义好了，接下来再定义迭代器部分。

//抽象迭代器
interface Iterator<E> {operator fun hasNext(): Booleanoperator fun next(): E?
}//ArrayList的具体迭代器
class ArrayListIterator<E>(val list: ArrayList<E>) : Iterator<E> {private var cursor = 0  //游标override fun hasNext(): Boolean {return cursor < list.size()}override fun next(): E? {if (cursor >= list.size()) {throw NoSuchElementException()}return list.get(cursor)}
}

至此一个完整的迭代器模式已经完整定义出来了，下面是调用方需要迭代容器元素时的代码：

fun main() {val arrayList = ArrayList<String>()arrayList.add("人生")arrayList.add("得意")arrayList.add("须尽欢")val iterator = arrayList.iterator()while (iterator.hasNext()) {val element = iterator.next()println("e:${element}")}
}
//输出：
人生
得意
须尽欢

以上就是迭代器的原理和代码实现。其实集合的遍历还可以通过 for 循环的方式，那么迭代器模式和 for 循环相比有哪些优势呢？

fun main() {//通过for循环遍历：for (i in 0 until list.size()) {println("e:${list.get(i)}")}
}

首先，对于类似数组和链表这样的数据结构，遍历方式比较简单，直接使用 for 循环来遍历就足够了。但是，对于复杂的数据结构（比如树、图）来说，有各种复杂的遍历方式。比如，树有前中后序、按层遍历；图有深度优先、广度优先遍历等等。如果由客户端代码来实现这些遍历算法，势必增加开发成本，且容易写错。如果将这部分遍历的逻辑写到容器类中，也会导致容器类代码的复杂性。

foreach 循环只是一个语法糖，底层是基于迭代器实现的。

所以面对复杂数据结构时，就需要使用迭代器模式，将容器代码和遍历代码进行解耦，将容器的遍历操作从容器类中拆分出来。比如，针对图的深度优先遍历和广度优先遍历，就可以定义 DFSIterator 和 BFSIterator 两个迭代器类来实现不同的遍历算法，在添加新的遍历算法时，只需要扩展新的迭代器类即可，非常符合开闭原则。而且每个迭代器独享自己的游标信息，就可以创建多个迭代器，同时对一个容器进行遍历。

至此我们可以总结出迭代器模式的优缺点：

优点：

  1. 职责分离：容器代码和遍历代码解耦，让两者职责更加单一，从而可以灵活的增加和修改遍历算法，符合开闭原则。
  2. 简化集合的遍历：迭代器提供了一个统一的接口来遍历集合对象，不需要调用者了解集合的内部结构。
  3. 使用灵活：迭代器之间相互独立，多个迭代器可同时遍历同一个容器。
  4. 安全性：由于集合对象的内部表示被封装起来，外部代码只能通过迭代器接口访问集合元素，这有助于保护集合对象的数据安全。

缺点：

  1. 增加复杂性：对于简单的集合，使用迭代器模式可能会增加额外的类和方法，从而增加代码的复杂性。
  2. 性能考虑：在某些情况下，使用迭代器可能比直接访问集合元素要慢，因为迭代器需要在每次调用 next() 方法时检查是否有下一个元素。

如何在迭代器中修改元素

通过迭代器来遍历集合元素的同时，如果增加或者删除集合中的元素，有可能会导致某个元素被重复遍历或遍历不到，也有可能正常遍历（运行结果的对错，要视情况而定），这种情况称为结果不可预期行为。

举个例子：

fun main() {val list = java.util.ArrayList<String>()list.add("a")list.add("b")list.add("c")list.add("d")val iterator = list.iterator()list.remove("b")println(iterator.next())
}

集合中存在 a、b、c、d 四个元素，在进行迭代器遍历时，如果其他地方删除了容器内的元素 b，此时对容器继续遍历就会产生不可预期的行为：正常遍历或漏掉某个元素。

原因是为了保持数组存储数据的连续性，数组的删除操作会涉及元素的搬移，从而导致迭代器中游标和数组元素不匹配了，流程如下：
在这里插入图片描述

同样，遍历过程中外部对容器添加元素也会造成未决行为：
在这里插入图片描述

虽然我们知道游标前删除或添加元素，会导致遍历漏掉或重复遍历元素；游标后删除或添加元素则遍历结果正常，但不知道的是外部会在什么时机对容器元素进行修改，所以是未决行为。

要解决迭代器遍历集合时，增加、删除集合元素导致的不可预期行为有两个方案：

  1. 迭代器遍历时，禁止增删元素（困难）
  2. 遵循fail-first思想，在增删元素之后立即让迭代器遍历报错，将错误尽早抛出（合理）

第一种解决方案比较难实现，需要确定遍历开始和结束的时间点。遍历开始的时间节点很容易获得，比如迭代器的创建时间。但遍历结束的时间点无法确认，毕竟存在遍历到一半就结束的情况，如果调用方主动通知结束遍历，又会增加调用成本，所以该方案pass。

第二种解决方案比较合理，Java 中的迭代器使用的就是该方案，增删元素后，让迭代器报错。具体实现步骤如下：

首先容器内维护一个成员变量 modCount，记录容器被修改的次数。每次容器增加或删除元素时候，都让 modCount + 1。其次迭代器也维护一个成员变量 expectedModCount，用来记录迭代器创建时，容器的修改次数。当通过 iterator() 函数创建迭代器时，将容器 modCount 赋值给迭代器 expectedModCount 变量，每次调用迭代器方法（如 hasNext()、next()）时，都校验一下当前容器的修改次数 modCount，是否等于迭代器创建时容器的修改次数 expectedModCount，也就是看迭代器创建后 modCount 是否修改过。如果两个值不同，则说明容器修改过了，迭代器继续运行会产生不可预期的结果，此时选择 fail-fast 方式，抛出异常，尽早终止迭代流程。

//容器：
class ArrayList<E>(): List<E> {var modCount: Int = 0  //1.记录容器修改次数...override fun remove(e: E) {modCount++//...}override fun add(e: E) {modCount++//...}
}//迭代器：
class ArrayListIterator<E>(val list: ArrayList<E>) : Iterator<E> {private var cursor = 0  //游标private var expectedModCount: Int = list.modCount  //2.记录初始修改次数override fun hasNext(): Boolean {checkForComodification()return cursor < list.size()}override fun next(): E? {checkForComodification()if (cursor >= list.size()) {throw NoSuchElementException()}return list.get(cursor)}//3.校验并抛出异常private fun checkForComodification() {if (list.modCount != expectedModCount) throw ConcurrentModificationException()}
}//调用时：
fun main() {val arrayList = ArrayList<String>()arrayList.add("人生")arrayList.add("得意")arrayList.add("须尽欢")val iterator = arrayList.iterator()arrayList.add("。")iterator.next() //报错：ConcurrentModificationException异常！
}

为什么 Java 的迭代器可以安全的删除元素？

在 Java 中，迭代器还定义了一个 remove() 方法，用于在遍历集合的同时，安全地删除集合中的元素。那么它是怎么做到的？下面分析一下 Java 迭代器的源码：

java">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 returnint lastRet = -1; // index of last element returned; -1 if no suchint 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();//1. 调用next时，cursor加1，lastRet被赋值为游标的上一个元素cursor = i + 1;return (E) elementData[lastRet = i];}public void remove() {if (lastRet < 0)	//3.调用remove后lastRet为-1，再调用就会抛出异常throw new IllegalStateException();checkForComodification();try {//2.删除时，只能删除游标的上一个元素，并将游标回退一个位置ArrayList.this.remove(lastRet);cursor = lastRet;lastRet = -1;expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}}
}

在上面的代码实现中，迭代器类新增了一个 lastRet 成员变量，用来记录游标指向的前一个元素。迭代器的 remove 方法也只能删除 lastRet 指向的元素。在删除这个元素时，会将迭代器的游标回退一位，从而避免游标前删除元素导致的某个元素遍历不到。流程如下：
在这里插入图片描述

分析源码后可以发现，虽然 Java 中的迭代器提供了删除方法，但使用上也有一定限制：只能删除游标指向的前一个元素，且一个 next() 函数之后，只能跟着最多一个 remove() 操作，多次调用 remove() 操作会报错。

至于 Java 为什么不提供增加元素的方法，个人觉得迭代器的主要作用毕竟是遍历，添加元素的逻辑放到迭代器里本来就不太合适。

总结

迭代器模式提供了一种方法，访问一个容器对象中各个元素，而又不需暴露该对象的内部细节。目的是将容器对象的遍历与其内部表示分离，可以更好的支持对容器对象的多种遍历算法，并且可以在不修改容器对象本身的前提下增加新的遍历方式。

迭代器模式工作原理如下：

  1. 创建容器对象：首先，创建一个具体容器对象，并添加一些元素。
  2. 获取迭代器：通过容器对象的迭代器创建方法（通常是 iterator()），获取一个具体迭代器对象。
  3. 遍历集合：使用迭代器对象的 hasNext() 方法检查是否还有元素可以遍历，如果有，则使用 next() 方法获取下一个元素，直到遍历完所有元素。

http://www.ppmy.cn/ops/128370.html

相关文章

在Nodejs中使用MySQL数据库

在Nodejs中使用MySQL数据库

简介 MySQL是一个关系型数据库管理系统&#xff0c;由瑞典MySQL AB公司开发&#xff0c;属于Oracle旗下产品。MySQL是最流行的关系型数据库管理系统之一&#xff0c;在WEB应用方面&#xff0c;MySQL是最好的RDBMS&#xff08;Relational Database Management System&#xff0…
阅读更多...
Rust编程语言变量的所有权（ownership）

Rust编程语言变量的所有权（ownership）

文章目录 什么是所有权所有权规则转让所有权变量与数据交互的方式(一):移动变量与数据交互的方式(二):克隆只在栈上的数据:拷贝所有权与函数返回值与作用域引用和借用可变引用悬垂引用（Dangling References）引用的规则什么是所有权 所有权（ownership）是Rust 的核心功能之一…
阅读更多...
执行Django项目的数据库迁移命令时报错：(1050, “Table ‘django_session‘ already exists“)；如何破？

执行Django项目的数据库迁移命令时报错：(1050, “Table ‘django_session‘ already exists“)；如何破？

一、问题描述&#xff1a; 当我们写Django时&#xff0c;由于自己的操作不当&#xff0c;导致执行数据库迁移命令时报错&#xff0c;报错的种类有很多&#xff0c;例如&#xff1a; 迁移文件冲突&#xff1a;可能你有多个迁移文件试图创建同一个表。数据库状态与迁移文件不同…
阅读更多...
OJ练习：判断环形链表、返回入环的第一个节点

OJ练习：判断环形链表、返回入环的第一个节点

目录 1. 判断环形链表1.1 判断环形链表拓展 2. 返回入环首节点解法一解法二 1. 判断环形链表 题目来自 141.环形链表 - 力扣&#xff08;LeetCode&#xff09; 解题思路&#xff1a;使用快慢指针。 定义一个慢指针slow指向头节点&#xff0c;每次向前走一步定义一个快指针fast指…
阅读更多...
使用 NumPy 和 Matplotlib 实现交互式数据可视化

使用 NumPy 和 Matplotlib 实现交互式数据可视化

使用 NumPy 和 Matplotlib 实现交互式数据可视化 在数据分析中&#xff0c;交互式可视化可以更好地帮助我们探索和理解数据。虽然 Matplotlib 是静态绘图库&#xff0c;但结合一些技巧和 Matplotlib 的交互功能&#xff08;widgets、event handlers&#xff09;&#xff0c;我…
阅读更多...
2000-2020年各地级市人类需求指数数据

2000-2020年各地级市人类需求指数数据

2000-2020年各地级市人类需求指数数据 1、年份&#xff1a;2000、2010、2020年 2、指标&#xff1a;城市名称、HMDI2000、HMDI2010、HMDI2020 3、范围&#xff1a;341个地级市 4、说明&#xff1a;各城市的人类需求指数项目旨在全面评估Z国城市居民在不同社会发展阶段对自然…
阅读更多...
前端性能优化之Canvas优化

前端性能优化之Canvas优化

元素是众多广泛使用的网络 2D 图像渲染标准之一。它被广泛用于游戏及复杂的图像可视化中。然而，随着网站和应用将 canvas 画布推至极限，性能开始成为问题。 Canvas 上下文切换 Canvas 绘制 API 都是在上下文context上进行调用，context不是一个普通的对象，当我们对其赋值的…
阅读更多...
苍穹外卖05

苍穹外卖05

redis 1. 启动redis .\redis-server.exe redis.windows.conf 2. 连接redis到客户端(这里我们使用ARDM图形化工具) 新建连接 一旦建立好后就永久直接可用(和mysql一个道理) 连接成功界面
阅读更多...
最新文章

Copyright @ 2022~2023