迭代器模式

概述

Iterator 迭代器模式提供一种顺序访问聚合对象中各元素的方法,同时不需要暴露该对象的内部表示。它也被视为 Cursor 模式。迭代器模式为遍历聚合对象提供了方法。基于迭代器模式,你可以实现具体的遍历操作。通常,Iterator 类定义了访问聚合对象的接口;iterator 保存了当前访问元素的引用。迭代器模式的简单示例如下:

将遍历机制 ListIterator 与迭代对象 List 分离,可以在迭代对象外围定义不同的遍历策略 Iterator 子类,无需在迭代对象中枚举它们。比如,FilteringListIterator 迭代器仅用于迭代满足特定过滤条件的元素。

迭代器和迭代对象是耦合的。对于不同类型的聚合对象,如 List、SkipList,SkipList 是一种类同于平衡树的概率数据结构。通常在 List、SkipList 上有 AbstractList 抽象类,抽象了操作列表的通用接口。List 的迭代器为 ListIterator,SkipList 的迭代器为 SkipListIterator,以实现不同的迭代机制。同样的,ListIterator、SkipListIterator 上有 AbstractIterator 抽象类,抽象了迭代器的通用接口。

在创建迭代器时,我们需要指定具体的迭代对象。通常,我们让迭代对象创建相关的迭代器,如迭代对象上挂有 createIterator 用于创建它相应的迭代器。createIterator 使用工厂方法。

结构

  • Iterator:定义访问和遍历元素的接口。
  • ConcreteIterator:实现 Iterator 接口,持有当前访问元素的引用。
  • Aggregate:定义创建 Iterator 的接口。
  • ConcreteAggregate:实现创建 ConcreteIterator 具体方法。

迭代器有多种实现方式。实现迭代器通常需要考虑以下问题:

  1. 迭代器分为内部迭代器和外部迭代器两类。内部迭代器指,客户端将一个要执行的操作交给内部迭代器,迭代器将该操作应用于聚合对象中的每个元素。外部迭代器指,客户端必须提前遍历聚合对象,并显式地请求 nextElement。
  2. 遍历算法可以由聚合对象实现,也可以由迭代器实现。如果在聚合对象内实现,聚合对象中会有游标指向当前访问的元素。如果遍历算法在迭代器中实现,那样就可以针对聚合对象使用不同的迭代算法。与此同时,如果迭代过程中需要访问聚合对象的私有变量,在迭代器中实现遍历算法也意味着过耦合。
  3. 迭代器的健壮性。迭代器的健壮性问题,指在遍历过程中,如果添加或删除元素,就会造成聚合对象中的一个元素可能被遍历多次或遍历零次。为避免这种问题,简单的方式是可以复制聚合对象,但这样做成本太高了。一个健壮的迭代器需要确保插入和删除不会干扰遍历,并且它不会复制聚合对象。保证健壮性的方法是,在添加或删除元素时,调整迭代器的内部状态,或者在内部维护信息以确保正确的遍历。
  4. 迭代器的最小接口包含 first、next、isDone、currentItem。对于已排序的聚合对象,previous 方法可以访问上一个元素。对于已排序的聚合对象或已添加索引的聚合对象,skipTo 可以定位到特定的元素。
  5. 多态迭代器可以由工厂方法创建,或者显式地调用具体迭代器。多态迭代器所需面对的问题是,我们需要显式地释放迭代器(即内存)。当迭代有多个退出点时,可能伴随的程序异常将永远不会释放迭代器内存。在这个问题上,可使用代理模式确保内存被正确释放。
  6. 通过迭代器子类实现对聚合对象中某些元素的特权访问。
  7. 对于复杂的嵌套结构(如树),使用外部迭代器通常会造成复杂的程序实现,使用内部迭代器可以简化问题。这种内部迭代器基于光标记录当前访问的节点,同时由节点接口移动到同级、父级或子级节点上。对于深度嵌套的数据结构,可使用不同的迭代器实现多种迭代方案,如前序、后序、有序和广度优先遍历等。
  8. 空迭代器,指 isDone 总返回 true 的迭代器。在树结构中,叶子节点可使用空迭代器,父节点可以实现为遍历子节点的迭代器。