設計模式之迭代器模式

語言: CN / TW / HK

一、背景

之前在分享《 【團隊分享】GO map 原始碼實現 》的時候,介紹了 map 的迭代器實現。

其實,這背後涉及到一種設計模式:迭代器模式。

設計模式的書籍和文章很多,這裡不過多介紹設計模式的概念,而介紹一些使用場景。

二、日常使用

先來看一段程式碼。

for k,v := range m {
  ...
}

相信對於 go 語言,大家平常寫程式碼的時候,經常寫上面的語法。

而對於 cpp 語言,則會寫下面的程式碼

for(auto it = m.begin(); it != m.end(); ++it) {

}

其他語言也都有類似的語法。

不同語言看起來有一些細微差異,但是這些語言底層的實現方式都差不多的。

都是遵循迭代器設計模式帶來的一個好處,語法變得簡潔多了。

三、場景

迭代器模式的優點是,我們不需要理解容器的具體實現,就可以按照某種方法,遍歷這個容器的所有元素。

容器可能很抽象,在 java 裡叫做集合。

簡單的容器有陣列、連結串列、佇列、棧等。

複雜的容器有 hash 表、二叉樹、紅黑樹等。

不管容器是什麼資料結構,我們都不需要關心,迭代器會去封裝好細節。

我們只需要建立迭代器,然後不斷的獲取下個值即可。

這時候你可能會想,直接把迭代器放在對應的容器裡實現就好了。

這樣做正常情況下沒問題,但是當需要同一時間多次使用迭代器時就有問題。

因為迭代器迭代過程中需要儲存一個狀態,在容器內儲存狀態的話,就沒法多次迭代了。

所以,各種語言自帶的迭代器都會封裝一個獨立的迭代器類。

有時候,我們希望根據迭代器的自身的性質,選擇不同的方式來迭代容器。

比如對於二叉樹容器,我們可能希望採用深度優先便利,也可能希望採用廣度優先便利。

這時候,容器的遍歷方式就是隨著訴求的變化而變化了。

而從面向物件的角度,有時候可能會有不同的容器,但是我們不關心這個容器的實現方式。

此時就需要使用抽象迭代器與多型實現了。

四、理論

容器可能是變化的,遍歷演算法可能是變化的,兩個抽象一下,我們就可以設計出一種迭代器模型了。

這個圖看著比較抽象。

實際各語言的內部容器實現上,由於只有一種遍歷演算法與一個容器實現方式,所以都進行了適當的簡化,去掉了多型。

但是,如果我們做專案設計的時候,涉及多種演算法或者多種容器,就需要考慮引入多型了。

五、最後

那我們什麼時候需要使用迭代器,什麼不應該使用迭代器模式呢?

如果資料結構或者遍歷演算法比較複雜時,需要拆分為容器集合類與迭代類,這屬於單一職責原則。

如果後續容器集合要更換資料結構,或者迭代演算法要更換時,建立一個新的具體類即可,這樣就不需要修改現有的程式碼。

另外,由於迭代器時單獨的物件,遍歷的狀態與資料結構無關,所以我們同一時間可以建立多個迭代器。

而專案處於初期,容器非常簡單時,比如陣列,那可以暫時不要引入迭代器模式,以防過度設計。

《完》

-EOF-

本文公眾號:天空的程式碼世界

個人微訊號:tiankonguse

QQ演算法群:165531769(不止演算法)

知識星球:不止演算法