迭代器模式(行为型)

发表于 分类于 Waline： 本文字数： 13k 阅读时长 ≈ 12 分钟

前言

在C++ STL标准库里面有各种容器对象，如vector,list,map等等，对这些容器对象的遍历操作时候,都是首先获取相应容器的迭代器，再通过迭代器的begin方法,++操作符,end方法来遍历整个容器对象内的各个元素，使得容器对象的元素存储操作和遍历操作分离了，这样的好处是对于同一个类型的容器对象可以通过不同的遍历方法来遍历，同样的，不同的类型的容器对象也可以通过相同的遍历方法来进行。像STL标准库里面的这种解耦数据存储和遍历操作的方法就是本文将要介绍的迭代器模式。

迭代器模式

一般来说，聚合对象拥有两个职责存储数据和遍历数据。从依赖性来看，前者是聚合对象的基本职责；而后者既是可变化的，又是可分离的。因此，可以将遍历数据的行为从聚合对象中分离出来，封装在一个迭代器的对象中，由迭代器来提供遍历聚合对象内部数据的行为，这将简化聚合对象的设计，更符合单一职责原则的要求

意图

提供一种方法顺序访问一个聚合对象中各个元素，而又不需暴露该对象的内部表示，别名游标。

迭代器模式包含聚合和迭代器两个层次结构。迭代器里面都包含了创建迭代器的工厂模式

参与者

  • Iterator
    抽象迭代器,定义了访问和遍历元素的接口
    一般包含获取第一个元素的first()方法，访问下一个元素的next()方法，用于判断是否还有下一个元素的hasNext()方法，用于获取当前元素的currentItem()方法等。这些方法在具体的迭代器中被实现

  • ConcreteIterator
    具体迭代器,实现了抽象迭代器声明的接口，完成对聚合对象的遍历，同时在具体迭代器中通过游标来记录在聚合对象中所处的当前位置，游标通常是一个非负整数
    具体迭代器中通常包含一个聚合对象的引用来指明迭代的对象

  • Aggregate
    抽象的聚合类，用于存储和管理元素对象，声明一个createIterator()方法用来创建一个迭代器对象，相当于抽象迭代器工厂的角色

  • ConcreteAggregate
    具体的聚合类，实现了抽象聚合类的createIterator()方法，该方法返回一个具体聚合类对象的具体迭代器对象实例

模式结构

iterator

代码实现

1.首先定义抽象的迭代器类Iterator,并提供几个常用的聚合元素遍历操作接口：First() ,Next(),Current(), IsDone()等：

1
2
3
4
5
6
7
8
9
10
11
// Abstract Iterator
// 模板类Iterator定义, 使用方法：template <typename(class) T>
template <typename T>                        
class Iterator
{
public:
    virtual void First()  = 0;
    virtual void Next()   = 0;
    virtual T* Current()  = 0;
    virtual bool IsDone() = 0;
};

2.再定义具体迭代器类ConcreteItertor，并实现相应的接口:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Concrete Iterator
template <typename T>     
class Aggregate;       // 模板类Aggregate声明，template <typename(class) T>

template <typename T>  // 模板类ConcreteItertor定义，template <typename(class) T>
class ConcreteItertor: public Iterator<T>
{
private:
    Aggregate<T> *m_pAggr;             // 与某个聚合对象联系的迭代器
    int m_cur;                         // 游标
public:
    ConcreteItertor(Aggregate<T> *pAggr) : m_pAggr(pAggr) {}; //构造方式注入需要遍历的具体聚合对象
public:
    virtual void First()
    {
        m_cur = 0;
    }
    virtual void Next()
    {
        if (m_cur < (m_pAggr->GetLen()))
        {
            m_cur++;
        }
    }
    virtual T* Current()
    {
        if (m_cur < (m_pAggr->GetLen()))
        {
            return &((*m_pAggr)[m_cur]); //  重载了操作符[]
        }
        else
        {
            return NULL;
        }
    }
    virtual bool IsDone()
    {
        return (m_cur >= (m_pAggr->GetLen()));
    }
};

