迭代器模式

一、引言

　　迭代这个名词对于熟悉Java的人来说绝对不陌生。我们常常使用JDK提供的迭代接口进行java collection的遍历：

Iterator it = list.iterator();
while(it.hasNext()){
　//using “it.next();”do some businesss logic
}

而这就是关于迭代器模式应用很好的例子。

二、定义与结构

　　迭代器（Iterator）模式，又叫做游标（Cursor）模式。GOF给出的定义为：提供一种方法访问一个容器（container）对象中各个元素，而又不需暴露该对象的内部细节。

　　从定义可见，迭代器模式是为容器而生。很明显，对容器对象的访问必然涉及到遍历算法。你可以一股脑的将遍历方法塞到容器对象中去；或者根本不去提供什么遍历算法，让使用容器的人自己去实现去吧。这两种情况好像都能够解决问题。

　　然而在前一种情况，容器承受了过多的功能，它不仅要负责自己“容器”内的元素维护（添加、删除等等），而且还要提供遍历自身的接口；而且由于遍历状态保存的问题，不能对同一个容器对象同时进行多个遍历。第二种方式倒是省事，却又将容器的内部细节暴露无遗。

　　而迭代器模式的出现，很好的解决了上面两种情况的弊端。先来看下迭代器模式的真面目吧。

　　迭代器模式由以下角色组成：

　　1) 迭代器角色（Iterator）：迭代器角色负责定义访问和遍历元素的接口。

　　2) 具体迭代器角色（Concrete Iterator）：具体迭代器角色要实现迭代器接口，并要记录遍历中的当前位置。

　　3) 容器角色（Container）：容器角色负责提供创建具体迭代器角色的接口。

　　4) 具体容器角色（Concrete Container）：具体容器角色实现创建具体迭代器角色的接口——这个具体迭代器角色于该容器的结构相关。

结构图

具体实现

迭代者抽象类

package iterator;
/**
 * 迭代器抽象类
 *
 */
public abstract class Iterator {
    public abstract Object First();
    public abstract Object Next();
    public abstract boolean hasNext();
    public abstract Object currentItem();
}

集合抽象类

package iterator;
/**
 * 聚集抽象类
 *
 */
public abstract class Aggregate {
    public abstract Iterator createIterator();
    public abstract Object get(int i);
    public abstract int size();
}

实现迭代器抽象类和集合抽象类

具体迭代类

package iterator;

/**
 * 具体迭代类
 */
public class ConcreteIterator extends Iterator {
    private ConcreteAggregate aggregate;
    private int current = 0;
    public ConcreteIterator(ConcreteAggregate aggregate){
        this.aggregate = aggregate;
    }
    public Object First(){
        return aggregate.get(0);
    }
    public boolean hasNext(){
        return current<aggregate.size();
    }
    public Object Next(){
        Object res = null;
        if(current < aggregate.size()){
            res = aggregate.get(current);
        }
        current++;
        return res;
    }
    public Object currentItem(){
        Object res = null;
        if(current < aggregate.size()){
            res = aggregate.get(current);
        }
        return res;
    }
}

具体集合类

package iterator;
/**
 * 具体集合类
 */
public class ConcreteAggregate extends Aggregate{
    private String[] items = new String[]{"A","B","C","D"};
    public Iterator createIterator(){
        return new ConcreteIterator(this);
    }
    public int size(){
        return items.length;
    }
    public Object get(int i){
        if(i>=0 && i<size())
            return items[i];
        return null;
    }
}

客户端

package iterator;

public class Main {
    public static void main(String[] args){
        ConcreteAggregate a = new ConcreteAggregate();
        Iterator iterator = a.createIterator();
        while(iterator.hasNext()){
            System.out.println(iterator.Next());
        }
    }
    
}

优点

简化了遍历方式，对于对象集合的遍历，还是比较麻烦的，对于数组或者有序列表，我们尚可以通过游标来取得，但用户需要在对集合了解很清楚的前提下，自行遍历对象，但是对于hash表来说，用户遍历起来就比较麻烦了。而引入了迭代器方法后，用户用起来就简单的多了。
可以提供多种遍历方式，比如说对有序列表，我们可以根据需要提供正序遍历，倒序遍历两种迭代器，用户用起来只需要得到我们实现好的迭代器，就可以方便的对集合进行遍历了。
封装性良好，用户只需要得到迭代器就可以遍历，而对于遍历算法则不用去关心。

缺点

对于比较简单的遍历（像数组或者有序列表），使用迭代器方式遍历较为繁琐，大家可能都有感觉，像ArrayList，我们宁可愿意使用for循环和get方法来遍历集合。

适用场景

迭代器模式是与集合共生共死的，一般来说，我们只要实现一个集合，就需要同时提供这个集合的迭代器，就像java中的Collection，List、Set、Map等，这些集合都有自己的迭代器。假如我们要实现一个这样的新的容器，当然也需要引入迭代器模式，给我们的容器实现一个迭代器。

但是，由于容器与迭代器的关系太密切了，所以大多数语言在实现容器的时候都给提供了迭代器，并且这些语言提供的容器和迭代器在绝大多数情况下就可以满足我们的需要，所以现在需要我们自己去实践迭代器模式的场景还是比较少见的，我们只需要使用语言中已有的容器和迭代器就可以了。

ArrayList中的迭代器源码

   /**
     * 迭代器 
     * Returns a list iterator over the elements in this list (in proper
     * sequence), starting at the specified position in the list.
     * The specified index indicates the first element that would be
     * returned by an initial call to {@link ListIterator#next next}.
     * An initial call to {@link ListIterator#previous previous} would
     * return the element with the specified index minus one.
     *
     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

    /**
     * Returns a list iterator over the elements in this list (in proper
     * sequence).
     *
     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @see #listIterator(int)
     */
    public ListIterator<E> listIterator() {
//        ArrayList a = new ArrayList();
//        Iterator interator = a.iterator(); // test 
        return new ListItr(0);
    }

    /**
     * 返回迭代器 
     *
     * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @return an iterator over the elements in this list in proper sequence
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * An optimized version of AbstractList.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;

        public boolean hasNext() { // 是否越界 记录运行到第几个id
            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];
        }

        public void remove() { // 删除元素 
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

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

    /**
     * An optimized version of AbstractList.ListItr 迭代器一个优化版本
     */
    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) { // 从index 下标开始迭代
            super();
            cursor = index;
        }

        public boolean hasPrevious() { // 前驱
            return cursor != 0;
        }

        public int nextIndex() { // 后继id
            return cursor;
        }

        public int previousIndex() { // 前驱id
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() { // 前驱元素
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) { // 当前位置更新元素
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) { // 添加元素
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }