GoF設(shè)計(jì)模式之迭代器模式

上一篇：【Go實(shí)現(xiàn)】實(shí)踐GoF的23種設(shè)計(jì)模式：觀察者模式

簡單的分布式應(yīng)用系統(tǒng)（示例代碼工程）：https://github.com/ruanrunxue/Practice-Design-Pattern--Go-Implementation

簡介

有時(shí)會(huì)遇到這樣的需求，開發(fā)一個(gè)模塊，用于保存對(duì)象；不能用簡單的數(shù)組、列表，得是紅黑樹、跳表等較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)；有時(shí)為了提升存儲(chǔ)效率或持久化，還得將對(duì)象序列化；但必須給客戶端提供一個(gè)易用的 API，允許方便地、多種方式地遍歷對(duì)象，絲毫不察覺背后的數(shù)據(jù)結(jié)構(gòu)有多復(fù)雜。

對(duì)這樣的 API，很適合使用迭代器模式（Iterator Pattern）實(shí)現(xiàn)。

GoF 對(duì) 迭代器模式 的定義如下：

Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

從描述可知，迭代器模式主要用在訪問對(duì)象集合的場(chǎng)景，能夠向客戶端隱藏集合的實(shí)現(xiàn)細(xì)節(jié)。

Java 的 Collection 家族、C++ 的 STL 標(biāo)準(zhǔn)庫，都是使用迭代器模式的典范，它們?yōu)榭蛻舳颂峁┝撕唵我子玫?API，并且能夠根據(jù)業(yè)務(wù)需要實(shí)現(xiàn)自己的迭代器，具備很好的可擴(kuò)展性。

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

場(chǎng)景上下文

在簡單的分布式應(yīng)用系統(tǒng)（示例代碼工程）中，db 模塊用來存儲(chǔ)服務(wù)注冊(cè)和監(jiān)控信息，它的主要接口如下：

//demo/db/db.go
packagedb
//Db數(shù)據(jù)庫抽象接口
typeDbinterface{
CreateTable(t*Table)error
CreateTableIfNotExist(t*Table)error
DeleteTable(tableNamestring)error

Query(tableNamestring,primaryKeyinterface{},resultinterface{})error
Insert(tableNamestring,primaryKeyinterface{},recordinterface{})error
Update(tableNamestring,primaryKeyinterface{},recordinterface{})error
Delete(tableNamestring,primaryKeyinterface{})error

...
}

從增刪查改接口可以看出，它是一個(gè) key-value 數(shù)據(jù)庫，另外，為了提供類似關(guān)系型數(shù)據(jù)庫的按列查詢能力，我們又抽象出Table對(duì)象：

//demo/db/table.go
packagedb
//Table數(shù)據(jù)表定義
typeTablestruct{
namestring
recordTypereflect.Type
recordsmap[interface{}]record
}

其中，Table底層用map存儲(chǔ)對(duì)象數(shù)據(jù)，但并沒有存儲(chǔ)對(duì)象本身，而是從對(duì)象轉(zhuǎn)換而成的record。record的實(shí)現(xiàn)原理是利用反射機(jī)制，將對(duì)象的屬性名 field 和屬性值 value 分開存儲(chǔ)，以此支持按列查詢能力（一類對(duì)象可以類比為一張表）：

//demo/db/record.go
packagedb

typerecordstruct{
primaryKeyinterface{}
fieldsmap[string]int//key為屬性名，value屬性值的索引
values[]interface{}//存儲(chǔ)屬性值
}
//從對(duì)象轉(zhuǎn)換成record
funcrecordFrom(keyinterface{},valueinterface{})(rrecord,eerror){
...//異常處理
vType:=reflect.TypeOf(value)
vVal:=reflect.ValueOf(value)
ifvVal.Type().Kind()==reflect.Pointer{
vType=vType.Elem()
vVal=vVal.Elem()
}
record:=record{
primaryKey:key,
fields:make(map[string]int,vVal.NumField()),
values:make([]interface{},vVal.NumField()),
}
fori:=0;ireturnrecord,nil
}

