原创

设计模式基础(十七)——迭代器模式

迭代器模式(Iterator Design Pattern ),也叫做游标模式,是一种行为型模式。 迭代器模式用来遍历集合对象。这里说的“集合对象”也可以叫“容器”“聚合对象”,实际上就是包含一组对象的对象,比如数组、链表、树、图、跳表。迭代器模式将集合对象的遍历操作从集合类中拆分出来,放到迭代器类中,让两者的职责更加单一。

一、基本原理

一个完整的迭代器模式一般会涉及容器和容器迭代器两部分内容。为了达到基于接口编程的目的,容器又包含容器接口、容器实现类,迭代器又包含迭代器接口、迭代器实现类。
对于迭代器模式,我画了一张简单的类图,你可以看一看,先有个大致的印象:



假设我们现在需要针对 ArrayList 和 LinkedList 两个线性容器,设计实现对应的迭代器。按照上面的类图,我们定义一个迭代器接口 Iterator,以及针对两种容器的具体迭代器实现类 ArrayIterator 和 ListIterator。

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(); //注意这里,cursor在指向最后一个元素的时候,hasNext()仍旧返回true。
  }

  @Override
  public void next() {
    cursor++;
  }

  @Override
  public E currentItem() {
    if (cursor >= arrayList.size()) {
      throw new NoSuchElementException();
    }
    return arrayList.get(cursor);
  }
}

客户端使用方式:

public class Demo {
  public static void main(String[] args) {
    ArrayList<String> names = new ArrayList<>();
    names.add("xzg");
    names.add("wang");
    names.add("zheng");

    Iterator<String> iterator = new ArrayIterator(names);
    while (iterator.hasNext()) {
      System.out.println(iterator.currentItem());
      iterator.next();
    }
  }
}

在上面的代码实现中,我们需要将容器对象,通过构造函数传递给迭代器类。为了封装迭代器的创建细节,我们可以在容器中定义一个 iterator() 方法,来创建对应的迭代器:

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("xzg");
    names.add("wang");
    names.add("zheng");

    Iterator<String> iterator = names.iterator();
    while (iterator.hasNext()) {
      System.out.println(iterator.currentItem());
      iterator.next();
    }
  }
}

二、迭代修改

如果在使用迭代器遍历集合的同时增加、删除集合中的元素,会发生什么情况?此时可能会导致某个元素被重复遍历或遍历不到。不过,并不是所有情况下都会遍历出错,有的时候也可以正常遍历,所以,这种行为称为结果不可预期,也就是说,运行结果到底是对还是错,要视情况而定。

“不可预期”比直接出错更加可怕,有的时候运行正确,有的时候运行错误,一些隐藏很深、很难 debug 的 bug 就是这么产生的。那我们如何才能避免出现这种不可预期的运行结果呢? 有两种方案:

  1. 遍历的时候不允许增删元素;
  2. 增删元素之后让遍历报错。

Java 语言就是采用的是第二种解决方案,增删元素之后,让遍历报错。 那么如何实现呢?基本的思路如下:

  1. 在集合中定义一个成员变量 modCount,记录集合被修改的次数,集合每调用一次增加或删除元素的函数,就会给 modCount 加 1;
  2. 当调用集合的 iterator() 函数来创建迭代器时,我们把 modCount 值传递给迭代器的 expectedModCount 成员变量;
  3. 每次调用迭代器上的 hasNext()、next()、currentItem() 函数,都检查集合上的 modCount 是否等于 expectedModCount,如果两个值不相同,那就说明集合存储的元素已经改变了,于是 fail-fast 抛出运行时异常,结束掉程序。

上面的描述翻译成代码就是下面这样子:

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异常
  }
}

Java 语言中的迭代器类定义了一个 remove() 方法,能够在遍历集合的同时,安全地删除集合中的元素。不过,这个方法比较鸡肋,只能删除游标指向的前一个元素,而且一个 next() 函数之后,只能跟着最多一个 remove() 操作,多次调用 remove() 操作会报错。 所以,最佳实践就是不要在遍历集合的过程中增删元素!

三、迭代快照

如果我们确实要在迭代的过程中增删元素,可以利用迭代器“快照”。
所谓快照(Snapshot),指为容器创建迭代器的时候,给容器拍了一张快照,之后即便我们增删容器中的元素,快照中的元素并不会做相应的改动。而迭代器遍历的对象是快照而非容器,这样就避免了在使用迭代器遍历的过程中,增删元素导致的不可预期结果。

3.1 方案一

我们先来看最简单的一种解决办法。在迭代器类中定义一个成员变量 snapshot 来存储快照。每当创建迭代器的时候,都拷贝一份容器中的元素到快照中,后续的遍历操作都基于这个迭代器自己持有的快照来进行。具体的代码实现如下所示:

