迭代器设计模式

迭代器设计模式是行为型设计模式（关注对象间的通信）的一种。

意图：提供一种方法顺序访问一个聚合对象中各个元素, 而又无须暴露该对象的内部表示。即将数据的存储和遍历分离。

使用场景: 1、访问一个聚合对象的内容而无须暴露它的内部表示。 2、需要为聚合对象提供多种遍历方式。 3、为遍历不同的聚合结构提供一个统一的接口。

UML

迭代器模式

JAVA中的迭代器

JAVA中迭代器模式的典型应用场景就是集合类中的迭代器了，例如LinkedList.java中的ListItr迭代器，作为内部类声明在LinkedList类中：

public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }
//public interface ListIterator<E> extends Iterator<E> 
    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }
      //hasNext方法和next方法是迭代器的核心方法
        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            //LinkedList是线程不安全的，如果下面的方法check失败会抛出ConcurrentModificationException
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
        ...
        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }
       ...


}

Python中的迭代器

python中凡是可作用于for循环的对象都是Iterable类型；凡是可作用于next()函数的对象都是Iterator(迭代器)类型，它们表示一个惰性计算的序列；集合数据类型如list、dict、str等是Iterable但不是Iterator，不过可以通过iter()函数获得一个Iterator对象。

提到python中的迭代器就不得不说python中的生成器。python中的生成器都是Iterator对象。

python可以通过如下的方式创建生成器对象：

1.生成器表达式

将列表生成式的[]改为()即可：

>>> g = (x * x for x in range(10))
>>> g
<generator object <genexpr> at 0x1022ef630>

这样通过next()内置函数可以直接获取下迭代器的一个元素。

>>> next(g)
0
>>> next(g)
1
>>> next(g)
4

2.函数中使用yeild关键字

如果一个函数定义中包含yield关键字，那么这个函数就不再是一个普通函数，而是一个generator:

def fib(max):
    n, a, b = 0, 0, 1
    while n < max:
        yield b
        a, b = b, a + b
        n = n + 1
    return 'done'

上面实现了一个斐波那契数列的生成器：

>>> f = fib(6)
>>> f
<generator object fib at 0x104feaaa0>

generator和函数的执行流程不一样。函数是顺序执行，遇到return语句或者最后一行函数语句就返回。而变成generator的函数，在每次调用next()的时候执行，遇到yield语句返回，再次执行时从上次返回的yield语句处继续执行。

Python的Iterator对象表示的是一个数据流，Iterator对象可以被next()函数调用并不断返回下一个数据，直到没有数据时抛出StopIteration错误。可以把这个数据流看做是一个有序序列，但我们却不能提前知道序列的长度，只能不断通过next()函数实现按需计算下一个数据，所以Iterator的计算是惰性的，只有在需要返回下一个数据时它才会计算。

由于数据生成的算法是固定的，这样只需要在调用next时进行一次计算，不需要开辟存储空间存储整个序列。在迭代海量数据时非常有优势。