迭代器模式

1 前言

最近非常感伤，总是怀念大学的日子，做梦的时候也常常梦到。梦到大学在电脑前傻傻的敲着键盘，写着代码，对付着数据结构与算法的作业；建立一个链表，遍历链表，打印链表。现在把那个时候声明的链表的头文件拿出来看看:

复制代码
 1 typedef struct tagNode
 2 {
 3      int value;
 4      tagNode *pPre;
 5      tagNode *pNext;
 6 }Node;
 7 
 8 class CList
 9 {
10 public:
11      CList();
12      CList(size_t n);
13      ~CList();
14 
15      bool PushBack(int value);
16      bool PopBack(int &value);
17      bool Insert(int pos, int value);
18      bool Delete(int pos);
19      bool IsEmpty();
20      int GetLength();
21 
22      void Print();
23 
24      // To iterate the list
25      bool HasNext();
26      int Next();
27 
28 private:
29      int m_iLength;
30      Node *m_pCurrent;
31      Node *m_pHead;
32      Node *m_pTail;
33 };

再回头看看，自己写的代码都有点不认识了。是的，那个时候，就是直接将链表的创建和遍历都放在一类中，就是为了方便，直到那天看了迭代器设计模式，让我有了一次回过头来重新审视自己写过的代码，认识自己的不足的机会。

2 迭代器模式

在GOF的《设计模式:可复用面向对象软件的基础》一书中对迭代器模式是这样说的：提供一种方法顺序访问一个聚合对象中各个元素，而又不需要暴露该对象的内部表示。

一个聚合对象，就是所谓的对象容器了；作为一个容器，都应该提供一种方法来让别人可以访问它的元素；但是，有的时候，我是不希望遍历容器的人知道我的容器是如何实现的；那该怎么办？就像我在大学那样实现的链表，只提供了从头到尾的遍历，如果我需要从尾到头的遍历呢？是不是我又要添加对应的方法了呢！！！容器的遍历方式千变万化，我们不知道需求是如何的，如果需求变了，那么我们的代码就会发生很大的改动，所以，我们需要去改变；对于上面的代码，当我对同一个链表对象进行多次遍历时，是不是就出现了m_pCurrent对象混乱的局面呢？是的，这一切的一切，都说明，我们必须去将一个容器的内部结构与它的遍历进行解耦，要是出现上面的情况时，我们就无法面对。就好比STL中的容器，它将容器中对象的实现和遍历很好的解耦了，所以，我们就无法知道它的内部是如何组织对象数据的，同时，我们也可以按照我们自己的想法去遍历容器，而不会出现任何差错。在我们的项目中使用迭代器模式就能很好的将容器对象的内部表示与对它的遍历进行解耦。接下来，我们再来详细的总结迭代器模式。

3 UML类图

Iterator：定义迭代器访问和遍历元素的接口；

ConcreteIterator：实现具体的迭代器；

Aggregate：定义的容器，创建相应迭代器对象的接口；

ConcreteAggregate：具体的容器实现创建相应迭代器的接口，该操作返回ConcreteIterator的一个适当的实例。

使用场合

访问一个聚合对象的内容而无需暴露它的内部表示；

支持对聚合对象的多种遍历（从前到后，从后到前）；

为遍历不同的聚合结构提供一个统一的接口，即支持多态迭代。

作用

它支持以不同的方式遍历一个聚合，甚至都可以自己定义迭代器的子类以支持新的遍历；

迭代器简化了聚合的接口，有了迭代器的遍历接口，聚合本身就不再需要类似的遍历接口了。这样就简化了聚合的接口；

在同一个聚合上可以有多个遍历，每个迭代器保持它自己的遍历状态；因此，我们可以同时进行多个遍历。

4 代码实现

