一、概述
Iterator（迭代器）模式又稱Cursor（游標）模式，用于提供一種方法順序訪問一個聚合對象中各個元素, 而又不需暴露該對象的內部表示。或者這樣說可能更容易理解：Iterator模式是運用于聚合對象的一種模式，通過運用該模式，使得我們可以在不知道對象內部表示的情況下，按照一定順序（由iterator提供的方法）訪問聚合對象中的各個元素。
由于Iterator模式的以上特性：與聚合對象耦合，在一定程度上限制了它的廣泛運用，一般僅用于底層聚合支持類，如STL的list、vector、stack等容器類及ostream_iterator等擴展iterator。
根據STL中的分類，iterator包括：
Input Iterator：只能單步向前迭代元素，不允許修改由該類迭代器引用的元素。
Output Iterator：該類迭代器和Input Iterator極其相似，也只能單步向前迭代元素，不同的是該類迭代器對元素只有寫的權力。
Forward Iterator：該類迭代器可以在一個正確的區間中進行讀寫操作，它擁有Input Iterator的所有特性，和Output Iterator的部分特性，以及單步向前迭代元素的能力。
Bidirectional Iterator：該類迭代器是在Forward Iterator的基礎上提供了單步向后迭代元素的能力。
Random Access Iterator：該類迭代器能完成上面所有迭代器的工作，它自己獨有的特性就是可以像指針那樣進行算術計算，而不是僅僅只有單步向前或向后迭代。
這五類迭代器的從屬關系，如下圖所示，其中箭頭A→B表示，A是B的強化類型，這也說明了如果一個算法要求B，那么A也可以應用于其中。
圖1、五種迭代器之間的關系
vector 和deque提供的是RandomAccessIterator，list提供的是BidirectionalIterator，set和map提供的 iterators是 ForwardIterator，關于STL中iterator的更多信息。
二、結構
Iterator模式的UML結構如下圖所示：
三、應用
Iterator模式有三個重要的作用：
1）它支持以不同的方式遍歷一個聚合 復雜的聚合可用多種方式進行遍歷，如二叉樹的遍歷，可以采用前序、中序或后序遍歷。迭代器模式使得改變遍歷算法變得很容易: 僅需用一個不同的迭代器的實例代替原先的實例即可，你也可以自己定義迭代器的子類以支持新的遍歷，或者可以在遍歷中增加一些邏輯，如有條件的遍歷等。
2）迭代器簡化了聚合的接口 有了迭代器的遍歷接口，聚合本身就不再需要類似的遍歷接口了，這樣就簡化了聚合的接口。
3）在同一個聚合上可以有多個遍歷 每個迭代器保持它自己的遍歷狀態，因此你可以同時進行多個遍歷。
4）此外，Iterator模式可以為遍歷不同的聚合結構（需擁有相同的基類）提供一個統一的接口，即支持多態迭代。
簡 單說來，迭代器模式也是Delegate原則的一個應用，它將對集合進行遍歷的功能封裝成獨立的Iterator，不但簡化了集合的接口，也使得修改、增 加遍歷方式變得簡單。從這一點講，該模式與Bridge模式、Strategy模式有一定的相似性，但Iterator模式所討論的問題與集合密切相關， 造成在Iterator在實現上具有一定的特殊性，具體將在示例部分進行討論。
四、優缺點
正如前面所說，與集合密切相關，限制了 Iterator模式的廣泛使用，就個人而言，我不大認同將Iterator作為模式提出的觀點，但它又確實符合模式“經常出現的特定問題的解決方案”的 特質，以至于我又不得不承認它是個模式。在一般的底層集合支持類中，我們往往不愿“避輕就重”將集合設計成集合 + Iterator 的形式，而是將遍歷的功能直接交由集合完成，以免犯了“過度設計”的詬病，但是，如果我們的集合類確實需要支持多種遍歷方式（僅此一點仍不一定需要考慮 Iterator模式，直接交由集合完成往往更方便），或者，為了與系統提供或使用的其它機制，如STL算法，保持一致時，Iterator模式才值得考 慮。
五、舉例
可以考慮使用兩種方式來實現Iterator模式：內嵌類或者友元類。通常迭代類需訪問集合類中的內部數據結構，為此，可在集合類中設置迭代類為friend class，但這不利于添加新的迭代類，因為需要修改集合類，添加friend class語句。也可以在抽象迭代類中定義protected型的存取集合類內部數據的函數，這樣迭代子類就可以訪問集合類數據了，這種方式比較容易添加新的迭代方式，但這種方式也存在明顯的缺點：這些函數只能用于特定聚合類，并且，不可避免造成代碼更加復雜。
STL的list::iterator、deque::iterator、rbtree::iterator等采用的都是外部Iterator類的形式，雖然STL的集合類的iterator分散在各個集合類中，但由于各Iterator類具有相同的基類，保持了相同的對外的接口（包括一些traits及tags等，感興趣者請認真閱讀參考1、2），從而使得它們看起來仍然像一個整體，同時也使得應用algorithm成為可能。我們如果要擴展STL的iterator，也需要注意這一點，否則，我們擴展的iterator將可能無法應用于各algorithm。
以下是一個遍歷二叉樹的Iterator的例子，為了方便支持多種遍歷方式，并便于遍歷方式的擴展，其中還使用了Strategy模式（見筆記21）：
（注：1、雖然下面這個示例是本系列所有示例中花費我時間最多的一個，但我不得不承認，它非常不完善，感興趣的朋友，可以考慮參考下面的參考材料將其補充完善，或提出寶貴改進意見。2、 我本想考慮將其封裝成與STL風格一致的形式，使得我們遍歷二叉樹必須通過Iterator來進行，但由于二叉樹在結構上較線性存儲結構復雜，使訪問必須 通過Iterator來進行，但這不可避免使得BinaryTree的訪問變得異常麻煩，在具體應用中還需要認真考慮。3、以下只提供了Inorder<中序>遍歷iterator的實現。）
1 #include <assert.h>
2
3 #include <iostream>
4 #include <xutility>
5 #include <iterator>
6 #include <algorithm>
7 using namespace std;
8
9 template <typename T>
10 class BinaryTree;
11 template <typename T>
12 class Iterator;
13
14 template <typename T>
15 class BinaryTreeNode
16 {
17 public:
18 typedef BinaryTreeNode<T> NODE;
19 typedef BinaryTreeNode<T>* NODE_PTR;
20
21 BinaryTreeNode(const T& element) : data(element), leftChild(NULL), rightChild(NULL), parent(NULL) { }
22 BinaryTreeNode(const T& element, NODE_PTR leftChild, NODE_PTR rightChild)
23 :data(element), leftChild(leftChild), rightChild(rightChild), parent(NULL)
24 {
25 if (leftChild)
26 leftChild->setParent(this);
27 if (rightChild)
28 rightChild->setParent(this);
29 }
30
31 T getData(void) const { return data; }
32 NODE_PTR getLeft(void) const { return leftChild; }
33 NODE_PTR getRight(void) const { return rightChild; }
34 NODE_PTR getParent(void) const { return parent; }
35 void SetData(const T& data) { this->data = item; }
36 void setLeft(NODE_PTR ptr) { leftChild = ptr; ptr->setParent(this); }
37 void setRight(NODE_PTR ptr) { rightChild = ptr; ptr->setParent(this); }
38 void setParent(NODE_PTR ptr) { parent = ptr; }
39 private:
40 T data;
41 NODE_PTR leftChild;
42 NODE_PTR rightChild;
43 NODE_PTR parent; // pointer to parent node, needed by iterator
44
45 friend class BinaryTree<T>;
46 };
posted on 2012-07-16 08:11
王海光 閱讀(757)
評論(0) 編輯 收藏 引用 所屬分類:
Design Pattern