迭代器（Iterator）

意图

提供一种方法，顺序访问一个聚合对象中的各个元素，而又不暴露其（指聚合对象）内部表示。

结构

迭代器结构图

动机

一个聚合对象，应该提供一种方法让别人可以访问它的元素，而又不暴露它的内部结构。另外，针对不同的需求，可能还要以不同的方式遍历访问各个元素。

迭代器模式关键思想是将访问和遍历机制与聚合对象分离。这样，我们就可以定义不同的迭代器（Iterator）来实现不同的遍历策略。

适用性

• 访问一个聚合对象无需暴露它的内部表示；
• 支持对聚合对象的多种遍历；
• 为不同的聚合结构提供统一的遍历接口。

重要作用

1. 迭代器模式支持以不同的方式遍历一个聚合，复杂的聚合可以用多种方式进行遍历。它使得改变遍历算法变得很容易；

• 简化了聚合的接口，聚合本身不再需要遍历接口；
• 在同一个聚合上可以有多个遍历（迭代器）。

示例

创建不同的列表（聚合），并创建相应的迭代器来访问和遍历它们的各个元素。

实现（C#）

迭代器示例

using System;
using System.Collections;

// 聚合对象（这里指列表）的抽象基类
public abstract class AbstractList
{
    public abstract Iterator CreateIterator();
    public abstract int Count { get; }
    public abstract void Append(object element);
    public abstract void Remove(object element);
    public abstract object this[int index] { get; }
}


public class List : AbstractList
{
    private readonly ArrayList elements = new ArrayList();

    public override Iterator CreateIterator()
    {
        return new ListIterator(this);
    }

    public override int Count
    {
        get { return this.elements.Count;}
    }

    public override void Append(object element)
    {
        this.elements.Add(element);
    }

    public override void Remove(object element)
    {
        this.elements.Remove(element);
    }

    public override object this[int index] { get { return elements[index]; }}
}


public class SkipList : AbstractList
{
    private readonly ArrayList elements = new ArrayList();

    public override Iterator CreateIterator()
    {
        return new SkipListIterator(this);
    }

    public override int Count
    {
        get { return this.elements.Count;}
    }

    public override void Append(object element)
    {
        this.elements.Add(element);
    }

    public override void Remove(object element)
    {
        this.elements.Remove(element);
    }

    public override object this[int index] { get { return elements[index]; }}
}

// 迭代器的抽象基类
public abstract class Iterator
{
    public abstract void First();
    public abstract void Next();
    public abstract bool IsDone();
    public abstract object Current();
}

// 正常顺序访问的迭代器
public class ListIterator : Iterator
{
    private readonly AbstractList list;
    private int currentIndex = 0;

    public ListIterator(AbstractList list)
    {
        this.list = list;
    }

    public override void First()
    {
        this.currentIndex = 0;
    }

    public override void Next()
    {
        this.currentIndex ++;
    }

    public override bool IsDone()
    {
        return list.Count <= this.currentIndex;
    }

    public override object Current()
    {
        return list[this.currentIndex];
    }
}

// 跳过偶数索引的间隔迭代器
public class SkipListIterator : Iterator
{
    private readonly AbstractList list;
    private int currentIndex = 0;

    public SkipListIterator(AbstractList list)
    {
        this.list = list;
    }

    public override void First()
    {
        this.currentIndex = 0;
    }

    public override void Next()
    {
        this.currentIndex += 2;
    }

    public override bool IsDone()
    {
        return list.Count <= this.currentIndex;
    }

    public override object Current()
    {
        return list[this.currentIndex];
    }
}

// 测试
public class App
{
    public static void Main(string[] args)
    {
        AbstractList list = new List();
        AbstractList skipList = new SkipList();

        list.Append("1");
        list.Append("2");
        list.Append("3");
        list.Append("4");
        list.Append("5");
        list.Append("6");
        list.Append("7");
        list.Append("8");

        skipList.Append("1");
        skipList.Append("2");
        skipList.Append("3");
        skipList.Append("4");
        skipList.Append("5");
        skipList.Append("6");
        skipList.Append("7");
        skipList.Append("8");

        Iterator listIterator = list.CreateIterator();
        do
        {
            Console.Write("{0} ", listIterator.Current());
            listIterator.Next();
        }
        while(!listIterator.IsDone());

        Console.WriteLine();

        Iterator skipListIterator = skipList.CreateIterator();
        do
        {
            Console.Write("{0} ", skipListIterator.Current());
            skipListIterator.Next();
        }
        while(!skipListIterator.IsDone());
    }
}

// 控制台输出：
//  1 2 3 4 5 6 7 8
//  1 3 5 7