复制代码
  1 #include <iostream>
  2 using namespace std;
  3 
  4 typedef struct tagNode
  5 {
  6      int value;
  7      tagNode *pNext;
  8 }Node;
  9 
 10 class JTList
 11 {
 12 public:
 13      JTList() : m_pHead(NULL), m_pTail(NULL){};
 14      JTList(const JTList &);
 15      ~JTList();
 16      JTList &operator=(const JTList &);
 17 
 18      long GetCount() const;
 19      Node *Get(const long index) const;
 20      Node *First() const;
 21      Node *Last() const;
 22      bool Includes(const int &) const;
 23 
 24      void Append(const int &);
 25      void Remove(Node *pNode);
 26      void RemoveAll();
 27 
 28 private:
 29      Node *m_pHead;
 30      Node *m_pTail;
 31      long m_lCount;
 32 };
 33 
 34 class Iterator
 35 {
 36 public:
 37      virtual void First() = 0;
 38      virtual void Next() = 0;
 39      virtual bool IsDone() const = 0;
 40      virtual Node *CurrentItem() const  = 0;
 41 };
 42 
 43 class JTListIterator : public Iterator
 44 {
 45 public:
 46      JTListIterator(JTList *pList) : m_pJTList(pList), m_pCurrent(NULL){}
 47 
 48      virtual void First();
 49      virtual void Next();
 50      virtual bool IsDone() const;
 51      virtual Node *CurrentItem() const;
 52 
 53 private:
 54      JTList *m_pJTList;
 55      Node *m_pCurrent;
 56 };
 57 
 58 JTList::~JTList()
 59 {
 60      Node *pCurrent = m_pHead;
 61      Node *pNextNode = NULL;
 62      while (pCurrent)
 63      {
 64           pNextNode = pCurrent->pNext;
 65           delete pCurrent;
 66           pCurrent = pNextNode;
 67      }
 68 }
 69 
 70 long JTList::GetCount()const
 71 {
 72      return m_lCount;
 73 }
 74 
 75 Node *JTList::Get(const long index) const
 76 {
 77      // The min index is 0, max index is count - 1
 78      if (index > m_lCount - 1 || index < 0)
 79      {
 80           return NULL;
 81      }
 82 
 83      int iPosTemp = 0;
 84      Node *pNodeTemp = m_pHead;
 85      while (pNodeTemp)
 86      {
 87           if (index == iPosTemp++)
 88           {
 89                return pNodeTemp;
 90           }
 91           pNodeTemp = pNodeTemp->pNext;
 92      }
 93      return NULL;
 94 }
 95 
 96 Node *JTList::First() const
 97 {
 98      return m_pHead;
 99 }
100 
101 Node *JTList::Last() const
102 {
103      return m_pTail;
104 }
105 
106 bool JTList::Includes(const int &value) const
107 {
108      Node *pNodeTemp = m_pHead;
109      while (pNodeTemp)
110      {
111           if (value == pNodeTemp->value)
112           {
113                return true;
114           }
115           pNodeTemp = pNodeTemp->pNext;
116      }
117      return false;
118 }
119 
120 void JTList::Append(const int &value)
121 {
122      // Create the new node
123      Node *pInsertNode = new Node;
124      pInsertNode->value = value;
125      pInsertNode->pNext = NULL;
126 
127      // This list is empty
128      if (m_pHead == NULL)
129      {
130           m_pHead = m_pTail = pInsertNode;
131      }
132      else
133      {
134           m_pTail->pNext = pInsertNode;
135           m_pTail = pInsertNode;
136      }
137      ++m_lCount;
138 }
139 
140 void JTList::Remove(Node *pNode)
141 {
142      if (pNode == NULL || m_pHead == NULL || m_pTail == NULL)
143      {
144           return;
145      }
146 
147      if (pNode == m_pHead) // If the deleting node is head node
148      {
149           Node *pNewHead = m_pHead->pNext;
150           m_pHead = pNewHead;
151      }
152      else
153      {
154           // To get the deleting node's previous node
155           Node *pPreviousNode = NULL;
156           Node *pCurrentNode = m_pHead;
157           while (pCurrentNode)
158           {
159                pPreviousNode = pCurrentNode;
160                pCurrentNode = pCurrentNode->pNext;
161                if (pCurrentNode == pNode)
162                {
163                     break;
164                }
165           }
166 
167           // To get the deleting node's next node
168           Node *pNextNode = pNode->pNext;
169 
170           
              // If pNextNode is NULL, it means the deleting node is the tail node, 
              // we should change the m_pTail pointer

171           if (pNextNode == NULL)
172           {
173                m_pTail = pPreviousNode;
174           }
175 
176           // Relink the list
177           pPreviousNode->pNext = pNextNode;
178      }
179 
180      // Delete the node
181      delete pNode;
182      pNode = NULL;
183      --m_lCount;
184 }
185 
186 void JTList::RemoveAll()
187 {
188      delete this;
189 }
190 
191 void JTListIterator::First()
192 {
193      m_pCurrent = m_pJTList->First();
194 }
195 
196 void JTListIterator::Next()
197 {
198      m_pCurrent = m_pCurrent->pNext;
199 }
200 
201 bool JTListIterator::IsDone() const
202 {
203      return m_pCurrent == m_pJTList->Last()->pNext;
204 }
205 
206 Node *JTListIterator::CurrentItem() const
207 {
208      return m_pCurrent;
209 }
210 
211 int main()
212 {
213      JTList *pJTList = new JTList;
214      pJTList->Append(10);
215      pJTList->Append(20);
216      pJTList->Append(30);
217      pJTList->Append(40);
218      pJTList->Append(50);
219      pJTList->Append(60);
220      pJTList->Append(70);
221      pJTList->Append(80);
222      pJTList->Append(90);
223      pJTList->Append(100);
224 
225      Iterator *pIterator = new JTListIterator(pJTList);
226 
227      // Print the list by JTListIterator
228      for (pIterator->First(); !pIterator->IsDone(); pIterator->Next())
229      {
230           cout<<pIterator->CurrentItem()->value<<"->";
231      }
232      cout<<"NULL"<<endl;
233 
234      // Test for removing
235      Node *pDeleteNode = NULL;
236      for (pIterator->First(); !pIterator->IsDone(); pIterator->Next())
237      {
238           pDeleteNode = pIterator->CurrentItem();
239           if (pDeleteNode->value == 100)
240           {
241                pJTList->Remove(pDeleteNode);
242                break;
243           }
244      }
245 
246      // Print the list by JTListIterator
247      for (pIterator->First(); !pIterator->IsDone(); pIterator->Next())
248      {
249           cout<<pIterator->CurrentItem()->value<<"->";
250      }
251      cout<<"NULL"<<endl;
252 
253      delete pIterator;
254      delete pJTList;
255 
256      return 0;
257 }

