1 意圖

提供一種方法順序訪問一個(gè)聚合對(duì)象中的各個(gè)元素，而又不需暴露該對(duì)象的內(nèi)部表示。

2 別名

游標(biāo)（Curse）

3 動(dòng)機(jī)

一個(gè)聚合對(duì)象，如列表，應(yīng)該提供一種方法來讓別人可以訪問它的元素，而又不需暴露它的內(nèi)部結(jié)構(gòu)，此外，針對(duì)不同的需要，可能要以不同的方式遍歷這個(gè)列表。但是即使可以預(yù)見到所需的那些遍歷操作，你可能也不希望列表的接口中充斥著各種不同遍歷的操作。有時(shí)還可能需要在同一個(gè)列表上同時(shí)進(jìn)行多個(gè)遍歷。

迭代器模式都可幫你解決所有這些問題。這一模式的關(guān)鍵思想是將對(duì)列表的訪問和遍歷從列表對(duì)象中分離出來并放入一個(gè)迭代器對(duì)象中，迭代器類定義了一個(gè)訪問該列表元素的接口。迭代器對(duì)象負(fù)責(zé)跟蹤當(dāng)前的元素，即它知道哪些元素已經(jīng)遍歷過了。

例如，一個(gè)列表（List）類可能需要一個(gè)列表迭代器，它們之間的關(guān)系如下圖：

image.png

在實(shí)例化列表迭代器之前，必須提供遍歷的列表。一旦有了該列表迭代器的實(shí)例，就可以順序地訪問該列表的各個(gè)元素，CurrentItem操作返回表列中的當(dāng)前元素，F(xiàn)irst操作初始化迭代器，使當(dāng)前元素指向列表的第一個(gè)元素 ,Next操作將當(dāng)前元素指針向前推進(jìn)一步，指向下一個(gè)元素, 而IsDone檢查是否已越過最后一個(gè)元素，也就是完成了此次遍歷。

將遍歷機(jī)制與列表對(duì)象分離使我們可以定義不同的迭代器來實(shí)現(xiàn)不同的遍歷策略，而無需在列表接口中列舉它們。例如 , 過濾表列迭代器（FilteringListIterator）可能只訪問那些滿足特定過濾約束條件的元素。

注意迭代器和列表是耦合在一起的，而且客戶對(duì)象必須知道遍歷的是一個(gè)列表而不是其他聚合結(jié)構(gòu)。 最好能有一種辦法使得不需改變客戶代碼即可改變?cè)摼酆项??？梢酝ㄟ^將迭代器的概念推廣到多態(tài)迭代（polymorphic iteration）來達(dá)到這個(gè)目標(biāo)。

例如, 假定我們還有一個(gè)列表的特殊實(shí)現(xiàn)，比如說SkipList[Pug90 ]。SkipList是一種具有類似于平衡樹性質(zhì)的隨機(jī)數(shù)據(jù)結(jié)構(gòu)。我們希望我們的代碼對(duì)List和SkipList對(duì)象都適用。

首先，定義一個(gè)抽象列表類 AbstractList，它提供操作列表的公共接口。類似地，我們也需要一個(gè)抽象的迭代器類Iterator，它定義公共的迭代接口。然后我們可以為每個(gè)不同的列表實(shí)現(xiàn)定義具體的Iterator子類。這樣迭代機(jī)制就與具體的聚合類無關(guān)了。

image.png

余下的問題是如何創(chuàng)建迭代器。既然要使這些代碼不依賴于具體的列表子類 , 就不能僅僅簡(jiǎn)單地實(shí)例化一個(gè)特定的類 , 而要讓列表對(duì)象負(fù)責(zé)創(chuàng)建相應(yīng)的迭代器。這需要列表對(duì)象提供CreateIterator這樣的操作, 客戶請(qǐng)求調(diào)用該操作以獲得一個(gè)迭代器對(duì)象。

創(chuàng)建迭代器是一個(gè)Factory Method模式（3.3）的例子，我們?cè)谶@里用它來使得一個(gè)客戶可向一個(gè)列表請(qǐng)求合適的迭代器。Factory Method模式產(chǎn)生兩個(gè)類層次，一個(gè)是列表的，一個(gè)是迭代器的。CreateIterator是聯(lián)系這兩個(gè)類層次的。

4 適用性

迭代器模式可用來：

• 1 訪問一個(gè)聚合對(duì)象的內(nèi)容而無需暴露它的內(nèi)部表示；
• 2 支持對(duì)聚合對(duì)象的多種遍歷；
• 3 為遍歷不同的聚合結(jié)構(gòu)提供一個(gè)統(tǒng)一的接口 (即, 支持多態(tài)迭代)

5 結(jié)構(gòu)

image.png

6 參與者

• Iterator（迭代器）
  ——迭代器定義訪問和遍歷元素的接口
• concreteIterator（具體迭代器）
  ——具體迭代器實(shí)現(xiàn)迭代器接口
  —— 對(duì)該聚合遍歷時(shí)跟蹤當(dāng)前位置