當(dāng)然，客戶端并不會(huì)察覺 db 模塊背后的復(fù)雜機(jī)制，它們直接使用的仍是對(duì)象：

typetestRegionstruct{
Idint
Namestring
}
funcclient(){
mdb:=db.MemoryDbInstance()
tableName:="testRegion"
table:=NewTable(tableName).WithType(reflect.TypeOf(new(testRegion)))
mdb.CreateTable(table)
mdb.Insert(tableName,"region1",&testRegion{Id:0,Name:"region-1"})
result:=new(testRegion)
mdb.Query(tableName,"region1",result)
}

另外，除了上述按 Key 查詢接口，我們還想提供全表查詢接口，有隨機(jī)和有序 2 種表記錄遍歷方式，并且支持客戶端自己擴(kuò)展遍歷方式。下面使用迭代器模式來實(shí)現(xiàn)該需求。

代碼實(shí)現(xiàn)

這里并沒有按照標(biāo)準(zhǔn)的 UML 結(jié)構(gòu)去實(shí)現(xiàn)，而是結(jié)合工廠方法模式來解決公共代碼的復(fù)用問題：

//demo/db/table_iterator.go
packagedb

//關(guān)鍵點(diǎn)1:定義迭代器抽象接口，允許后續(xù)客戶端擴(kuò)展遍歷方式
//TableIterator表迭代器接口
typeTableIteratorinterface{
HasNext()bool
Next(nextinterface{})error
}

//關(guān)鍵點(diǎn)2:定義迭代器接口的實(shí)現(xiàn)
//tableIteratorImpl迭代器接口公共實(shí)現(xiàn)類
typetableIteratorImplstruct{
//關(guān)鍵點(diǎn)3:定義一個(gè)集合存儲(chǔ)待遍歷的記錄，這里的記錄已經(jīng)排序好或者隨機(jī)打散
records[]record
//關(guān)鍵點(diǎn)4:定義一個(gè)cursor游標(biāo)記錄當(dāng)前遍歷的位置
cursorint
}

//關(guān)鍵點(diǎn)5:在HasNext函數(shù)中的判斷是否已經(jīng)遍歷完所有記錄
func(r*tableIteratorImpl)HasNext()bool{
returnr.cursorlen(r.records)
}

//關(guān)鍵點(diǎn)6:在Next函數(shù)中取出下一個(gè)記錄，并轉(zhuǎn)換成客戶端期望的對(duì)象類型，記得增加cursor
func(r*tableIteratorImpl)Next(nextinterface{})error{
record:=r.records[r.cursor]
r.cursor++
iferr:=record.convertByValue(next);err!=nil{
returnerr
}
returnnil
}

//關(guān)鍵點(diǎn)7:通過工廠方法模式，完成不同類型的迭代器對(duì)象創(chuàng)建
//TableIteratorFactory表迭代器工廠
typeTableIteratorFactoryinterface{
Create(table*Table)TableIterator
}

//隨機(jī)迭代器
typerandomTableIteratorFactorystruct{}
func(r*randomTableIteratorFactory)Create(table*Table)TableIterator{
varrecords[]record
for_,r:=rangetable.records{
records=append(records,r)
}
rand.Seed(time.Now().UnixNano())
rand.Shuffle(len(records),func(i,jint){
records[i],records[j]=records[j],records[i]
})
return&tableIteratorImpl{
records:records,
cursor:0,
}
}

//有序迭代器
//Comparator如果i
typeComparatorfunc(i,jinterface{})bool
//sortedTableIteratorFactory根據(jù)主鍵進(jìn)行排序，排序邏輯由Comparator定義
typesortedTableIteratorFactorystruct{
comparatorComparator
}
func(s*sortedTableIteratorFactory)Create(table*Table)TableIterator{
varrecords[]record
for_,r:=rangetable.records{
records=append(records,r)
}
sort.Sort(newRecords(records,s.comparator))
return&tableIteratorImpl{
records:records,
cursor:0,
}
}

