上一篇文章中,我们学习了状态模式。状态模式是状态机的一种实现方法。它通过将事件触发的状态转移和动作执行,拆分到不同的状态类中,以此来避免状态机类中的分支判断逻辑,应对状态机类代码的复杂性。
今天,我们学习另外一种行为型设计模式,迭代器模式。它用来遍历集合对象。不过,很多编程语言都将迭代器作为一个基础的类库,直接提供出来了。在平时开发中,特别是业务开发,我们直接使用即可,很少会自己去实现一个迭代器。不过,知其然知其所以然,弄懂原理能帮助我们更好的使用这些工具类,所以,我觉得还是有必要学习一下这个模式。我们知道,大部分编程语言都提供了多种遍历集合的方式,比如 for 循环、foreach 循环、迭代器等。所以,今天我们除了讲解迭代器的原理和实现之外,还会重点讲一下,相对于其他遍历方式,利用迭代器来遍历集合的优势。

迭代器模式(Iterator Design Pattern),也叫作游标模式(Cursor Design Pattern)。在开篇中我们讲到,它用来遍历集合对象。这里说的“集合对象”也可以叫“容器”“聚合对象”,实际上就是包含一组对象的对象,比如数组、链表、树、图、跳表。迭代器模式将集合对象的遍历操作从集合类中拆分出来,放到迭代器类中,让两者的职责更加单一。

迭代器的结构与实现

结构

  1. 迭代器角色(Iterator):迭代器角色负责定义访问和遍历元素的接口。
  2. 具体迭代器角色(Concrete Iterator):具体迭代器角色要实现迭代器接口,并要记录遍历中的当前位置。
  3. 容器角色(Container):容器角色负责提供创建具体迭代器角色的接口。
  4. 具体容器角色(Concrete Container):具体容器角色实现创建具体迭代器角色的接口,这个具体迭代器角色于该容器的结构相关。

接下来,我们通过一个例子来具体讲,如何实现一个迭代器。

开篇中我们有提到,大部分编程语言都提供了遍历容器的迭代器类,PHP亦是如此。PHP 拥有内置的迭代器接口, 可用于创建与其他 PHP 代码兼容的自定义迭代器。我们在平时开发中,直接拿来用即可,几乎不大可能从零编写一个迭代器。不过,这里为了讲解迭代器的实现原理,我们假设某个新的编程语言的基础类库中,还没有提供线性容器对应的迭代器,需要我们从零开始开发。现在,我们一块来看具体该如何去做。
接下来我们以数组为例来写一个迭代器对数组集合进行处理。
我们先来看下 Iterator 接口的定义。具体的代码如下所示:

interface Iterator
{
    public function first();
    public function next();
    public function isDone();
    public function currentItem();
}

在代码中,first操作初始化迭代器,使当前元素指向第一个元素,next操作将当前元素指针向前推进一步,isDone检查是否越过最后一个元素,也就是是否完成遍历。currentItem()方法用于返回当前元素。
现在,我们再来看下 ArrayIterator 的代码实现,具体如下所示。


class ArrayIterator implements Iterator
{
    private $current;
    private $list =[];

    public function __construct(array $list)
    {
        $this->list = $list;
        $this->current = 0;
    }

    public function first()
    {
        $this->current[0];
    }
    public function next()
    {
        $this->current++;
        if ($this->current < count($this->list)) {
           return $this->list[$this->current];
        }
    }
    public function isDone()
    {
        return $this->current >= count($this->list);
    }
    public function currentItem()
    {
        return $this->list[$this->current];
    }
}

$arrayIterator = new ArrayIterator(array(1,2,3,4));
 while (!$arrayIterator->isDone())
 {
     echo $arrayIterator->currentItem()."\n";
     $arrayIterator->next();
}
//运行结果 : 1 2 3 4

在上面的代码实现中,我们需要将待遍历的容器对象,通过构造函数传递给迭代器类。实际上,为了封装迭代器的创建细节,我们可以在容器中定义一个 iterator() 方法,来创建对应的迭代器。为了能实现基于接口而非实现编程,我们还需要将这个方法定义在Container接口中。具体的代码实现和使用示例如下所示:

interface Container
{
    public function iterator(array $list);
}

class ArrayContainer implements Container
{

    public function iterator(array $list)
    {
        return new ArrayIterator($list);
    }
}
//clientCode
 $arrayContainer = new ArrayContainer();
 $arrayIterator = $arrayContainer->iterator(array(1,2,3,4));
 while (!$arrayIterator->isDone())
 {
    echo $arrayIterator->currentItem()."\n";
    $arrayIterator->next();
}