3.再定义抽象的聚合类Aggregate，并提供了与聚合元素存储相关的操作接口,同时还声明一个创建迭代器的工厂方法CreateIterator()：

1
2
3
4
5
6
7
8
9
10
11
12
13
// Abstract Aggregate
template <typename T>
class Aggregate
{
public:
    virtual Iterator<T>* CreateIterator() = 0; // 工厂方法创建迭代器
    virtual T& operator[](int index) = 0;
    virtual int GetLen() = 0;
    virtual void AddItem(T t) = 0;
    virtual void RemoveItem() = 0;
    virtual void ClearItem() = 0;

};

4.定义一个具体的聚合类ConcreteAggregate,实现抽象聚合类中的工厂方法返回一个具体的聚合对象迭代器，同时实现相应的元素存储相关的操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Concrete Aggregate : 再封装了一次vector
template <typename T>
class ConcreteAggregate : public Aggregate<T>
{
private:
    vector<T> m_vecData;
public:
    void AddItem(T t)
    {
        m_vecData.push_back(t);
    }
    void RemoveItem()
    {
        m_vecData.pop_back();
    }
    void ClearItem()
    {
        m_vecData.clear();
    }
    T& operator[](int index)    // 重载[]
    {
        return m_vecData[index];
    }
    int GetLen()
    {
        return m_vecData.size();
    }
    virtual Iterator<T>* CreateIterator()   
    // 实现工厂方法，创建的具体聚合对象迭代器实例      
    {
        return new ConcreteItertor<T>(this); // 与当前聚合相关联的迭代器(this)  客户端负责创建和释放Iterator
    }
};

5.测试迭代器模式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void IteratorTest_General()
{
    // 创建聚合对象
    Aggregate<int> *pA = new ConcreteAggregate<int>;
    pA->AddItem(1);
    pA->AddItem(2);
    pA->AddItem(3);
    pA->AddItem(4);

    // 创建迭代器
    Iterator<int> *pI = pA->CreateIterator(); // 可以再次创建

    //遍历迭代器
    for (pI->First(); !pI->IsDone(); pI->Next())
    {
        cout << "Item: " << *(pI->Current()) << endl;
    }

    SAFE_RELASE_POINTER(pA);
    SAFE_RELASE_POINTER(pI); // 手动释放创建的迭代器
}

6.运行结果：

Item: 1
Item: 2
Item: 3
Item: 4

迭代器模式的分类

在迭代器模式结构图中，我们可以看到具体迭代器类和具体聚合类之间存在双重关系，其中一个关系为关联关系，在具体迭代器中需要维持一个对具体聚合对象的引用，该关联关系的目的是访问存储在聚合对象中的数据，以便迭代器能够对这些数据进行遍历操作，除了引用方式，还可以在聚合类的内部定义迭代器，迭代器模式根据具体迭代器的实现在具体聚合类的内部还是外部，可以分为两类：

外部迭代器模式

即一般模式的迭代器，具体迭代器需要一个聚合对象引用，通过关联关系来关联两个层次结构，即上述的例子实现

内部迭代器模式