public class SnapshotArrayIterator<E> implements Iterator<E> {
  private int cursor;
  private ArrayList<E> snapshot;

  public SnapshotArrayIterator(ArrayList<E> arrayList) {
    this.cursor = 0;
    this.snapshot = new ArrayList<>();
    this.snapshot.addAll(arrayList);
  }

  @Override
  public boolean hasNext() {
    return cursor < snapshot.size();
  }

  @Override
  public E next() {
    E currentItem = snapshot.get(cursor);
    cursor++;
    return currentItem;
  }
}

这个解决方案虽然简单,但代价也有点高。每次创建迭代器的时候,都要拷贝一份数据到快照中,会增加内存的消耗。如果一个容器同时有多个迭代器在遍历元素,就会导致数据在内存中重复存储多份。

3.2 方案二

我们可以在容器中,为每个元素保存两个时间戳:添加时间戳 addTimestamp、删除时间戳 delTimestamp。当元素被加入到集合中的时候,我们将 addTimestamp 设置为当前时间,将 delTimestamp 设置成最大长整型值(Long.MAX_VALUE);当元素被删除时,我们将 delTimestamp 更新为当前时间,表示已经被删除。

同时,每个迭代器也保存一个迭代器创建时间戳 snapshotTimestamp,也就是迭代器快照的创建时间戳。当使用迭代器来遍历容器的时候,只有满足addTimestamp < snapshotTimestamp && delTimestamp > snapshotTimestamp 的元素,才是属于这个迭代器的快照。

public class ArrayList<E> implements List<E> {
  private static final int DEFAULT_CAPACITY = 10;

  //不包含标记删除元素
  private int actualSize; 
  //包含标记删除元素
  private int totalSize; 

  private Object[] elements;
  private long[] addTimestamps;
  private long[] delTimestamps;

  public ArrayList() {
    this.elements = new Object[DEFAULT_CAPACITY];
    this.addTimestamps = new long[DEFAULT_CAPACITY];
    this.delTimestamps = new long[DEFAULT_CAPACITY];
    this.totalSize = 0;
    this.actualSize = 0;
  }

  @Override
  public void add(E obj) {
    elements[totalSize] = obj;
    addTimestamps[totalSize] = System.currentTimeMillis();
    delTimestamps[totalSize] = Long.MAX_VALUE;
    totalSize++;
    actualSize++;
  }

  @Override
  public void remove(E obj) {
    for (int i = 0; i < totalSize; ++i) {
      if (elements[i].equals(obj)) {
        delTimestamps[i] = System.currentTimeMillis();
        actualSize--;
      }
    }
  }

  public int actualSize() {
    return this.actualSize;
  }

  public int totalSize() {
    return this.totalSize;
  }

  public E get(int i) {
    if (i >= totalSize) {
      throw new IndexOutOfBoundsException();
    }
    return (E)elements[i];
  }

  public long getAddTimestamp(int i) {
    if (i >= totalSize) {
      throw new IndexOutOfBoundsException();
    }
    return addTimestamps[i];
  }

  public long getDelTimestamp(int i) {
    if (i >= totalSize) {
      throw new IndexOutOfBoundsException();
    }
    return delTimestamps[i];
  }
}

public class SnapshotArrayIterator<E> implements Iterator<E> {
  private long snapshotTimestamp;
  private int cursorInAll; // 在整个容器中的下标,而非快照中的下标
  private int leftCount; // 快照中还有几个元素未被遍历
  private ArrayList<E> arrayList;

  public SnapshotArrayIterator(ArrayList<E> arrayList) {
    this.snapshotTimestamp = System.currentTimeMillis();
    this.cursorInAll = 0;
    this.leftCount = arrayList.actualSize();;
    this.arrayList = arrayList;

    justNext(); // 先跳到这个迭代器快照的第一个元素
  }

  @Override
  public boolean hasNext() {
    return this.leftCount >= 0; // 注意是>=, 而非>
  }

  @Override
  public E next() {
    E currentItem = arrayList.get(cursorInAll);
    justNext();
    return currentItem;
  }

  private void justNext() {
    while (cursorInAll < arrayList.totalSize()) {
      long addTimestamp = arrayList.getAddTimestamp(cursorInAll);
      long delTimestamp = arrayList.getDelTimestamp(cursorInAll);
      if (snapshotTimestamp > addTimestamp && snapshotTimestamp < delTimestamp) {
        leftCount--;
        break;
      }
      cursorInAll++;
    }
  }
}

四、总结

迭代器模式主要用来遍历集合对象。 迭代器模式封装集合内部的复杂数据结构,开发者不需要了解如何遍历,直接使用容器提供的迭代器即可。

正文到此结束
本文目录