引言
疊代器模式(Iteratorpattern)
疊代這個名詞對於熟悉Java的人來說絕對不陌生。我們常常使用JDK提供的疊代接口進行javacollection的遍歷：
Iterator it = list.iterator();
while(it.hasNext()){
//using “it.next();”do some businesss logic
}
而這就是關於疊代器模式套用很好的例子。
這也是疊代器最常用的方法。
定義結構
然而在前一種情況，容器承受了過多的功能，它不僅要負責自己“容器”內的元素維護（添加、刪除等等），而且還要提供遍歷自身的接口；而且由於遍歷狀態保存的問題，不能對同一個容器對象同時進行多個遍歷。第二種方式倒是省事，卻又將容器的內部細節暴露無遺。
而疊代器模式的出現，很好的解決了上面兩種情況的弊端。先來看下疊代器模式的真面目吧。
疊代器模式由以下角色組成：
1) 疊代器角色（Iterator）：疊代器角色負責定義訪問和遍曆元素的接口。
2) 具體疊代器角色（Concrete Iterator）：具體疊代器角色要實現疊代器接口，並要記錄遍歷中的當前位置。
3) 容器角色（Container）：容器角色負責提供創建具體疊代器角色的接口。
4) 具體容器角色（Concrete Container）：具體容器角色實現創建具體疊代器角色的接口——這個具體疊代器角色與該容器的結構相關。
疊代器模式的類圖如下：
從結構上可以看出，疊代器模式在客戶與容器之間加入了疊代器角色。疊代器角色的加入，就可以很好的避免容器內部細節的暴露，而且也使得設計符合“單一職責原則”。
注意，在疊代器模式中，具體疊代器角色和具體容器角色是耦合在一起的——遍歷算法是與容器的內部細節緊密相關的。為了使客戶程式從與具體疊代器角色耦合的困境中脫離出來，避免具體疊代器角色的更換給客戶程式帶來的修改，疊代器模式抽象了具體疊代器角色，使得客戶程式更具一般性和重用性。這被稱為多態疊代。
實現自己
在實現自己的疊代器的時候，一般要操作的容器有支持的接口才可以。而且我們還要注意以下問題：
在疊代器遍歷的過程中，通過該疊代器進行容器元素的增減操作是否安全呢？
在容器中存在複合對象的情況，疊代器怎樣才能支持深層遍歷和多種遍歷呢？
以上兩個問題對於不同結構的容器角色，各不相同，值得考慮。
適用情況
由上面的講述，我們可以看出疊代器模式給容器的套用帶來以下好處：
1) 支持以不同的方式遍歷一個容器角色。根據實現方式的不同，效果上會有差別。
2) 簡化了容器的接口。但是在java Collection中為了提高可擴展性，容器還是提供了遍歷的接口。
3) 對同一個容器對象，可以同時進行多個遍歷。因為遍歷狀態是保存在每一個疊代器對象中的。
由此也能得出疊代器模式的適用範圍：
1) 訪問一個容器對象的內容而無需暴露它的內部表示。
2) 支持對容器對象的多種遍歷。
3) 為遍歷不同的容器結構提供一個統一的接口（多態疊代）。
簡介
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）：該類疊代器能完成上面所有疊代器的工作，它自己獨有的特性就是可以像指針那樣進行算術計算，而不是僅僅只有單步向前或向後疊代。
vector 和deque提供的是RandomAccessIterator，list提供的是BidirectionalIterator，set和map提供的 iterators是 ForwardIterator，關於STL中iterator的更多信息，請閱讀參考1或2。
套用
Iterator模式有三個重要的作用：
1）它支持以不同的方式遍歷一個聚合 複雜的聚合可用多種方式進行遍歷，如二叉樹的遍歷，可以採用前序、中序或後序遍歷。疊代器模式使得改變遍歷算法變得很容易: 僅需用一個不同的疊代器的實例代替原先的實例即可，你也可以自己定義疊代器的子類以支持新的遍歷，或者可以在遍歷中增加一些邏輯，如有條件的遍歷等。
2）疊代器簡化了聚合的接口 有了疊代器的遍歷接口，聚合本身就不再需要類似的遍歷接口了，這樣就簡化了聚合的接口。
3）在同一個聚合上可以有多個遍歷 每個疊代器保持它自己的遍歷狀態，因此你可以同時進行多個遍歷。
4）此外，Iterator模式可以為遍歷不同的聚合結構（需擁有相同的基類）提供一個統一的接口，即支持多態疊代。
簡 單說來，疊代器模式也是Delegate原則的一個套用，它將對集合進行遍歷的功能封裝成獨立的Iterator，不但簡化了集合的接口，也使得修改、增 加遍歷方式變得簡單。從這一點講，該模式與Bridge模式、Strategy模式有一定的相似性，但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的實現。）
#include <assert.h>
#include <iostream>
#include <xutility>
#include <iterator>
#include <algorithm>
using namespace std;
template <typename T>
class BinaryTree;
template <typename T>
class Iterator;
template <typename T>
class BinaryTreeNode
{
public:
typedef BinaryTreeNode<T> NODE;
typedef BinaryTreeNode<T>* NODE_PTR;
BinaryTreeNode(const T& element) : data(element), leftChild(NULL), rightChild(NULL), parent(NULL) { }
BinaryTreeNode(const T& element, NODE_PTR leftChild, NODE_PTR rightChild)
:data(element), leftChild(leftChild), rightChild(rightChild), parent(NULL)
{
if (leftChild)
leftChild->setParent(this);
if (rightChild)
rightChild->setParent(this);
}
T getData(void) const { return data; }
NODE_PTR getLeft(void) const { return leftChild; }
NODE_PTR getRight(void) const { return rightChild; }
NODE_PTR getParent(void) const { return parent; }
void SetData(const T& data) { this->data = item; }
void setLeft(NODE_PTR ptr) { leftChild = ptr; ptr->setParent(this); }
void setRight(NODE_PTR ptr) { rightChild = ptr; ptr->setParent(this); }
void setParent(NODE_PTR ptr) { parent = ptr; }
private:
T data;
NODE_PTR leftChild;
NODE_PTR rightChild;
NODE_PTR parent; // pointer to parent node, needed by iterator
friend class BinaryTree<T>;
};
