iterator

iterator

疊代器(Iterator)模式,又叫做游標(Cursor)模式。GOF給出的定義為:提供一種方法訪問一個容器(container)對象中各個元素,而又不需暴露該對象的內部細節。 從定義可見,疊代器模式是為容器而生。很明顯,對容器對象的訪問必然涉及到遍歷算法。你可以一股腦的將遍歷方法塞到容器對象中去;或者根本不去提供什麼遍歷算法,讓使用容器的人自己去實現去吧。這兩種情況好像都能夠解決問題。

引言

疊代器模式(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>;

};

相關詞條

相關搜尋

熱門詞條

聯絡我們