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

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

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

文章标题:设计模式-行为型-迭代器模式

文章字数:1.5k

本文作者:Leilei Chen

发布时间:2020-07-24, 14:30:04

最后更新:2020-08-24, 05:50:46

原始链接:https://www.llchen60.com/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F-%E8%A1%8C%E4%B8%BA%E5%9E%8B-%E8%BF%AD%E4%BB%A3%E5%99%A8%E6%A8%A1%E5%BC%8F/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