• Aggregate（聚合）
  —— 聚合定義創(chuàng)建相應(yīng)迭代器對(duì)象的接口
• ConcreteAggregate（具體聚合）
  ——具體聚合實(shí)現(xiàn)創(chuàng)建相應(yīng)迭代器的接口，該操作返回concreteIterator的一個(gè)適當(dāng)?shù)膶?shí)例。

7 協(xié)作

concreteIterator跟蹤聚合中的當(dāng)前對(duì)象，并能夠計(jì)算出待遍歷的后繼對(duì)象。

8 效果

迭代器模式有三個(gè)重要的作用：

• 1 它支持以不同的方式遍歷一個(gè)聚合復(fù)雜的聚合可用多種方式進(jìn)行遍歷。例如 , 代碼生成和語義檢查要遍歷語法分析樹。代碼生成可以按中序或者按前序來遍歷語法分析樹。迭代器模式使得改變遍歷算法變得很容易 : 僅需用一個(gè)不同的迭代器的實(shí)例代替原先的實(shí)例即可。你也可以自己定義迭代器的子類以支持新的遍歷；
• 2 迭代器簡(jiǎn)化了聚合的接口有了迭代器的遍歷接口，聚合本身就不再需要類似的遍歷接口了。這樣就簡(jiǎn)化了聚合的接口。
• 3 在同一個(gè)聚合上可以有多個(gè)遍歷 每個(gè)迭代器保持它自己的遍歷狀態(tài)。因此你可以同時(shí)進(jìn)行多個(gè)遍歷。

9 實(shí)現(xiàn)

迭代器在實(shí)現(xiàn)上有許多變化和選擇。下面是一些較重要的實(shí)現(xiàn)。實(shí)現(xiàn)迭代器模式時(shí)常需要根據(jù)所使用的語言提供的控制結(jié)構(gòu)來進(jìn)行權(quán)衡。一些語言 (例如, CLU[LG86])甚至直接支持這一模式。

• 1 誰控制該迭代 一個(gè)基本的問題是決定由哪一方來控制該迭代 , 是迭代器還是使用該迭代器的客戶。當(dāng)由客戶來控制迭代時(shí) , 該迭代器稱為一個(gè)外部迭代器（external iterator），而當(dāng)由迭代器控制迭代時(shí), 該迭代器稱為一個(gè)內(nèi)部迭代器（internal iterator）。使用外部迭代器的客戶必須主動(dòng)推進(jìn)遍歷的步伐，顯式地向迭代器請(qǐng)求下一個(gè)元素。相反地 , 若使用內(nèi)部迭代器，客戶只需向其提交一個(gè)待執(zhí)行的操作，而迭代器將對(duì)聚合中的每一個(gè)元素實(shí)施該操作。
  外部迭代器比內(nèi)部迭代器更靈活。例如 , 若要比較兩個(gè)集合是否相等，這個(gè)功能很容易用外部迭代器實(shí)現(xiàn)，而幾乎無法用內(nèi)部迭代器實(shí)現(xiàn)。在象 C + +這樣不提供匿名函數(shù)、閉包 , 或象Smalltalk和CLOS這樣不提供連續(xù)( continuation)的語言中，內(nèi)部迭代器的弱點(diǎn)更為明顯。但另一方面, 內(nèi)部迭代器的使用較為容易, 因?yàn)樗鼈円呀?jīng)定義好了迭代邏輯。
• 2 誰定義遍歷算法 迭代器不是唯一可定義遍歷算法的地方。聚合本身也可以定義遍歷算法，并在遍歷過程中用迭代器來存儲(chǔ)當(dāng)前迭代的狀態(tài)。我們稱這種迭代器為一個(gè)游標(biāo)，因?yàn)樗鼉H用來指示當(dāng)前位置?？蛻魰?huì)以這個(gè)游標(biāo)為一個(gè)參數(shù)調(diào)用該聚合的Next操作,而Next操作將改變這個(gè)指示器的狀態(tài)。
  如果迭代器負(fù)責(zé)遍歷算法 , 那么將易于在相同的聚合上使用不同的迭代算法 , 同時(shí)也易于在不同的聚合上重用相同的算法。從另一方面說 , 遍歷算法可能需要訪問聚合的私有變量。如果這樣，將遍歷算法放入迭代器中會(huì)破壞聚合的封裝性。
• 3 迭代器健壯程度如何 在遍歷一個(gè)聚合的同時(shí)更改這個(gè)聚合可能是危險(xiǎn)的。如果在遍歷聚合的時(shí)候增加或刪除該聚合元素 , 可能會(huì)導(dǎo)致兩次訪問同一個(gè)元素或者遺漏掉某個(gè)元素。一個(gè)簡(jiǎn)單的解決辦法是拷貝該聚合，并對(duì)該拷貝實(shí)施遍歷 , 但一般來說這樣做代價(jià)太高。
  一個(gè)健壯的迭代器(robust iterator)保證插入和刪除操作不會(huì)干擾遍歷, 且不需拷貝該聚合。有許多方法來實(shí)現(xiàn)健壯的迭代器。其中大多數(shù)需要向這個(gè)聚合注冊(cè)該迭代器。當(dāng)插入或刪除元素時(shí)，該聚合要么調(diào)整迭代器的內(nèi)部狀態(tài) , 要么在內(nèi)部的維護(hù)額外的信息以保證正確的遍歷。
