程式設計時,資料會收集在容器(Container),有時必須以一致的方式,取得容器中的資料加以處理,此時可採用迭代器(Iterator)代為尋訪容器或是包裹容器外觀。

若需具體控制迭代細節,開發者可用外部迭代器;若只在乎個別元素處理,則可透過抽象介面提供元素處理方式,由內部迭代器控制迭代細節。

傳統的迭代器模式
不同物件容器內部實作時,會採用不同資料結構,例如ArrayList內部用陣列、LinkedList用鏈結、HashSet用雜湊演算、TreeSet用樹狀結構等。如果開發者同時面對兩種以上的容器造訪需求,直接根據具體容器類型提供的介面,會撰寫出專用的存取邏輯。如果容器實作者可提供迭代器代為存取內部結構,容器使用者無論面對的容器類型為何,都只要針對迭代器外觀操作,以一致邏輯存取元素。

以Java的Collection實作為例,由於Collection規範了iterator()方法須傳回Iterator實作,無論ArrayList、LinkedList、HashSet、TreeSet等,都必須根據內部結構實作Iterator,如果開發者想要存取的元素是收集在Collection,可操作Iterator的hasNext、next、remove等方法,無需考慮Collection內部資料結構。

Collection實作品是將Iterator以內部類別(Inner class),實作在ArrayList、LinkedList、HashSet、TreeSet等類別,讓客戶端完全無需考量結構等細節,那麼如果也想以一致方式存取陣列呢?可結合配接器(Adapter)模式,獨立定義ArrayIterator類別實作Iterator介面,包裹想要迭代的陣列。

實際上,為了讓取得Iterator的方式也能一致,從JDK5後提供了Iterable介面,定義iterator()傳回Iterator,而Collection成為子介面,這使得其他資料型態,也可透過迭代器取得資料,例如可定義IterableString實作Iterable介面,使用IterableString包裹String,以傳回的Iterator迭代字串中字元。

在《Design Patterns: Elements of Reusable Object-Oriented Software》書中,定義了迭代器模式:「提供一種循序(Sequentially)存取聚集(aggregate)物件,但又不曝露底層細節的方式。」Java定義Iterator或Iterable等,正是傳統迭代器的基本實現。

具體控制流程的外部迭代器

無論是從容器內部傳回Iterator實作物件,或是以包裹器(Wrapper)方式實現Iterator,都是外部迭代器的作法,也就是對迭代器的控制權是在客戶端,因此客戶端可掌握迭代過程的整個細節,處理上會有較大的彈性,像是可決定以迴圈或遞迴控制迭代器、控制迭代停止時機,同時操作兩個以上的迭代器進行元素比較,或者是對實現組合(Composite)模式的容器,進行巢狀等更複雜的迭代。

然而,正因為可控制的細節較多,在操作外部迭代器時,也就容易出現較複雜的邏輯。例如在同一個迴圈中同時處理多個子問題,或者是操作某個迭代器尋訪容器元素時,另一執行緒改變了容器內容而造成迭代錯誤的問題,必要時必須對迭代器進行同步控制,或者是讓迭代器實現Fail Fast概念,也就是在錯誤發生時儘快呈現。以Java的Iterator實現為例,在某執行緒使用迭代器而另一執行緒改變容器內容時,會拋出ConcurrentModificationException。

使用迭代器的出發點是不涉及容器結構來存取元素,然而有時關心的是容器中個別元素的處理策略,不在乎迭代流程,此時可結合策略(Strategy)模式,傳回不同的迭代器實作。

例如,重載(Overload)iterator方法,接收可針對元素進行轉換處理的物件,使傳回的迭代器在迭代時傳回轉換後的結果,像是迭代字元陣列時,將小寫字母轉為大寫;或者是重載iterator方法,接收一個可針對元素進行true、false判斷,使得透過迭代器取得的元素,是容器中元素集合的子集。