具体迭代器的实现在聚合类的内部定义和实现,将具体的迭代器作为聚合类的内部类即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// Concrete Aggregate : 再封装了一次vector
template <typename T>
class ConcreteAggregate : public Aggregate<T>
{
private:
    vector<T> m_vecData;
public:
    /************************************************************************/
    /* 内部迭代器实现                                                                     */
    /************************************************************************/
    template <typename T>         // 外部实现迭代器，模板类ConcreteItertor定义，需要template <typename(class) T>
    class ConcreteItertor: public Iterator<T>
    {
    private:
        Aggregate<T> *m_pAggr;             // 与某个聚合对象联系的迭代器
        int m_cur; 
    public:
        ConcreteItertor(Aggregate<T> *pAggr) : m_pAggr(pAggr), m_cur(0) {}; 
    public:
        virtual void First()
        {
            m_cur = 0;
        }
        virtual void Next()
        {
            if (m_cur < (m_pAggr->GetLen()))
            {
                m_cur++;
            }
        }
        virtual T* Current()
        {
            if (m_cur < (m_pAggr->GetLen()))
            {
                return &((*m_pAggr)[m_cur]); //  重载了操作符[]
            }
            else
            {
                return NULL;
            }
        }
        virtual bool IsDone()
        {
            return (m_cur >= (m_pAggr->GetLen()));
        }
    };
    /************************************************************************/
    /* 内部迭代器实现                                                                     */
    /************************************************************************/
public:
    void AddItem(T t)
    {
        m_vecData.push_back(t);
    }
    void RemoveItem()
    {
        m_vecData.pop_back();
    }
    void ClearItem()
    {
        m_vecData.clear();
    }
    T& operator[](int index)    // 重载[]
    {
        return m_vecData[index];
    }
    int GetLen()
    {
        return m_vecData.size();
    }
    virtual Iterator<T>* CreateIterator()
    {
        return new ConcreteItertor<T>(this); // 与当前聚合相关联的迭代器，外部实现迭代器
    }
};

无论使用哪种实现机制，客户端代码都是一样的，也就是说客户端无须关心具体迭代器对象的创建细节，只需通过调用工厂方法createIterator()即可得到一个可用的迭代器对象

使用场景

  • 访问一个聚合对象的内容而无须暴露它的内部表示。将聚合对象的访问与内部数据的存储分离，使得访问聚合对象时无须了解其内部实现细节
    -需要为一个聚合对象提供多种遍历方式
  • 为遍历不同的聚合结构提供一个统一的接口，在该接口的实现类中为不同的聚合结构提供不同的遍历方式，而客户端可以一致性地操作该接口

优缺点

  • 优点
    • 支持以不同的方式遍历一个聚合对象，在同一个聚合对象上可以定义多种遍历方式，同时扩展方便
    • 简化了聚合类。由于引入了迭代器，在原有的聚合对象中不需要再自行提供数据遍历等方法，这样可以简化聚合类的设计
  • 缺点
    • 将存储数据和遍历数据的职责分离，增加新的聚合类需要对应增加新的迭代器类，类的个数成对增加，这在一定程度上增加了系统的复杂性

迭代器模式具体实例

STL顺序容器遍历问题

使用迭代器模式简单实现前言所述的STL顺序容器array和list的遍历功能

代码实现
1.定义抽象顺序容器迭代器类SequenceIterator:

1
2
3
4
5
6
7
8
9
10
// Abstract Sequence Iterator
template <class T>
class SequenceIterator
{
public:
    virtual void first() = 0;
    virtual void next() = 0;
    virtual T& currentItem() = 0;
    virtual bool isdone() = 0;
};

2.分别定义具体的顺序容器迭代器类ArrayIterator和ListIterator,并实现相应的遍历操作接口:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// Concrete Array Iterator
template <class T>
class Array;

template <class T>
class ArrayIterator : public SequenceIterator<T>
{
private:
    Array<T> *m_pArray;
    int m_curpos;
public:
    ArrayIterator(Array<T> *pArray): m_pArray(pArray) {}; //与具体的聚合对象关联的迭代器
public:
    virtual void first()
    {
        m_curpos = 0;
    }
    virtual void next()
    {
        m_curpos++;
    }
    virtual T& currentItem()
    {
        return (*m_pArray)[m_curpos];
    }
    virtual bool isdone()
    {
        return (m_curpos >= (m_pArray->GetSize()));
    }
};

// Concrete List Iterator
template <class T>
class List;

template <class T>
//  a typedef template is illegal
/*typedef struct tag_Node
{
    T Value;
    tag_Node *pNext;
}Node;  
 可以用using C++11
*/
struct Node
{
    T Value;
    Node<T> *pNext;
};
//List的结点

