實踐GoF的設計模式：迭代器模式

摘要：迭代器模式主要用在存取物件集合的場景，能夠向用戶端隱藏集合的實現細節。

本文分享自華為雲社群《【Go實現】實踐GoF的23種設計模式：迭代器模式》，作者：元閏子。

簡介

有時會遇到這樣的需求，開發一個模組，用於儲存物件；不能用簡單的陣列、列表，得是紅黑樹、跳錶等較為複雜的資料結構；有時為了提升儲存效率或持久化，還得將物件序列化；但必須給使用者端提供一個易用的 API，允許方便地、多種方式地遍歷物件，絲毫不察覺背後的資料結構有多複雜。

對這樣的 API，很適合使用 迭代器模式（Iterator Pattern）實現。

GoF 對迭代器模式的定義如下：

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

從描述可知，迭代器模式主要用在存取物件集合的場景，能夠向用戶端隱藏集合的實現細節。

Java 的 Collection 家族、C++ 的 STL 標準庫，都是使用迭代器模式的典範，它們為使用者端提供了簡單易用的 API，並且能夠根據業務需要實現自己的迭代器，具備很好的可延伸性。

UML 結構

場景上下文

在簡單的分散式應用系統（範例程式碼工程）中，db 模組用來儲存服務註冊和監控資訊，它的主要介面如下：

// demo/db/db.go
package db
// Db 資料庫抽象介面
type Db interface {
 CreateTable(t *Table) error
 CreateTableIfNotExist(t *Table) error
 DeleteTable(tableName string) error
 Query(tableName string, primaryKey interface{}, result interface{}) error
 Insert(tableName string, primaryKey interface{}, record interface{}) error
 Update(tableName string, primaryKey interface{}, record interface{}) error
 Delete(tableName string, primaryKey interface{}) error
 ...
}

從增刪查改介面可以看出，它是一個 key-value 資料庫，另外，為了提供類似關係型資料庫的按列查詢能力，我們又抽象出 Table 物件：

// demo/db/table.go
package db
// Table 資料表定義
type Table struct {
    name            string
 recordType reflect.Type
    records         map[interface{}]record
}

其中，Table 底層用 map 儲存物件資料，但並沒有儲存物件本身，而是從物件轉換而成的 record 。record 的實現原理是利用反射機制，將物件的屬性名 field 和屬性值 value 分開儲存，以此支援按列查詢能力（一類物件可以類比為一張表）：

// demo/db/record.go
package db
type record struct {
 primaryKey interface{}
    fields     map[string]int // key為屬性名，value屬性值的索引
    values     []interface{} // 儲存屬性值
}
// 從物件轉換成record
func recordFrom(key interface{}, value interface{}) (r record, e error) {
 ... // 例外處理
 vType := reflect.TypeOf(value)
 vVal := reflect.ValueOf(value)
 if vVal.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()),
 }
 for i := 0; i < vVal.NumField(); i++ {
 fieldType := vType.Field(i)
 fieldVal := vVal.Field(i)
 name := strings.ToLower(fieldType.Name)
 record.fields[name] = i
 record.values[i] = fieldVal.Interface()
 }
 return record, nil
}

當然，使用者端並不會察覺 db 模組背後的複雜機制，它們直接使用的仍是物件：