最后，為Table對(duì)象引入TableIterator：

//demo/db/table.go

//Table數(shù)據(jù)表定義
typeTablestruct{
namestring
recordTypereflect.Type
recordsmap[interface{}]record
//關(guān)鍵點(diǎn)8:持有迭代器工廠方法接口
iteratorFactoryTableIteratorFactory//默認(rèn)使用隨機(jī)迭代器
}
//關(guān)鍵點(diǎn)9:定義Setter方法，提供迭代器工廠的依賴注入
func(t*Table)WithTableIteratorFactory(iteratorFactoryTableIteratorFactory)*Table{
t.iteratorFactory=iteratorFactory
returnt
}
//關(guān)鍵點(diǎn)10:定義創(chuàng)建迭代器的接口，其中調(diào)用迭代器工廠完成實(shí)例化
func(t*Table)Iterator()TableIterator{
returnt.iteratorFactory.Create(t)
}

客戶端這樣使用：

funcclient(){
table:=NewTable("testRegion").WithType(reflect.TypeOf(new(testRegion))).
WithTableIteratorFactory(NewSortedTableIteratorFactory(regionIdComparator))
iter:=table.Iterator()
foriter.HashNext(){
next:=new(testRegion)
err:=iter.Next(next)
...
}
}

總結(jié)實(shí)現(xiàn)迭代器模式的幾個(gè)關(guān)鍵點(diǎn)：

1. 定義迭代器抽象接口，目的是提供客戶端自擴(kuò)展能力，通常包含HashNext()和Next()兩個(gè)方法，上述例子為TableIterator。
2. 定義迭代器接口的實(shí)現(xiàn)類，上述例子為tableIteratorImpl，這里主要起到了 Java/C++ 等帶繼承特性語言中，基類的作用，目的是復(fù)用代碼。
3. 在實(shí)現(xiàn)類中持有待遍歷的記錄集合，通常是已經(jīng)排序好或隨機(jī)打散后的，上述例子為tableIteratorImpl.records。
4. 在實(shí)現(xiàn)類中持有游標(biāo)值，記錄當(dāng)前遍歷的位置，上述例子為tableIteratorImpl.cursor。
5. 在HashNext()方法中判斷是否已經(jīng)遍歷完所有記錄。
6. 在Next()方法中取出下一個(gè)記錄，并轉(zhuǎn)換成客戶端期望的對(duì)象類型，取完后增加游標(biāo)值。
7. 通過工廠方法模式，完成不同類型的迭代器對(duì)象創(chuàng)建，上述例子為TableIteratorFactory接口，以及它的實(shí)現(xiàn)，randomTableIteratorFactory和sortedTableIteratorFactory。
8. 在待遍歷的對(duì)象中，持有迭代器工廠方法接口，上述例子為Table.iteratorFactory。
9. 為對(duì)象定義 Setter 方法，提供迭代器工廠的依賴注入，上述例子為Table.WithTableIteratorFactory()方法。
10. 為對(duì)象定義創(chuàng)建迭代器的接口，上述例子為Table.Iterator()方法。

其中，7～9 步是結(jié)合工廠方法模式實(shí)現(xiàn)時(shí)的特有步驟，如果你的迭代器實(shí)現(xiàn)中沒有用到工廠方法模式，可以省略這幾步。

擴(kuò)展

Go 風(fēng)格的實(shí)現(xiàn)

前面的實(shí)現(xiàn)，是典型的面向?qū)ο箫L(fēng)格，下面以隨機(jī)迭代器為例，給出一個(gè) Go 風(fēng)格的實(shí)現(xiàn)：

//demo/db/table_iterator_closure.go
packagedb

//關(guān)鍵點(diǎn)1:定義HasNext和Next函數(shù)類型
typeHasNextfunc()bool
typeNextfunc(interface{})error