• 4 附加的迭代器操作迭代器的最小接口由First、Next、IsDone和CurrentItem 操作組成。其他一些操作可能也很有用。例如 , 對(duì)有序的聚合可用一個(gè)Previous操作將迭代器定位到前一個(gè)元素。SkipTo操作用于已排序并做了索引的聚合中，它將迭代器定位到符合指定條件的元素對(duì)象上。
• 5 在C + +中使用多態(tài)的迭代器使用多態(tài)迭代器是有代價(jià)的。它們要求用一個(gè)Factory Method動(dòng)態(tài)的分配迭代器對(duì)象。因此僅當(dāng)必須多態(tài)時(shí)才使用它們。否則使用在棧中分配內(nèi)存的具體的迭代器。
  多態(tài)迭代器有另一個(gè)缺點(diǎn) : 客戶必須負(fù)責(zé)刪除它們。這容易導(dǎo)致錯(cuò)誤 , 因?yàn)槟闳菀淄涐尫乓粋€(gè)使用堆分配的迭代器對(duì)象，當(dāng)一個(gè)操作有多個(gè)出口時(shí)尤其如此。而且其間如果有異常被觸發(fā)的話，迭代器對(duì)象將永遠(yuǎn)不會(huì)被釋放。
• 6 迭代器可有特權(quán)訪問迭代器可被看為創(chuàng)建它的聚合的一個(gè)擴(kuò)展。迭代器和聚合緊密耦合。在C + +中我們可讓迭代器作為它的聚合的一個(gè)友元 (friend )來表示這種緊密的關(guān)系。這樣你就不需要在聚合類中定義一些僅為迭代器所使用的操作。
  但是, 這樣的特權(quán)訪問可能使定義新的遍歷變得很難 , 因?yàn)樗鼘⒁蟾淖冊(cè)摼酆系慕涌谠黾恿硪粋€(gè)友元。為避免這一問題 , 迭代器類可包含一些protected操作來訪問聚合類的重要的非公共可見的成員。迭代器子類 (且只有迭代器子類)可使用這些protected操作來得到對(duì)該聚合的特權(quán)訪問。
• 7 用于復(fù)合對(duì)象的迭代器在Composite ( 4 . 3 )模式中的那些遞歸聚合結(jié)構(gòu)上 , 外部迭代器可能難以實(shí)現(xiàn), 因?yàn)樵谠摻Y(jié)構(gòu)中不同對(duì)象處于嵌套聚合的多個(gè)不同層次， 因此一個(gè)外部迭代器為跟蹤當(dāng)前的對(duì)象必須存儲(chǔ)一條縱貫該 Composite的路徑。有時(shí)使用一個(gè)內(nèi)部迭代器會(huì)更容易一些。它僅需遞歸地調(diào)用自己即可，這樣就隱式地將路徑存儲(chǔ)在調(diào)用棧中，而無需顯式地維護(hù)當(dāng)前對(duì)象位置。如果復(fù)合中的節(jié)點(diǎn)有一個(gè)接口可以從一個(gè)節(jié)點(diǎn)移到它的兄弟節(jié)點(diǎn)、父節(jié)點(diǎn)和子節(jié)點(diǎn) , 那么基于游標(biāo)的迭代器是個(gè)更好的選擇。游標(biāo)只需跟蹤當(dāng)前的節(jié)點(diǎn) ; 它可依賴這種節(jié)點(diǎn)接口來遍歷該復(fù)合對(duì)象。復(fù)合常常需要用多種方法遍歷。前序 , 后序, 中序以及廣度優(yōu)先遍歷都是常用的。你可用不同的迭代器類來支持不同的遍歷。
• 8 空迭代器一個(gè)空迭代器(NullIterator)是一個(gè)退化的迭代器 , 它有助于處理邊界條件。根據(jù)定義，一個(gè)NullIterator總是已經(jīng)完成了遍歷：即, 它的IsDone操作總是返回true?？盏魇沟酶菀妆闅v樹形結(jié)構(gòu)的聚合 (如復(fù)合對(duì)象)。在遍歷過程中的每一節(jié)點(diǎn) , 都可向當(dāng)前的元素請(qǐng)求遍歷其各個(gè)子結(jié)點(diǎn)的迭代器。該聚合元素將返回一個(gè)具體的迭代器。但葉節(jié)點(diǎn)元素返回NullIterator的一個(gè)實(shí)例。這就使我們可以用一種統(tǒng)一的方式實(shí)現(xiàn)在整個(gè)結(jié)構(gòu)上的遍歷。

9 代碼示例

github地址