Bug辉的博客 不忘初心,方得始终!

GoF设计模式 - 迭代器模式

2017-08-05
Bug辉 [原创文章]

本文为博主原创文章,请遵守文章最后的版权申明。


迭代器模式(Iterator),行为型模式。对外暴露一个一致的操作接口,提供一种一致的顺序访问集合中每个元素的机制。由于迭代器模式实在是太常用了,所以Java、C#等语言都对迭代器模式提供了内置的支持。

《GoF设计模式 - 概述》一文中已经讲述了设计原则等基础知识,如果还没有看,请先看完这篇文章

迭代器模式

迭代器模式

角色以及职责

  1. Aggregate: 被迭代的目标对象的抽象,可以理解为是一个集合类的抽象。
  2. Concrete Aggregate: Aggregate 的实现类。
  3. Iterator: 迭代器的抽象。该抽象将会限定顺序访问集合元素的方式。
  4. Concrete Iterator: 迭代器实现类。由于迭代器的实现类很多时候其实与集合实现类本身耦合度很高,所以在Java中往往会直接使用嵌套类或者匿名内嵌类的形式来实现。

适用场景

迭代器模式的适用场景是非常明确的,在文章开头其实就已经点明了迭代器模式的使用场景:

希望提供一个一致的顺序访问集合中的每一个元素的机制。

实例

这里的集合以及元素的概念与数学中的概念等价,各位路过的同学都是程序员,这些应该不用解释的。。

本文将直接以Java标准库中的集合类的迭代器实现来演示迭代器模式。为了不干扰同学们理解模式本身,在徒手实现一个简单集合的时候,我将尽可能的保持命名与Java自带的一致,并删改一些写起来麻烦的东西。

类图

迭代器模式

编码实现

首先定义好迭代器的抽象。Java中迭代器的接口名恰好与迭代器模式一致。

/**
 * 迭代器
 * @author: Elvin Zeng
 * @date: 17-8-5.
 */
public interface Iterator<E> {
    /**
     * @return 是否还有下一个元素(概念与数学中集合元素一样)
     */
    boolean hasNext();

    /**
     * @return 下一个元素(概念与数学中集合元素一样)
     */
    E next();
}

再来定义一个名为Iterable的不可描述的接口,用于限定获取迭代器的方式。这个接口其实并不属于迭代器模式的一部分。关于这个接口的来龙去脉后面会分析,请先往下看,不要着急。

/**
 * 可迭代的对象
 * @author: Elvin Zeng
 * @date: 17-8-5.
 */
public interface Iterable<T> {
    /**
     * @return 迭代器
     */
    Iterator<T> iterator();
}

然后定义一个集合类的抽象。这个接口对应着迭代器模式中的Aggregate

/**
 * 列表
 * @author: Elvin Zeng
 * @date: 17-8-5.
 */
public interface List<E> extends Iterable<E> {
    /**
     * @return 列表元素总数
     */
    int size();

    /**
     * @return 列表是否为空
     */
    boolean isEmpty();

    /**
     * 给列表添加元素,插入列表最后。
     * 根据需要还可以重载插入指定位置的版本。
     * 这里为了简化代码就不再演示。
     * @param e 待添加元素
     */
    void add(E e);
}

接着来创建一个List<E>的实现类,这个实现类对应的数据结构只是一个简单的单链表,对应着迭代器模式中的ConcreteAggregate
这里需要注意的是,单链表的节点类型是作为一个嵌套类实现的,对应的迭代器则是作为一个匿名内嵌类实现的。

/**
 * 单链表(非线程安全)
 * @author: Elvin Zeng
 * @date: 17-8-5.
 */
public class LinkedList<E> implements List<E> {
    private int size = 0;
    private Node<E> head;  //  表头对象引用
    private Node<E> last;  //  最后一个元素的引用

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>(){
            private Node<E> next = LinkedList.this.head;

            @Override
            public boolean hasNext() {
                return null != next;
            }

            @Override
            public E next() {
                if (null == next){
                    throw new RuntimeException("NoSuchElementException");
                }
                Node<E> current = this.next;
                this.next = next.getNext();
                return current.getItem();
            }
        };
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size < 1;
    }

    @Override
    public void add(E e) {
        Node<E> node = new Node<E>(null, e);
        if (null == head && null == last){
            head = node;
            last = node;
        }else{
            this.last.setNext(node);
            this.last = node;
        }
        this.size++;
    }

    /**
     * 单链表节点
     * @param <E> 链表元素类型
     */
    private static class Node<E>{
        private Node<E> next;
        private E item;

        public Node(Node<E> next, E item) {
            this.next = next;
            this.item = item;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }

        public E getItem() {
            return item;
        }

        public void setItem(E item) {
            this.item = item;
        }
    }
}