output

10->20->30->40->50->60->70->80->90->100->NULL
10->20->30->40->50->60->70->80->90->NULL

代码中实现了一个单向链表，将链表与迭代器解耦。对于多态迭代，添加抽象类AbstractJTList，声明如下：

class AbstractJTList
{
public:
     virtual Iterator *GetIterator() const = 0;
};

类JTList继承该抽象类，并实现GetIterator，如下：

Iterator *JTList::GetIterator() const
{
     return new JTListIterator(this);
}

好了，这样的话，在客户端就不用去new JTListIterator了，只需要这样：

Iterator *pIterator = pJTList->GetIterator();

这就完全好了；但是，这样又出现另外一个问题，我在GetIterator中new了一个JTListIterator，对于客户端来说，我并不知道这个new操作的存在，就会出现客户端不会去释放这个new开辟的内存，那么如何实现这个内存的自动释放呢。好了，就结合迭代器模式，再将之前总结的RAII机制再实际运用一次。

根据RAII机制，需要将这个迭代器进行封装，让它具有自动释放的功能，就得借助另一个类，如下：

复制代码
class IteratorPtr
{
public:
     IteratorPtr(Iterator *pIterator) : m_pIterator(pIterator){}
     ~IteratorPtr() { delete m_pIterator; }

     Iterator *operator->(){ return m_pIterator; }
     Iterator &operator*() { return *m_pIterator; }

private:
     IteratorPtr(const IteratorPtr &);
     IteratorPtr &operator=(const IteratorPtr &);
     void *operator new(size_t size);
     void operator delete(void *);

private:
     Iterator *m_pIterator;
};

我们在使用的时候，就像下面这样：

IteratorPtr pIterator(pJTList->GetIterator());

这样就省去了释放迭代器的麻烦了。

5 总结

迭代器模式是一个很经典的模式。但是，就是因为它太经典了，如果每次都要程序员去重复造轮子，就有点说不过去了，所以，现在基本成型的类库，都非常好的实现了迭代器模式，在使用这些类库提供的容器时，并不需要我们亲自去实现对应的迭代器；就好比STL了。但是话又说回来了，如此经典的东西，你不去学习是不是很可惜啊；是吧，在当今社会，技多不压身。好了，永远记住，设计模式是一种思想，并不是一层不变的，一种思想，你懂的。

本页共36段，2094个字符，5122 Byte(字节)


大
中
小
↓
∨