第十八章 迭代器模式(Iterator Pattern)

1 概要

迭代器模式(Iterator Pattern)是一种行为模式(Behavior Design Patters)。它主要用于提供一种方法依次访问容器中的元素(Elements in a Collection)。迭代器模式分离了容器内部逻辑结构和访问元素的逻辑。换句话说，使用迭代器模式，开发人员能够将注意力放在如何处理元素的逻辑上，而无需了解容器的内部结构。

另外，迭代器还“封装”了元素的访问顺序。对于同一个容器，不同的迭代器可以表示以不同的顺序访问元素。

2 迭代器模式的结构

在迭代器模式中有6个参与方。

1. 待访问的对象(Object)，它们包含在容器中。
2. 容器接口(Set)表示的是容器的接口。一个容器对象内部包含了多个待访问的对象(Object)。
3. 具体的容器(ConcreteSet)表示实现容器接口的具体实现。
4. 迭代器接口(Interator)表示迭代器的接口。
5. 具体的迭代器(ConcreteInterator)表示一个具体的迭代器实现，它会按照一定的顺序访问容器中的元素。
6. 使用迭代器的客户(Client)。

图一 迭代器模式结构。

3 迭代器示例

迭代器模式是一个常见的设计模式。我们将使用一个简单的例子来展示迭代器的使用方法。我们首先定义了待访问的对象Element和存放Element的对象Set。Set对象的成员方法getIterator()返回一个迭代器对象。开发人员可以使用这个迭代器对象依次访问容器中的Element对象。成员方法addElement()向容器中添加新元素。成员方法get()可根据元素所在的位置返回元素对象。成员方法size()则返回容器中元素的个数。

public class Element {
}

public Interface Set {
    public Iterator getIterator();
    
    public void addElement(Element element);
    public Element get(int index);
    public int size();
}

在ConcreteSet中实现了一个简单的容器。容器中的元素存放在数组elements中。

public class ConcreteSet implements Set {
    Element[] elements = null;
    int index = 0;

    public ConcreteSet() {
        this.elements = new Element[10];
    }

    @Override
    public Iterator getIterator() {
        return new ReversedIteratorImpl(this);
    }

    @Override
    public void addElement(Element ele) throws IllegalStateException {
        if (index < 10) {
            this.elements[index] = ele;
            index ++;
        } else {
            throw new IllegalStateException();
        }
    }
    
    @Override
    public int size() {
        return index;
    }
    
    @Override
    public Element get(int index) throws IllegalStateException {
        if (index < this.index && index >= 0) {
            return this.elements[index];
        }
        throw new IllegalStateException();
    }
}

Interator接口定义了迭代器提供的接口。ReversedIteratorImpl则是Interator接口的一个具体实现。ReversedIteratorImpl将会逆向访问Set中的每一个元素。ReversedIteratorImpl中的成员变量set和pos保存了访问的容器对象和当前的位置信息。

public Interface Iterator {
    public Element next();
    public boolean hasNext();
}

public class ReversedIteratorImpl implements Iterator {
    private Set set = null;
    private int pos = 0;

    public ReversedIteratorImpl(Set set) {
        this.set = set;
        this.pos = set.size() - 1;
    }

    @Override
    public Element next() {
        return this.set.get(this.pos--);
    }

    @Override
    public boolean hasNext() {
        return this.pos >= 0
    }
}

在使用时，我们首先创建两个Element对象，并将它们放入Set对象中。然后，我们通过调用getIterator()创建一个迭代器对象。这个迭代器对象会逆向访问Set中所有的元素。

public class IteratorClient {
    public static void main(String[] args) {
        Set collection = new ConcreteSet();
        collection.addElement(new Element());
        collection.addElement(new Element());

        Iterator iterator = collection.getIterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next().toString());
        }
    }
}

4 应用示例

Java标准库也使用了迭代器模式。最常见的是当访问容器(Collection)里的元素时，开发人员可以调用iterator()方法，创建一个java.util.Iterator的对象。实际上，interator()方法是java.lang.Iterable的接口之一，常见的容器，例如：链表、堆栈、队列等均实现了Iterable接口。除此之外，java.util.Scanner也实现了Iterator接口，用于读取或者扫描文本信息。java.util.Enumeration也使用了迭代器模式，用于访问所有定义的枚举值。

我们在本小节中以java.util.ArrayList为例，介绍ArrayList是如何使用迭代器模式的。如果读者对其他容器、Scanner或者Enumeration的实现感兴趣，可自行阅读其源代码。

ArrayList是Java标准库中提供的一个常用的链表类。它的成员方法iterator()返回一个迭代器对象。从下面的源代码来看，ArrayList的iterator()方法直接返回一个Itr类的对象。Itr是ArrayList的一个内部类，实现了Iterator接口。这个迭代器对象是一种Fast-Failed对象，即在使用这个迭代器的过程中，如果链表对象的内容发生变化，则迭代器对象会变为无效对象，调用next()方法访问容器中的元素时会抛出异常。

Itr对象保存了三个成员变量。cursor用于保存当前指向对象的位置。lastRet则指向了容器中最后一个元素的位置。expectedModCount则用于检测容器对象是否发生变化。modCount是容器中的一个计数器。每当容器发生变化时，modCount会增加１。所以，当Itr对象被创建时，成员变量expectedModCount会保存当时的modCount的值。每当迭代器Itr访问容器中的元素时，都会比较计数器的值。若发生变化，则抛出ConcurrentModificationException异常，表示容器被同时修改了。

// OpenJDK 15
package java.util;

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    ...
    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;

        // prevent creating a synthetic constructor
        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];
        }

        ...

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
    ...
}

5 小结

本章介绍了迭代器模式的结构和使用方法。迭代器模式将元素的访问逻辑从元素的管理维护逻辑中分离出来，使得元素的访问和管理维护更加简单、直观。迭代器是一种非常实用且常见的设计模式。