最后是客户端

/**
 * Client
 * @author: Elvin Zeng
 * @date: 17-8-5.
 */
public class App {
    public static void main(String[] args) {
        //  注意这里的List是本程序中自己实现的,不是Java库自带的那个。
        List<String> list = new LinkedList<String>();

        list.add("first");
        list.add("second");
        list.add("third");
        list.add("fourth");

        System.out.println("列表是否为空:" + list.isEmpty());
        System.out.println("列表当前元素总数:" + list.size());
        System.out.println("以下是列表中的所有元素");
        Iterator<String> iterator = list.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

}

执行结果

$ java -jar iterator-1.0-SNAPSHOT.jar
列表是否为空:false
列表当前元素总数:4
以下是列表中的所有元素
first
second
third
fourth

迭代器模式分析

文章前面反复提到过一句话:

提供一个一致的顺序访问集合中的每一个元素的机制

通过本文的例子,我们再来分析一下这句话。
首先,所谓的迭代即一个一个地访问集合的每一个元素。也就是说,作用的对象是一个集合。这个目标对象,在迭代器模式中被成为Aggregate。 最简单的“集合”其实就是数组,在C语系中,我们可以直接通过数组下标来访问每一个元素。然而,我们的集合体系是非常复杂的。不同的具体集合类型(Concrete Aggregate)底层的数据结构可能是完全不同的!有可能是简单的数组,也有可能是链表、队列、树、图。想象一下,假如底层数据结构是一个图,很显然,类似数组下标的方式是没有办法去遍历图的顶点的。而我们希望统一所有集合的迭代方式,这就是迭代器模式的意图!

在C#语言中,我们可以通过索引器来实现类似数组下标的语法访问集合元素。but,迭代器模式的目的不是精确定位到某个元素,而是提供一个机制去迭代这个集合。

迭代器模式实现了不管集合的底层是什么数据结构都可以通过统一的方式去迭代集合元素的效果!非常的方便。正是如此,所以这个设计模式已经被C#、Java在语言层面上支持了(请原谅我把C#放到前面了,毕竟这个是C#先搞出来Java后来模仿的)。
在Java中,只要实现了Iterable接口的集合类,都可以通过foreach循环来隐式调用迭代器。举个例子来说:

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
    System.out.println(iterator.next());
}

如果list对应的类实现了java.lang.Iterable接口,则可以直接通过下面的语法来迭代。在这种情况下,上面那段代码等价于下面这段代码。

for(String element : list){
    System.out.println(element);
}

是不是很简便啊!不过,在本文的例子中,为了演示迭代器模式的实现过程,所以我定义了一个自己的Iterable类,并没有用Java内置的那个。 只要你在实现集合的时候,换成Java内置的那个,就可以用foreach语法了。

分析到这里,想必同学们已经明白了Iterable接口的来龙去脉了吧!也就是说,Iterable只是给迭代器模式引入语言级支持需要的,而并不是迭代器模式本身需要的接口。

在C#中,与Iterable等价的是IEnumerable接口。而迭代器本身则被命名为了IEnumerator

说到这里,我倒是想起了一件往事。大概是2013年,曾经给小伙伴们上过一堂课。那时我们一群学生自发组织了一个技术分享会,在分享分上我给小伙伴们讲过这个问题的。一眨眼,这么多年就过去了。真是时光匆匆啊。。。

参考


版权声明

知识共享许可协议
若无特殊说明则文章内容均为博主原创内容,包括但不限于代码、文字、图片。
《GoF设计模式 - 迭代器模式》 Bug辉 采用 知识共享 署名-非商业性使用-禁止演绎 4.0 国际 许可协议 进行许可。
转载文章时文章署名请注明原作者为Bug辉(Elvin Zeng、zenghui、曾辉也行)并带上原文链接:https://www.bughui.com/2017/08/05/gof-design-pattern-iterator/

鉴于目前国人版权意识比较薄弱,所以路过的同学可能并不了解CC协议。在此特地介绍一下!上述协议大概的意思是(这里只是简单解释,并不替代协议,以上述协议为准):
  • 权利:遵守协议的情况下你可以在任何媒介以任何形式复制、发行本作品。
  • 约束:使用本作品得保留署名(作者+原文链接),不得声称或暗示文章是你创作的。
  • 约束:你不可以将本作品用于商业目的。
  • 约束:如果你再混合、转换、或者基于本作品创作,你不可以发布修改后的作品。
  • 在得到作者允许的情况下你可以不用受上述条款约束。
不论本作品是否对你有益,不论你是否认同本作品的观点,本作品都是作者的劳动产物。尊重别人的劳动别人才会尊重你的劳动是吧!


类似文章

评论

打赏时请在备注信息中填上你的称呼!好让我把你的名字加入致谢名单