结合刚刚的例子,我们来总结一下迭代器的设计思路。其实通过客户端的调用,我们发现迭代器中需要定义 的其实只要有isDone()、currentItem()、next() 三个最基本的方法。待遍历的容器或数据通过依赖注入传递到迭代器类中。容器通过 iterator() 方法来创建迭代器。

迭代器模式的优势

迭代器的原理和代码实现讲完了。接下来,我们来一块看一下,使用迭代器遍历集合的优势。
一般来讲,遍历集合数据有三种方法:for 循环、foreach 循环、iterator 迭代器。对于这三种方式,我们分别用代码写出来进行比较

//第一种遍历方式:for循环
for ($i=0;$i<count($arr);$i++){
    echo $arr[$i]."\n";
}

echo '<br>';

//第二种遍历方式:foreach循环
foreach ($arr as $value){
     echo $value."\n";
}

 echo '<br>';
 
//第三种遍历方式:迭代器遍历
$arrayContainer = new ArrayContainer();
$arrayIterator = $arrayContainer->iterator($arr);
 while (!$arrayIterator->isDone())
 {
    echo $arrayIterator->currentItem()."\n";
    $arrayIterator->next();
 }

实际上,foreach 循环只是一个语法糖而已,底层是基于迭代器来实现的。也就是说,上面代码中的第二种遍历方式(foreach 循环代码)的底层实现,就是第三种遍历方式(迭代器遍历代码)。这两种遍历方式可以看作同一种遍历方式,也就是迭代器遍历方式。从上面的代码来看,for 循环遍历方式比起迭代器遍历方式,代码看起来更加简洁。那我们为什么还要用迭代器来遍历容器呢?为什么还要给容器设计对应的迭代器呢?原因有以下三个。

首先,对于类似数组和链表这样的数据结构,遍历方式比较简单,直接使用 for 循环来遍历就足够了。但是,对于复杂的数据结构(比如树、图)来说,有各种复杂的遍历方式。比如,树有前中后序、按层遍历,图有深度优先、广度优先遍历等等。如果由客户端代码来实现这些遍历算法,势必增加开发成本,而且容易写错。如果将这部分遍历的逻辑写到容器类中,也会导致容器类代码的复杂性。

前面也多次提到,应对复杂性的方法就是拆分。我们可以将遍历操作拆分到迭代器类中。比如,针对图的遍历,我们就可以定义 DFSIterator、BFSIterator 两个迭代器类,让它们分别来实现深度优先遍历和广度优先遍历。
其次,将游标指向的当前位置等信息,存储在迭代器类中,每个迭代器独享游标信息。这样,我们就可以创建多个不同的迭代器,同时对同一个容器进行遍历而互不影响。

最后,容器和迭代器都提供了抽象的接口,方便我们在开发的时候,基于接口而非具体的实现编程。当需要切换新的遍历算法的时候,比如,从前往后遍历链表切换成从后往前遍历链表,客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可,其他代码都不需要修改。除此之外,添加新的遍历算法,我们只需要扩展新的迭代器类,也更符合开闭原则。

总结

迭代器模式,也叫游标模式。它用来遍历集合对象。这里说的“集合对象”,我们也可以叫“容器”“聚合对象”,实际上就是包含一组对象的对象,比如,数组、链表、树、图、跳表。

一个完整的迭代器模式,一般会涉及容器和容器迭代器两部分内容。为了达到基于接口而非实现编程的目的,容器又包含容器接口、容器实现类,迭代器又包含迭代器接口、迭代器实现类。容器中需要定义 iterator() 方法,用来创建迭代器。迭代器接口中需要定义 hasNext()、currentItem()、next() 三个最基本的方法。容器对象通过依赖注入传递到迭代器类中。

遍历集合一般有三种方式:for 循环、foreach 循环、迭代器遍历。后两种本质上属于一种,都可以看作迭代器遍历。相对于 for 循环遍历,利用迭代器来遍历有下面三个优势:

  • 迭代器模式封装集合内部的复杂数据结构,开发者不需要了解如何遍历,直接使用容器提供的迭代器即可;
  • 迭代器模式将集合对象的遍历操作从集合类中拆分出来,放到迭代器类中,让两者的职责更加单一;
  • 迭代器模式让添加新的遍历算法更加容易,更符合开闭原则。除此之外,因为迭代器都实现自相同的接口,在开发中,基于接口而非实现编程,替换迭代器也变得更加容易。

参考资料:设计模式之美-迭代器模式(上):相比直接遍历集合数据,使用迭代器有哪些优势
github示例 :https://github.com/yangpanyao/design-patterns/tree/master/Iterator/example1

Last modification:July 15th, 2020 at 07:48 pm