王争《设计模式之美》学习笔记

迭代器模式的原理和实现

• 迭代器模式（Iterator Design Pattern），也叫作游标模式（Cursor Design Pattern）。
• 迭代器是用来遍历容器的，所以，一个完整的迭代器模式一般会涉及容器
  和容器迭代器两部分内容。

实现一个迭代器

• 假设，线性数据结构包括数组和链表，对应 ArrayList 和 LinkedList 两个类。
• 我们从两个类中抽象出公共的接口，定义为 List 接口，以方便开发者基于接口而非实现编程，编写的代码能在两种数据存储结构之间灵活切换。
• 我们针对 ArrayList 和 LinkedList 两个线性容器，设计实现对应的迭代器。我们定义一个迭代器接口 Iterator，以及针对两种容器的具体的迭代器实现类 ArrayIterator 和 ListIterator。

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

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

• Iterator 接口有两种定义方式：
  • 第一种定义中，next() 函数用来将游标后移一位元素，currentItem() 函数用来返回当前游标指向的元素。
  • 在第二种定义中，返回当前元素与后移一位这两个操作，要放到同一个函数 next() 中完成。
  • 第一种定义方式更加灵活一些，比如我们可以多次调用 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() 方法，来创建对应的迭代器。为了能实现基于接口而非实现编程，我们还需要将这个方法定义在 List 接口中。

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() 方法来创建迭代器。

迭代器模式的优势

• 一般来讲，遍历集合数据有三种方法：for 循环、foreach 循环、iterator 迭代器。

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()既移动游标又返回数据
}

• foreach 循环只是一个语法糖而已，底层是基于迭代器来实现的。
• for 循环遍历方式比起迭代器遍历方式，代码看起来更加简洁。
• 那我们为什么还要用迭代器来遍历容器呢？原因有以下三个：
  • 首先，对于类似数组和链表这样的数据结构，遍历方式比较简单，直接使用 for 循环来遍历就足够了。但是，对于复杂的数据结构（比如树、图）来说，有各种复杂的遍历方式，应对复杂性的方法就是拆分，我们可以将遍历操作拆分到迭代器类中。比如，我们就可以定义 DFSIterator、BFSIterator 两个迭代器类，让它们分别来实现深度优先遍历和广度优先遍历。
  • 其次，将游标指向的当前位置等信息，存储在迭代器类中，每个迭代器独享游标信息。这样，我们就可以创建多个不同的迭代器，同时对同一个容器进行遍历而互不影响。
  • 最后，容器和迭代器都提供了抽象的接口，方便我们在开发的时候，基于接口而非具体的实现编程。当需要切换新的遍历算法的时候，比如，从前往后遍历链表切换成从后往前遍历链表，客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可，其他代码都不需要修改。除此之外，添加新的遍历算法，我们只需要扩展新的迭代器类，也更符合开闭原则。