type testRegion struct {
    Id   int
    Name string
}
func client() {
 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 查詢介面，我們還想提供全表查詢介面，有隨機和有序 2 種表記錄遍歷方式，並且支援使用者端自己擴充套件遍歷方式。下面使用迭代器模式來實現該需求。

程式碼實現

這裡並沒有按照標準的 UML 結構去實現，而是結合工廠方法模式來解決公共程式碼的複用問題：

// demo/db/table_iterator.go
package db
// 關鍵點1: 定義迭代器抽象介面，允許後續使用者端擴充套件遍歷方式
// TableIterator 表迭代器介面
type TableIterator interface {
 HasNext() bool
 Next(next interface{}) error
}
// 關鍵點2: 定義迭代器介面的實現
// tableIteratorImpl 迭代器介面公共實現類
type tableIteratorImpl struct {
 // 關鍵點3: 定義一個集合儲存待遍歷的記錄，這裡的記錄已經排序好或者隨機打散
    records []record
 // 關鍵點4: 定義一個cursor遊標記錄當前遍歷的位置
 cursor  int
}
// 關鍵點5: 在HasNext函數中的判斷是否已經遍歷完所有記錄
func (r *tableIteratorImpl) HasNext() bool {
 return r.cursor < len(r.records)
}
// 關鍵點6: 在Next函數中取出下一個記錄，並轉換成使用者端期望的物件型別，記得增加cursor
func (r *tableIteratorImpl) Next(next interface{}) error {
 record := r.records[r.cursor]
 r.cursor++
 if err := record.convertByValue(next); err != nil {
 return err
 }
 return nil
}
// 關鍵點7: 通過工廠方法模式，完成不同型別的迭代器物件建立
// TableIteratorFactory 表迭代器工廠
type TableIteratorFactory interface {
 Create(table *Table) TableIterator
}
// 隨機迭代器
type randomTableIteratorFactory struct{}
func (r *randomTableIteratorFactory) Create(table *Table) TableIterator {
 var records []record
 for _, r := range table.records {
        records = append(records, r)
 }
 rand.Seed(time.Now().UnixNano())
 rand.Shuffle(len(records), func(i, j int) {
        records[i], records[j] = records[j], records[i]
 })
 return &tableIteratorImpl{
        records: records,
        cursor: 0,
 }
}
// 有序迭代器
// Comparator 如果i<j返回true，否則返回false
type Comparator func(i, j interface{}) bool
// sortedTableIteratorFactory 根據主鍵進行排序，排序邏輯由Comparator定義
type sortedTableIteratorFactory struct {
    comparator Comparator
}
func (s *sortedTableIteratorFactory) Create(table *Table) TableIterator {
 var records []record
 for _, r := range table.records {
        records = append(records, r)
 }
 sort.Sort(newRecords(records, s.comparator))
 return &tableIteratorImpl{
        records: records,
        cursor: 0,
 }
}

最後，為 Table 物件引入 TableIterator：

// demo/db/table.go
// Table 資料表定義
type Table struct {
    name            string
 recordType reflect.Type
    records         map[interface{}]record
 // 關鍵點8: 持有迭代器工廠方法介面
 iteratorFactory TableIteratorFactory // 預設使用隨機迭代器
}
// 關鍵點9: 定義Setter方法，提供迭代器工廠的依賴注入
func (t *Table) WithTableIteratorFactory(iteratorFactory TableIteratorFactory) *Table {
 t.iteratorFactory = iteratorFactory
 return t
}
// 關鍵點10: 定義建立迭代器的介面，其中呼叫迭代器工廠完成範例化
func (t *Table) Iterator() TableIterator {
 return t.iteratorFactory.Create(t)
}

使用者端這樣使用：

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

總結實現迭代器模式的幾個關鍵點：

定義迭代器抽象介面，目的是提供使用者端自擴充套件能力，通常包含 HashNext() 和 Next() 兩個方法，上述例子為 TableIterator。
定義迭代器介面的實現類，上述例子為 tableIteratorImpl，這裡主要起到了 Java/C++ 等帶繼承特性語言中，基礎類別的作用，目的是複用程式碼。
在實現類中持有待遍歷的記錄集合，通常是已經排序好或隨機打散後的，上述例子為 tableIteratorImpl.records。
在實現類中持有遊標值，記錄當前遍歷的位置，上述例子為 tableIteratorImpl.cursor。
在 HashNext() 方法中判斷是否已經遍歷完所有記錄。
在 Next() 方法中取出下一個記錄，並轉換成使用者端期望的物件型別，取完後增加遊標值。
通過工廠方法模式，完成不同型別的迭代器物件建立，上述例子為 TableIteratorFactory 介面，以及它的實現，randomTableIteratorFactory 和 sortedTableIteratorFactory。
在待遍歷的物件中，持有迭代器工廠方法介面，上述例子為 Table.iteratorFactory。
為物件定義 Setter 方法，提供迭代器工廠的依賴注入，上述例子為 Table.WithTableIteratorFactory() 方法。
為物件定義建立迭代器的介面，上述例子為 Table.Iterator() 方法。

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

擴充套件

Go 風格的實現

前面的實現，是典型的物件導向風格，下面以隨機迭代器為例，給出一個 Go 風格的實現：

// demo/db/table_iterator_closure.go
package db
// 關鍵點1: 定義HasNext和Next函數型別
type HasNext func() bool
type Next func(interface{}) error
// 關鍵點2: 定義建立迭代器的方法，返回HashNext和Next函數
func (t *Table) ClosureIterator() (HasNext, Next) {
 var records []record
 for _, r := range t.records {
        records = append(records, r)
 }
 rand.Seed(time.Now().UnixNano())
 rand.Shuffle(len(records), func(i, j int) {
        records[i], records[j] = records[j], records[i]
 })
 size := len(records)
 cursor := 0
 // 關鍵點3: 在迭代器建立方法定義HasNext和Next的實現邏輯
 hasNext := func() bool {
 return cursor < size
 }
 next := func(next interface{}) error {
 record := records[cursor]
        cursor++
 if err := record.convertByValue(next); err != nil {
 return err
 }
 return nil
 }
 return hasNext, next
}

使用者端這樣用：

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

Go 風格的實現，利用了函數閉包的特點，把原本在迭代器實現的邏輯，放到了迭代器建立方法上。相比物件導向風格，省掉了迭代器抽象介面和實現物件的定義，看起來更加的簡潔。

總結幾個實現關鍵點：

宣告 HashNext 和 Next 的函數型別，等同於迭代器抽象介面的作用。
定義迭代器建立方法，返回型別為 HashNext 和 Next，上述例子為 ClosureIterator() 方法。
在迭代器建立方法內，定義 HasNext 和 Next 的具體實現，利用函數閉包來傳遞狀態（records 和 cursor）。

基於 channel 的實現

我們還能基於 Go 語言中的 channel 來實現迭代器模式，因為前文的 db 模組應用場景並不適用，所以另舉一個簡單的例子：

type Record int
func (r *Record) doSomething() {
 // ...
}
type ComplexCollection struct {
    records []Record
}
// 關鍵點1: 定義迭代器建立方法，返回只能接收的channel型別
func (c *ComplexCollection) Iterator() <-chan Record {
 // 關鍵點2: 建立一個無緩衝的channel
 ch := make(chan Record)
 // 關鍵點3: 另起一個goroutine往channel寫入記錄，如果接收端還沒開始接收，會阻塞住
 go func() {
 for _, record := range c.records {
 ch <- record
 }
 // 關鍵點4: 寫完後，關閉channel
 close(ch)
 }()
 return ch
}

使用者端這樣使用：

func client() {
 collection := NewComplexCollection()
 // 關鍵點5: 使用時，直接通過for-range來遍歷channel讀取記錄
 for record := range collection.Iterator() {
 record.doSomething()
 }
}

總結實現基於 channel 的迭代器模式的幾個關鍵點：

定義迭代器建立方法，返回一個只能接收的 channel。
在迭代器建立方法中，定義一個無緩衝的 channel。
另起一個 goroutine 往 channel 中寫入記錄。如果接收端沒有接收，會阻塞住。
寫完後，關閉 channel。
使用者端使用時，直接通過 for-range 遍歷 channel 讀取記錄即可。

帶有 callback 函數的實現

還可以在建立迭代器時，傳入一個 callback 函數，在迭代器返回記錄前，先呼叫 callback 函數對記錄進行一些操作。

比如，在基於 channel 的實現例子中，可以增加一個 callback 函數，將每個記錄列印出來：

// 關鍵點1: 宣告callback函數型別，以Record作為入參
type Callback func(record *Record)
//關鍵點2: 定義具體的callback函數
func PrintRecord(record *Record) {
 fmt.Printf("%+v\n", record)
}
// 關鍵點3: 定義以callback函數作為入參的迭代器建立方法
func (c *ComplexCollection) Iterator(callback Callback) <-chan Record {
 ch := make(chan Record)
 go func() {
 for _, record := range c.records {
 // 關鍵點4: 遍歷記錄時，呼叫callback函數作用在每條記錄上
 callback(&record)
 ch <- record
 }
 close(ch)
 }()
 return ch
}
func client() {
 collection := NewComplexCollection()
 // 關鍵點5: 建立迭代器時，傳入具體的callback函數
 for record := range collection.Iterator(PrintRecord) {
 record.doSomething()
 }
}

總結實現帶有 callback 的迭代器模式的幾個關鍵點：

宣告 callback 函數型別，以 Record 作為入參。
定義具體的 callback 函數，比如上述例子中列印記錄的 PrintRecord 函數。
定義迭代器建立方法，以 callback 函數作為入參。
迭代器內，遍歷記錄時，呼叫 callback 函數作用在每條記錄上。
使用者端建立迭代器時，傳入具體的 callback 函數。

典型應用場景

物件集合/儲存類模組，並希望向使用者端隱藏模組背後的複雜資料結構。
希望支援使用者端自擴充套件多種遍歷方式。

優缺點

優點

隱藏模組背後複雜的實現機制，為使用者端提供一個簡單易用的介面。
支援擴充套件多種遍歷方式，具備較強的可延伸性，符合開閉原則。
遍歷演演算法和資料儲存分離，符合單一職責原則。

缺點

容易濫用，比如給簡單的集合型別實現迭代器介面，反而使程式碼更復雜。
相比於直接遍歷集合，迭代器效率要更低一些，因為涉及到更多物件的建立，以及可能的物件拷貝。
需要時刻注意在迭代器遍歷過程中，由原始集合發生變更引發的並行問題。一種解決方法是，在建立迭代器時，拷貝一份原始資料（TableIterator 就這麼實現），但存在效率低、記憶體佔用大的問題。

與其他模式的關聯

迭代器模式通常會與工廠方法模一起使用，如前文實現。

文章配圖

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

參考

[1] 【Go實現】實踐GoF的23種設計模式：SOLID原則, 元閏子

[2] 【Go實現】實踐GoF的23種設計模式：工廠方法模式, 元閏子

[3] Design Patterns, Chapter 5. Behavioral Patterns, GoF

[4] Iterators in Go, Ewen Cheslack-Postava

[5] 迭代器模式, refactoringguru.cn

點選關注，第一時間瞭解華為雲新鮮技術~