template <class T>
class ListIterator : public SequenceIterator<T>
{
private:
    List<T>   *m_pList;
    Node<T>   *m_pcurNode;
public:
    ListIterator(List<T> *m_List): m_pList(m_List) {}; //与具体的聚合对象关联的迭代器
public:
    virtual void first()
    {
        m_pcurNode = m_pList->GetHeader();
    }
    virtual void next()
    {
        m_pcurNode = m_pcurNode->pNext;
    }
    virtual T& currentItem()
    {
        return m_pcurNode->Value;
    }
    virtual bool isdone()
    {
        return (m_pcurNode == m_pList->GetTailerPast());
    }
};

3.定义抽象的顺序容器聚合类Sequence,声明存储元素操作和迭代器工厂方法CreateIterator():

1
2
3
4
5
6
7
8
9
10
// Abstract Sequence
template <typename T>
class Sequence
{
    virtual SequenceIterator<T>* CreateIterator() = 0;
    virtual int  GetSize() = 0;
    virtual void PushBack(T t) = 0;
    virtual T&   PopBack() = 0;
    virtual void Clear() = 0;;
};

4.分别定义具体的容器类Array及List,实现存储元素操作和迭代器工厂方法CreateIterator()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
// Concrete Sequence : Array,通过数组方式实现
template <typename T>
#define ARRAY_MAX_SIZE 100
class Array : public Sequence<T>    // []只有
{
private:
    T m_data[ARRAY_MAX_SIZE];
    int m_count;
public:
    Array()
    {
        memset(m_data, 0, sizeof(T)* ARRAY_MAX_SIZE);
        m_count = 0;
    }
public:
    virtual SequenceIterator<T>* CreateIterator()
    //具体的工厂方法，返回array iterator
    { 
        return new ArrayIterator<T>(this);
    }
    virtual int GetSize()
    {
        return m_count;
    }
    virtual void PushBack(T t)
    {
        if (m_count >= ARRAY_MAX_SIZE)
        {
            cout << "Array Is Full" << endl;
            return;
        }
        m_data[m_count++] = t;
        if (m_count >= ARRAY_MAX_SIZE) // 最后一次PUSH之后，初始化curindex = ARRAY_MAX_SIZE - 1;
        {
            m_count = ARRAY_MAX_SIZE - 1;
        }
    }
    virtual T& PopBack()
    {
        T res = 0;
        if (m_count < 0)
        {
            cout << "Array Is Empty" << endl;
            return res;
        }
        res = m_data[--m_count];
        m_data[m_count] = 0;
        if (m_count < 0) // 最后一次POP之后，初始化curindex = 0;
        {
            m_count = 0;
        }
        return res;
    }
    virtual void Clear()
    {
        memset(m_data, 0, sizeof(T)* ARRAY_MAX_SIZE);
        m_count = 0;        
    }
public:  // Array 特有的方法
    T& operator[](int index)
    {
        T res = 0;
        if ((index < 0) || (index >= ARRAY_MAX_SIZE))
        {
            cout << "Index Is Out Of Array Range" << endl;
            return res;
        }
        res = m_data[index];
        return res;
    }
};

