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

SystemDesign 迭代器模式

创建时间:2020-07-24 14:30

字数:1.5k 阅读:

评论:

1. 迭代器模式的原理和实现
2. 实现支持快照功能的iterator

1. 迭代器模式的原理和实现

迭代器模式
- Iterator Design Pattern / Cursor Design Patten
- 用来遍历集合对象
- 编程语言基本上都将迭代器作为一个基础类库来提供了
- 集合对象指的是一个容器，而迭代器需要迭代的对象实际上是一组对象的对象
- 迭代器模式将集合对象的遍历操作从集合类当中拆分出来，放到迭代器类当中，使得二者的职责更加单一

涉及部分
- 容器
  - 接口
  - 实现类
- 容器迭代器
  - 接口
  - 实现类

1.1 实现一个线性结构容器的迭代器

// 接口定义方式一
public interface Iterator<E> {
  boolean hasNext();
  void next();
  E currentItem();
}

// 接口定义方式二
public interface Iterator<E> {
  boolean hasNext();
  E next();
}

定义方式一的好处在可以多次获得当前的对象，会更加灵活

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();
    }
  }
}

这里一个问题是还需要new ArrayIterator()，我们可以通过在List的接口当中定义迭代器，然后再ArrayList的类当中定义一个iterator()方法。然后在使用的时候，我们就可以通过实例化以后的容器，比如ArrayList，直接来调用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();
    }
  }
}

实现方式/ 设计思路
- 迭代器当中实现
  - hasNext()
  - currentItem()
  - next()
- 待遍历的容器
  - 通过依赖注入传递到迭代器当中
  - 容器通过iterator()方法来创建迭代器

1.2 为什么需要迭代器模式来遍历集合？

复杂数据结构遍历方式也会非常复杂，比如对于树，对于图来说。我们将遍历的方式定义到迭代器当中，这样就避免了要自己实现这样复杂的操作了。
通过迭代器模式，可以同时创建多个不同的迭代器，对同一个容器进行遍历而不互相影响
容器和迭代器都提供了抽象的接口，当我们需要改变遍历算法的时候，对代码的影响会很小，只在依赖注入处使用新的迭代器类所提供的算法即可

1.3 遍历时的增删

遍历时进行增删很大的一个问题是数组在做了增删以后，其他元素的位置会随之改变的。这样就会出现在迭代器当中有些元素无法迭代到的问题了

遍历时增删是会产生不可预期的遍历错误的，可以通过对遍历时候增删元素的限制来解决这个问题

遍历的时候不允许增删元素
- 比较难以实现
增删元素之后让遍历报错
- 在ArrayList当中定义一个成员变量modCount
  - 记录集合被修改的次数
  - 集合每调用一次增加或删除元素的函数，就会加1
  - 当调用集合上的iterator()函数创建迭代器的时候，将modCount值传递给迭代器的expectedModCount成员变量
  - 然后在每次调用迭代器上的函数的时候，都会检查一下modCount是否改变过

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

2. 实现支持快照功能的iterator

快照
- 为容器创建迭代器的时候，给容器拍的快照
- 使得即便我们之后增删容器中的元素，快照中的元素并不会做相应的变动
- 这样迭代器使用的对象是快照，而不是容器，这样就避免了在使用迭代器遍历的过程中，因为增删容器中的元素而导致的不可预期的结果或报错。

可以在迭代器类当中定义一个成员变量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;
  }
}

可以在容器当中为每个元素保存两个时间戳
- addTimestamp
- delTimestamp
- 当元素被加入到集合当中的时候，addTimestamp设置为当前时间，将delTimestamp设置成最大长整形值。当元素被删除时，将delTimestamp更新为当前时间，表示已经被删除
- 每个迭代器也保存一个迭代器创建时间戳 snapshotTimestamp
  - 只有满足addTimestamp < snapshotTimestamp < delTimestamp，才是属于这个迭代器的快照

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 stone2paul@gmail.com