//關(guān)鍵點(diǎn)2:定義創(chuàng)建迭代器的方法，返回HashNext和Next函數(shù)
func(t*Table)ClosureIterator()(HasNext,Next){
varrecords[]record
for_,r:=ranget.records{
records=append(records,r)
}
rand.Seed(time.Now().UnixNano())
rand.Shuffle(len(records),func(i,jint){
records[i],records[j]=records[j],records[i]
})
size:=len(records)
cursor:=0
//關(guān)鍵點(diǎn)3:在迭代器創(chuàng)建方法定義HasNext和Next的實(shí)現(xiàn)邏輯
hasNext:=func()bool{
returncursorfunc(nextinterface{})error{
record:=records[cursor]
cursor++
iferr:=record.convertByValue(next);err!=nil{
returnerr
}
returnnil
}
returnhasNext,next
}

客戶端這樣用：

funcclient(){
table:=NewTable("testRegion").WithType(reflect.TypeOf(new(testRegion))).
WithTableIteratorFactory(NewSortedTableIteratorFactory(regionIdComparator))
hasNext,next:=table.ClosureIterator()
forhasNext(){
result:=new(testRegion)
err:=next(result)
...
}
}

Go 風(fēng)格的實(shí)現(xiàn)，利用了函數(shù)閉包的特點(diǎn)，把原本在迭代器實(shí)現(xiàn)的邏輯，放到了迭代器創(chuàng)建方法上。相比面向?qū)ο箫L(fēng)格，省掉了迭代器抽象接口和實(shí)現(xiàn)對(duì)象的定義，看起來更加的簡潔。

總結(jié)幾個(gè)實(shí)現(xiàn)關(guān)鍵點(diǎn)：

1. 聲明HashNext和Next的函數(shù)類型，等同于迭代器抽象接口的作用。
2. 定義迭代器創(chuàng)建方法，返回類型為HashNext和Next，上述例子為ClosureIterator()方法。
3. 在迭代器創(chuàng)建方法內(nèi)，定義HasNext和Next的具體實(shí)現(xiàn)，利用函數(shù)閉包來傳遞狀態(tài)（records和cursor）。

基于 channel 的實(shí)現(xiàn)

我們還能基于 Go 語言中的 channel 來實(shí)現(xiàn)迭代器模式，因?yàn)榍拔牡?db 模塊應(yīng)用場(chǎng)景并不適用，所以另舉一個(gè)簡單的例子：

typeRecordint

func(r*Record)doSomething(){
//...
}

typeComplexCollectionstruct{
records[]Record
}

//關(guān)鍵點(diǎn)1:定義迭代器創(chuàng)建方法，返回只能接收的channel類型
func(c*ComplexCollection)Iterator()<-chanRecord{
//關(guān)鍵點(diǎn)2:創(chuàng)建一個(gè)無緩沖的channel
ch:=make(chanRecord)
//關(guān)鍵點(diǎn)3:另起一個(gè)goroutine往channel寫入記錄，如果接收端還沒開始接收，會(huì)阻塞住
gofunc(){
for_,record:=rangec.records{
ch<-?record
????????}
????//關(guān)鍵點(diǎn)4:寫完后，關(guān)閉channel
close(ch)
}()
returnch
}

客戶端這樣使用：

funcclient(){
collection:=NewComplexCollection()
//關(guān)鍵點(diǎn)5:使用時(shí)，直接通過for-range來遍歷channel讀取記錄
forrecord:=rangecollection.Iterator(){
record.doSomething()
}
}

總結(jié)實(shí)現(xiàn)基于 channel 的迭代器模式的幾個(gè)關(guān)鍵點(diǎn)：

1. 定義迭代器創(chuàng)建方法，返回一個(gè)只能接收的 channel。
2. 在迭代器創(chuàng)建方法中，定義一個(gè)無緩沖的 channel。
3. 另起一個(gè) goroutine 往 channel 中寫入記錄。如果接收端沒有接收，會(huì)阻塞住。
4. 寫完后，關(guān)閉 channel。
5. 客戶端使用時(shí)，直接通過 for-range 遍歷 channel 讀取記錄即可。

