10k

设计模式之美-课程笔记41-迭代器模式

Published on

迭代器模式

迭代器的优势比起直接遍历集合

迭代器模式的原理和实现

  1. 迭代器模式将集合对象的便利操作从集合类中拆分，放到迭代器类中，让两者职责更加单一。

  2. img

  3. 来实现一个迭代器

先定义一个接口

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

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

第二中方式是将第一种的返回当前的元素都放在next函数中。第一种相对灵活一些，我们可以多次调用currentItem获取当前元素。

ArrayIterator

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

迭代器的设计思路：迭代器中定义hasNext，currentItem，next三个最基本的方法。待遍历的容器对象通过依赖注入传递到迭代器类中。容器通过iterator方法创建迭代器。

迭代器模式的优势

首先看下Java的几种遍历：

List<String> names = new ArrayList<>();
names.add("xzg");
names.add("wang");
names.add("zheng");

// 第一种遍历方式：for循环
for (int i = 0; i < names.size(); i++) {
  System.out.print(names.get(i) + ",");
}

// 第二种遍历方式：foreach循环
for (String name : names) {
  System.out.print(name + ",")
}

// 第三种遍历方式：迭代器遍历
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
  System.out.print(iterator.next() + ","); // Java中的迭代器接口是第二种定义方式，next()既移动游标又返回数据
}
  1. 对于简单的数据结构，链表和数组，顺序循环遍历即可，for循环也可以满足，但是对于复杂的数据结构图和树，有很多遍历方式，Java通过封装预置这些遍历，减少了开发成。减少了本身代码的复杂度。
  2. 游标的存在可以让我们创建多个迭代器，互不影响。容器和迭代器职责更单一。
  3. 容器个迭代器都有抽象接口，基于接口编程更方便替换迭代器（比如，从前往后遍历链表切换成从后往前遍历链表，客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可，其他代码都不需要修改）；自己拓展新的数据结构或者算法可直接实现接口，更符合开闭原则。

遍历集合时为什么不能删减元素

在遍历时删除集合元素

  1. 在遍历时增删元素会导致元素被重复遍历或者遍历不到

  2. 但是这也不是一定发生，有时也能遍历出正常结果。

  3. 这种行为称为结果不可预期行为或者未决行为。

  4. 比如在list容器中，删除一个元素会让后续元素的都往前移位，而当前的游标已经挪到了下一个位置，所以下一个位置的元素挪到当前位置，而游标到了下一个位置，那原来下一个位置的元素就会被遍历不到。如下我们调用next，迭代器返回a，游标已经指向b，这时删除a会发生第三行的情况：游标仍然指向第二个位置但是，但是所有的元素往前一位。

    image-20231022094206147

  5. 当删除游标后的元素比如cd，就不会有这个问题，还是可以正常遍历。

  6. 所以说这个行为是未决行为。

  7. 同理，当我们调用一次next后，在游标之前添加元素，那么a被“挤到”后一位，此时cursor再次指向他，又会被遍历一遍。

    image-20231022094713884

如何应对遍历时改变集合导致的未决行为？

  1. 不允许增删元素在遍历时-》不太容易知道遍历结束的时间点。
  2. 在遍历时增删操作报错。
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异常
  }
}

在定义迭代器的时候会传入一个expectedModCount，也就是当前的集合的修改次数。

在容器中会定义一个变量modCount，表示当前容器被修改（增删改）的次数；

每次在迭代器中调用next，getCurItem或者hasNext的时候就回去检查当前的modCount是否等于expectedModCount。如果中途被修改，那么这两个值不相等，则会马上抛出一个exception。

如何在遍历时安全删除集合元素？

  1. Java迭代器中提供了remove方法，但是只能删除游标指向的前一个元素。而且一个next之后只能跟一个remove多次调用也会报错。
  2. remove如何实现安全删除？
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 return
    int lastRet = -1; // index of last element returned; -1 if no such
    int 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();
      cursor = i + 1;
      return (E) elementData[lastRet = i];
    }
    
    public void remove() {
      if (lastRet < 0)
        throw new IllegalStateException();
      checkForComodification();

      try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
      } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
      }
    }
  }
}

迭代器中额外一步操作，将游标往前移动一位，让游标正确指向因为删除前移的元素。

并且将上一个元素置为负数以达到不能重复调用remove的目的。

迭代器是容器的内部类。remove作为迭代器类的方法而不是容器类的方法，是因为如果容器有多个迭代器，需要对不同的迭代器维护这些信息，会变得复杂。

如何实现一个支持“快照”功能的iterator？

问题描述

所谓“快照”，指我们为容器创建迭代器的时候，相当于给容器拍了一张快照（Snapshot）。之后即便我们增删容器中的元素，快照中的元素并不会做相应的改动。而迭代器遍历的对象是快照而非容器，这样就避免了在使用迭代器遍历的过程中，增删容器中的元素，导致的不可预期的结果或者报错。

具体的代码如下所示。容器 list 中初始存储了 3、8、2 三个元素。尽管在创建迭代器 iter1 之后，容器 list 删除了元素 3，只剩下 8、2 两个元素，但是，通过 iter1 遍历的对象是快照，而非容器 list 本身。所以，遍历的结果仍然是 3、8、2。

public ArrayList<E> implements List<E> {
    int size;
   E[] array = new E[size];
    int index;
  
  @Override
  public void add(E obj) {
      // resize();
    array[index++] = obj;
  }
  
  @Override
  public void remove(E obj) {
    array[index] = 0;
  }
  
  @Override
  public Iterator<E> iterator() {
    return new SnapshotArrayIterator(this);
  }
}

public class SnapshotArrayIterator<E> implements Iterator<E> {
  List<E> list;
  int cursor;
  
  public SnapshotArrayIterator(List list) {
      this.list = new ArrayList<>(list);
      cursor = 0;
  }
  
  @Override
  public boolean hasNext() {
    return list.size() - 1 == cursor;
  }
  
  @Override
  public E next() {//返回当前元素，并且游标后移一位
      if (hasNext()) {
          return list.get(cursor++);
      }
  }
}

解决方案1

  1. 在迭代器中定义一个成员变量snapshot，每当创建迭代器的时候都拷贝一份容器中的元素到快照中，后续操作都基于这个快照。

  2. 实现简单，但是成本较高，每次都需要完全复制一份原来的容器元素，内存消耗大。

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

解决方案2

  1. 利用时间戳。对每一个元素保存添加时间和删除时间。对于一个快照来说，只有满足 addTimestamp< snapshotTimestamp<delTimestamp的元素才是属于这个迭代器的快照。
  2. 实际破坏了数组支持快速随机访问，变成了O(n)的访问。
    1. 可以通过再引入一个数组，支持随机访问（不要的数据直接删除，不做标记删除）。另一个数组做原来事情支持标记删除。

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++;
    }
  }
}

Thoughts? Leave a comment