设计模式系列-第二十章（行为型-迭代器模式）

迈不过友情╰ 2022-11-19 04:04 210阅读 0赞

# 一、迭代器的定义 #

上一课，我们学习了状态模式。状态模式是状态机的一种实现方法。这一章我们学习迭代器模式，迭代器也是比较简单的一种设计模式，，它用来遍历集合对象。这里说的“集合对象”也可以叫“容器”“聚合对象”，实际上就是包含一组对象的对象，比如数组、链表、树、图、跳表。迭代器模式将集合对象的遍历操作从集合类中拆分出来，放到迭代器类中，让两者的职责更加单一。

迭代器是用来遍历容器的，所以，一个完整的迭代器模式一般会涉及容器和容器迭代器两部分内容。为了达到基于接口而非实现编程的目的，容器又包含容器接口、容器实现类，迭代器又包含迭代器接口、迭代器实现类。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmcxMzEyNw_size_16_color_FFFFFF_t_70][]

很多编程语言都将迭代器作为一个基础的类库，直接提供出来了。大部分编程语言都提供了多种遍历集合的方式，比如 for 循环、foreach 循环、迭代器等。我们着重来讲一些迭代器的原理和与其他便利的差异。

# 二、迭代器的实现 #

现在，我们针对 ArrayList 和 LinkedList 两个线性容器，设计实现对应的迭代器。按照之前给出的迭代器模式的类图，我们定义一个迭代器接口 Iterator，以及针对两种容器的具体的迭代器实现类 ArrayIterator 和 ListIterator。我们先来看下 Iterator 接口的定义。具体的代码如下所示：

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

在第一种定义中，next() 函数用来将游标后移一位元素，currentItem() 函数用来返回当前游标指向的元素。在第二种定义中，返回当前元素与后移一位这两个操作，要放到同一个函数 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() 方法，来创建对应的迭代器。为了能实现基于接口而非实现编程，我们还需要将这个方法定义在 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() 方法来创建迭代器。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmcxMzEyNw_size_16_color_FFFFFF_t_70 1][]

# 三、迭代器的优势 #

一般来讲，遍历集合数据有三种方法：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 循环只是一个语法糖而已，底层是基于迭代器来实现的。也就是说，上面代码中的第二种遍历方式（foreach 循环代码）的底层实现，就是第三种遍历方式（迭代器遍历代码）。这两种遍历方式可以看作同一种遍历方式，也就是迭代器遍历方式。相对于 for 循环遍历，利用迭代器来遍历有下面三个优势：

*  迭代器模式封装集合内部的复杂数据结构，开发者不需要了解如何遍历，直接使用容器提供的迭代器即可；对于复杂的数据结构（比如树、图）来说，有各种复杂的遍历方式。比如，树有前中后序、按层遍历，图有深度优先、广度优先遍历等等。如果由客户端代码来实现这些遍历算法，势必增加开发成本，而且容易写错。如果将这部分遍历的逻辑写到容器类中，也会导致容器类代码的复杂性。
 *  迭代器模式将集合对象的遍历操作从集合类中拆分出来，放到迭代器类中，让两者的职责更加单一；
 *  迭代器模式让添加新的遍历算法更加容易，更符合开闭原则。除此之外，因为迭代器都实现自相同的接口，在开发中，基于接口而非实现编程，替换迭代器也变得更加容易。

# 四、增删数据对迭代器的影响 #

在通过迭代器来遍历集合元素的同时，增加或者删除集合中的元素，有可能会导致某个元素被重复遍历或遍历不到。不过，并不是所有情况下都会遍历出错，有的时候也可以正常遍历，所以，这种行为称为结果不可预期行为或者未决行为，也就是说，运行结果到底是对还是错，要视情况而定。实际上，“不可预期”比直接出错更加可怕，有的时候运行正确，有的时候运行错误，一些隐藏很深、很难 debug 的 bug 就是这么产生的。

有两种比较干脆利索的解决方案：一种是遍历的时候不允许增删元素，另一种是增删元素之后让遍历报错。实际上，第一种解决方案比较难实现，我们要确定遍历开始和结束的时间点。遍历开始的时间节点我们很容易获得。我们可以把创建迭代器的时间点作为遍历开始的时间点。但是，遍历结束的时间点确定就比较麻烦，当然我们可以在迭代器类中定义一个新的接口 finishIteration()，主动告知容器迭代器使用完了，但这样需要使用者多一步操作。

实际上，第二种解决方法更加合理。Java 语言就是采用的这种解决方案，增删元素之后，让遍历报错。怎么确定在遍历时候，集合有没有增删元素呢？我们在 ArrayList 中定义一个成员变量 modCount，记录集合被修改的次数，集合每调用一次增加或删除元素的函数，就会给 modCount 加 1。当通过调用集合上的 iterator() 函数来创建迭代器的时候，我们把 modCount 值传递给迭代器的 expectedModCount 成员变量，之后每次调用迭代器上的 hasNext()、next()、currentItem() 函数，我们都会检查集合上的 modCount 是否等于 expectedModCount，也就是看，在创建完迭代器之后，modCount 是否改变过。如果两个值不相同，那就说明集合存储的元素已经改变了，要么增加了元素，要么删除了元素，之前创建的迭代器已经不能正确运行了，再继续使用就会产生不可预期的结果，所以我们选择 fail-fast 解决方式，抛出运行时异常，结束掉程序，让程序员尽快修复这个因为不正确使用迭代器而产生的 bug。

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmcxMzEyNw_size_16_color_FFFFFF_t_70]: /images/20221022/bfea0862a89c47458e7016d2b8c5286b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmcxMzEyNw_size_16_color_FFFFFF_t_70 1]: /images/20221022/cbc713b340994e5990e9450c46fdef20.png