iterator:軟件設計模式-中文百科頻道

定義結構

然而在前一種情況，容器承受了過多的功能，它不僅要負責自己“容器”内的元素維護（添加、删除等等），而且還要提供遍曆自身的接口；而且由于遍曆狀态保存的問題，不能對同一個容器對象同時進行多個遍曆。第二種方式倒是省事，卻又将容器的内部細節暴露無遺。

而叠代器模式的出現，很好的解決了上面兩種情況的弊端。先來看下叠代器模式的真面目吧。

叠代器模式由以下角色組成：

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

using namespace std;

template

class BinaryTree;

template

class Iterator;

template

class BinaryTreeNode

{

public:

typedef BinaryTreeNode NODE;

typedef BinaryTreeNode* NODE_PTR;