// Concrete Sequence : List,通过单链表方式实现
template <typename T>
class List : public Sequence<T> //->只有
{
private:
    Node<T> *m_pHead;
    Node<T> *m_pTail;
    int   m_Count;
public:
    List()
    {
        m_pHead = NULL;
        m_pTail = NULL;
        m_Count = 0;
    }
    virtual ~List()
    {
        Clear();
    }
public:
    virtual SequenceIterator<T>* CreateIterator()
     //具体的工厂方法，返回list iterator
    {
        return new ListIterator<T>(this);
    }
    virtual int GetSize()
    {
        return m_Count;
    }
    virtual void PushBack(T t)
    {
        Node<T> *pNewNode = new Node<T>;
        pNewNode->Value = t;
        pNewNode->pNext = NULL;

        if (NULL_POINTER(m_pHead)) // 空的List
        {
            m_pHead = m_pTail = pNewNode;
        }
        else
        {
            m_pTail->pNext = pNewNode;
            m_pTail = pNewNode;
        }
        ++m_Count;
    }
    virtual T& PopBack()
    {
        T res = 0;
        if (NULL_POINTER(m_pHead))
        {
            cout << "List Is Empty" << endl;
            return res;
        }

        Node<T> *pTmp = m_pHead;
        while (pTmp->pNext != m_pTail && (m_pHead != m_pTail)) // 找出m_pTail的前面一个结点，即pTmp->pNext = m_pTail
        {
            pTmp = pTmp->pNext;
        }

        res = m_pTail->Value;  // 最后一个是m_pTail
        if (m_pHead == m_pTail)
        {
            m_pHead =  NULL; // m_pHead 防止指针悬挂，野指针
        }
        SAFE_RELASE_POINTER(m_pTail);
        m_pTail = pTmp;
        m_pTail->pNext = NULL; // 最后一个结点的pNext = NULL,便于删除的时候判断
        pTmp    = NULL;
        --m_Count;

        return res;
    }
    virtual void Clear()
    {
        Node<T> *pTmp = m_pHead;
        while (!NULL_POINTER(pTmp))
        {
            m_pHead = pTmp->pNext;
            SAFE_RELASE_POINTER(pTmp);
            pTmp = m_pHead;
        }
    }

public: // List 特有的方法
    Node<T>* GetHeader()
    {
        return m_pHead;
    }
    Node<T>* GetTailerPast()
    {
        if (NULL_POINTER(m_pTail))
        {
            return NULL;
        }
        return m_pTail->pNext;
    }
};

5.测试迭代器模式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void IteratorTest_Sequence()
{
    cout << "Before Array Pop Back:" << endl;
    Array<int> *pA = new Array<int>;
    pA->PushBack(10);
    pA->PushBack(20);
    pA->PushBack(30);
    pA->PushBack(40);
    SequenceIterator<int> *pIA = pA->CreateIterator();
    for (pIA->first(); !pIA->isdone(); pIA->next())
    {
        cout << "Array: " << pIA->currentItem() << endl;
    }

    cout << "After Array Pop Back:" << endl;
    int arrayPopRes = pA->PopBack();
    cout << "Array Pop Result is: " << arrayPopRes << endl;
    for (pIA->first(); !pIA->isdone(); pIA->next())
    {
        cout << "Array: " << pIA->currentItem() << endl;
    }

    cout << "Before List Pop Back:" << endl;
    List<int> *pL = new List<int>;
    pL->PushBack(100);
    pL->PushBack(200);
    pL->PushBack(300);
    pL->PushBack(400);
    SequenceIterator<int> *pIL = pL->CreateIterator();
    for (pIL->first(); !pIL->isdone(); pIL->next())
    {
        cout << "List: " << pIL->currentItem() << endl;
    }

    cout << "After List Pop Back:" << endl;
    int listPopRes = pL->PopBack();
    cout << "List Pop Result is: " << listPopRes << endl;
    for (pIL->first(); !pIL->isdone(); pIL->next())
    {
        cout << "List: " << pIL->currentItem() << endl;
    }

    SAFE_RELASE_POINTER(pA);
    SAFE_RELASE_POINTER(pIA);

    SAFE_RELASE_POINTER(pL);
    SAFE_RELASE_POINTER(pIL);
}

6.运行结果:

Before Array Pop Back:
Array: 10
Array: 20
Array: 30
Array: 40
After Array Pop Back:
Array Pop Result is: 40
Array: 10
Array: 20
Array: 30
Before List Pop Back:
List: 100
List: 200
List: 300
List: 400
After List Pop Back:
List Pop Result is: 400
List: 100
List: 200
List: 300