不過,使用外部迭代器實現以上概念,會使得程式碼繁雜,尤其是對於沒有一級(First-class)函式的語言來說,更是如此;另一方面,使用外部迭代器不可避免地,就是操作迭代器的方式,必然是線性的,然而有時對容器中的物件可以分而治之,以多個執行緒分別對容器中不同區段元素進行處理,使用外部迭代器,則顯然不容易作到這點。

抽象控制流程的內部迭代器
如果對迭代器的控制權不在客戶端,而是實現在某個方法中,這稱為內部迭代器。實際上,客戶端並不會真正接觸到迭代器,而是呼叫某個方法,該方法內部以某種方式尋訪元素,對客戶端來說,迭代器的概念被抽象化為迭代方法或某個動作。

以循序存取為例,JavaScript中的陣列擁有forEach方法,開發者可以傳入具備單參數的函式,forEach會將元素逐一傳入函式,然而取得元素時是採用迴圈、遞迴,甚至其他方式,開發者不得而知。

由於客戶端無法控制迭代流程,內部迭代器作法對客戶端較不具彈性,然而以抽象的外觀封裝迭代細節,客戶端可擁有較高階的語意,邏輯簡潔而清晰;如果關心容器中個別元素的處理策略,可使用高階的抽象方法名稱,像是迭代字元陣列時,想將小寫字母轉為大寫,可寫為['a', 'b', 'c'].map(function(c) { return c.toUpperCase(); },過濾一組數字,可寫為[1, 3, 2, 5, 4, 9, 8].filter(function(n) { return n > 4 })。

由於內部迭代器被抽象化了,也有了許多最佳化的可行時機。例如,對於極大的資料集合,可以多執行緒分而治之,也許可設計parallel方法,在客戶端需要平行處理時,提供具體的語意選擇,針對parallel傳回的方法進行map、filter等高階迭代處理時,採用分而治之進行處理;另一個例子,是實現惰性求值(Lazy Evaluation),例如在極大資料list上進行list.map(function(ele) {...}).filter(function(ele) {...})時,第一階段並不會對list所有元素進行map處理,而是在filter條件符合時才處理map,如果filter可提前結束,那麼必須map的元素就可大幅減少。

採用內部迭代器使迭代處理流程抽象化,如果語言具備一級函式,撰寫的程式就有簡潔的語意,這也是為何具備一級函式特性的語言中,較常見到內部迭代器的概念,不具一級函式特性的語言中,較常見外部迭代器。以Java而言,JDK7前的版本僅具備外部迭代器,而隨著JDK8的Lambda新語法導入,新的Collection API也開始見到內部迭代器的實現。

考量底層細節的封裝程度
現在迭代器已不再僅是書中提到,用於循序存取容器。有些語言一開始僅提供外部迭代器,有些語言則僅提供內部迭代器,然而在現代語言相互融合優點的情況下,不少語言在改版新增功能時,開始同時提供外部迭代器與內部迭代器,或者是在迭代器的使用,加上更高階語意。

舉例來說,由於從頭至尾循序存取容器中元素,是多數開發者經常的需求,Java在JDK5後提供增強式for迴圈語法,雖然看來是新語法,實則底層是外部迭代器的表現;然而,並非具備迴圈外觀的foreach語法,就是使用外部迭代器的實現,例如Ruby中的for……in語法,實際上,是內部迭代器each方法的語法蜜糖(Syntax sugar);還可提供如Python、Scala、Haskell等語言中List comprehension的語法,讓迭代器語法更接近數學表達式。

回歸到《Design Patterns》書中對迭代器的定義:「……存取聚集物件,但又不曝露底層細節……」,無論是語言提供外部迭代或內部迭代器,或是兩者之間的語法蜜糖封裝,迭代器對客戶端本來就該是抽象的,該採用或提供何種語法的考量點,在於對客戶端而言,底層細節該封裝的程度,必要時,客戶端亦不需意識迭代器存在。

 

作者簡介


Advertisement

更多 iThome相關內容