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

定义

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

举例

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

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

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

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

UML类图:

«interface»AbstractCollectionTIterator<T> *getIterator()ArrayTT *startint nLinkedListTListNode<T> *sentinel«interface»AbstractIteratorTT &next()bool hasNext()ArrayIteratorTArray<T> &arrayLinkedListIteratorTLinkedList<T> &list

代码:

抽象聚合类:

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;
    }
};

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

组成部分

抽象聚合类(Abstract Collection):存储数据的抽象类,持有迭代器对象。

具体聚合类(Concrete Collection):具体实现数据的存储。

抽象迭代器类(Abstract Iterator):定义判断是否有下一个元素和返回下一个元素的抽象接口。

具体迭代器类(Concrete Iterator):具体实现对某种聚合对象的遍历。

优缺点

优点

  1. 支持以不同的方式遍历一个聚合对象。如二叉树就可以有前序遍历、中序遍历、后序遍历、层序遍历等多种遍历方式。

  2. 迭代器简化了聚合类。聚合类内部就不需要再去实现遍历方法了。

  3. 由于引入了抽象层,增加新的聚合类和迭代器类都很方便,无须修改原有代码,符合开闭原则。

缺点

  1. 增加一种聚合类就要至少增加一种迭代器类,增加了系统的复杂性。

使用场景

  1. 在不暴露聚合对象的底层表示的前提下遍历聚合对象。

  2. 需要为聚合对象提供多种遍历方式。

  3. 为遍历不同的聚合结构提供一个统一的接口。

热门相关:斗神战帝   薄先生,情不由己   第一神算:纨绔大小姐   薄先生,情不由己   刺客之王