帶有 callback 函數(shù)的實(shí)現(xiàn)

還可以在創(chuàng)建迭代器時(shí)，傳入一個(gè) callback 函數(shù)，在迭代器返回記錄前，先調(diào)用 callback 函數(shù)對(duì)記錄進(jìn)行一些操作。

比如，在基于 channel 的實(shí)現(xiàn)例子中，可以增加一個(gè) callback 函數(shù)，將每個(gè)記錄打印出來：

//關(guān)鍵點(diǎn)1:聲明callback函數(shù)類型，以Record作為入?yún)?/span>
typeCallbackfunc(record*Record)
//關(guān)鍵點(diǎn)2:定義具體的callback函數(shù)
funcPrintRecord(record*Record){
fmt.Printf("%+v
",record)
}
//關(guān)鍵點(diǎn)3:定義以callback函數(shù)作為入?yún)⒌牡鲃?chuàng)建方法
func(c*ComplexCollection)Iterator(callbackCallback)<-chanRecord{
ch:=make(chanRecord)
gofunc(){
for_,record:=rangec.records{
//關(guān)鍵點(diǎn)4:遍歷記錄時(shí)，調(diào)用callback函數(shù)作用在每條記錄上
callback(&record)
ch<-?record
????????}
????????close(ch)
}()
returnch
}

funcclient(){
collection:=NewComplexCollection()
//關(guān)鍵點(diǎn)5:創(chuàng)建迭代器時(shí)，傳入具體的callback函數(shù)
forrecord:=rangecollection.Iterator(PrintRecord){
record.doSomething()
}
}

總結(jié)實(shí)現(xiàn)帶有 callback 的迭代器模式的幾個(gè)關(guān)鍵點(diǎn)：

1. 聲明 callback 函數(shù)類型，以 Record 作為入?yún)ⅰ?/li>
2. 定義具體的 callback 函數(shù)，比如上述例子中打印記錄的PrintRecord函數(shù)。
3. 定義迭代器創(chuàng)建方法，以 callback 函數(shù)作為入?yún)ⅰ?/li>
4. 迭代器內(nèi)，遍歷記錄時(shí)，調(diào)用 callback 函數(shù)作用在每條記錄上。
5. 客戶端創(chuàng)建迭代器時(shí)，傳入具體的 callback 函數(shù)。

典型應(yīng)用場(chǎng)景

• 對(duì)象集合/存儲(chǔ)類模塊，并希望向客戶端隱藏模塊背后的復(fù)雜數(shù)據(jù)結(jié)構(gòu)。

• 希望支持客戶端自擴(kuò)展多種遍歷方式。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

• 隱藏模塊背后復(fù)雜的實(shí)現(xiàn)機(jī)制，為客戶端提供一個(gè)簡單易用的接口。

• 支持?jǐn)U展多種遍歷方式，具備較強(qiáng)的可擴(kuò)展性，符合開閉原則。

• 遍歷算法和數(shù)據(jù)存儲(chǔ)分離，符合單一職責(zé)原則。

缺點(diǎn)

• 容易濫用，比如給簡單的集合類型實(shí)現(xiàn)迭代器接口，反而使代碼更復(fù)雜。
• 相比于直接遍歷集合，迭代器效率要更低一些，因?yàn)樯婕暗礁鄬?duì)象的創(chuàng)建，以及可能的對(duì)象拷貝。
• 需要時(shí)刻注意在迭代器遍歷過程中，由原始集合發(fā)生變更引發(fā)的并發(fā)問題。一種解決方法是，在創(chuàng)建迭代器時(shí)，拷貝一份原始數(shù)據(jù)（TableIterator就這么實(shí)現(xiàn)），但存在效率低、內(nèi)存占用大的問題。

與其他模式的關(guān)聯(lián)

迭代器模式通常會(huì)與工廠方法模式一起使用，如前文實(shí)現(xiàn)。

文章配圖

可以在用Keynote畫出手繪風(fēng)格的配圖中找到文章的繪圖方法。

審核編輯：湯梓紅