【设计模式】之迭代器模式

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

定义

迭代器模式（Iterator pattern）：用于顺序访问集合对象里的每一个元素，不用暴露集合是怎样存储元素的。

举例

某个班级有若干个学生，现在需要统计这些学生的平均分数。假设所有学生的分数是用数组存储的：

int totalScore(int *array, int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++) // 遍历数组
    {
        sum += array[i];
    }
    return sum;
}

但是，如果是用链表存储呢？就要重新写一套逻辑来遍历链表。那有没有一种方法，无论分数是如何存储的，都可以有统一的方式进行遍历呢？

答案是将“存储”与“遍历”解耦，先创建抽象的Collection和Iterator两个接口，再分别派生出具体的聚合对象和迭代器。遍历时，由迭代器来负责遍历，而不是由聚合对象负责遍历。

UML类图：

代码：

抽象聚合类：

template <typename T>
class AbstractCollection
{
public:
    virtual ~AbstractCollection() = default;
};

具体聚合类（数组、单向链表）：

template <typename T>
class Array : public AbstractCollection<T>
{
    friend class ArrayIterator<T>;

    T *start;
    int n;

public:
    Array(T *start, int n) : start(start), n(n) { }

    ArrayIterator<T> getIterator()
    {
        return ArrayIterator<T>(*this);
    }

    T &operator[](int i)
    {
        return start[i];
    }
};

template <typename T>
class LinkedList : public AbstractCollection<T>
{
    friend class ListNodeIterator<T>;
    /*
    本例中单向链表的首节点之前有哨兵节点（sentinel)，尾结点的后一个节点为nullptr
    */
    struct ListNode
    {
        T data;
        ListNode *next;
    };

    ListNode *sentinel;

public:
    LinkedList(ListNode *sentinel) : sentinel(sentinel) { }

    ListNodeIterator<T> getIterator()
    {
        return ListNodeIterator<T>(*this);
    }
};

抽象迭代器类：

template <typename T>
class AbstractIterator
{
public:
    virtual ~AbstractIterator() = default;
    virtual bool hasNext() = 0;
    virtual T &next() = 0;
};

具体迭代器类：

template <typename T>
class ArrayIterator : public AbstractIterator<T>
{
    Array<T> &array;
    int i;

public:
    ArrayIterator(Array<T> &array) : array(array), i(-1) { }

    bool hasNext() override
    {
        return i + 1 < array.n;
    }

    T &next() override
    {
        ++i;
        return array[i];
    }
};

template <typename T>
class LinkedListIterator : public AbstractIterator<T>
{
    LinkedList<T> &list;
    LinkedList::ListNode *current;

public:
    LinkedListIterator(LinkedList<T> &list) : list(list), current(list.sentinel) { }

    bool hasNext() override
    {
        return current->next != nullptr;
    }

    T &next() override
    {
        current = current->next;
        return current->data;
    }
};

客户端：

class Client
{
public:
    void testArray()
    {
        Array<int> array( /* 初始化部分省略 */ );
        int sum = 0;
        for (auto iterator = array.getIterator(); iterator.hasNext(); )
        {
            sum += iterator.next();
        }
        cout << sum << endl;
    }

    void testLinkedList()
    {
        LinkedList<int> list( /* 初始化部分省略 */ );
        int sum = 0;
        for (auto iterator = list.getIterator(); iterator.hasNext(); )
        {
            sum += iterator.next();
        }
        cout << sum << endl;
    }
};

可以看到，遍历部分的代码是完全一样的。这正是因为我们给不同的遍历方式提供了统一的接口。