迭代器模式

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ggVHZVhH-1661052140169)(C:/Users/86158/AppData/Roaming/Typora/typora-user-images/image-20220816115459025.png)]

*迭代器模式(Iterator)**:提供一种方法顺序访问一个聚合对象中各个元素,而又*不暴露该对象的内部表示

UML

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-E5HPRPpt-1661052140170)(C:/Users/86158/AppData/Roaming/Typora/typora-user-images/image-20220816120713879.png)]

分析

通过UML可以看出,对于集合Aggregate,其遍历能力被拆了出来,由Iterator负责遍历。

大家可能有疑问,可以用for循环解决的问题,为啥要搞得这么复杂呢?

其实主要看集合结构的复杂性,如果是普通的数组,可以不需要Iterator,直接使用for循环即可。如果是复杂的集合呢?对于这个集合需要有多种遍历方案呢?

如对于图结构,有广度优先、深度优先两种遍历方式,都在图集合里实现,是否感觉违背了职责单一原则。

所以对于复杂结构,迭代器有如下优势

  1. 这种拆分,使集合和迭代器职责更加单一,符合单一职责原则
  2. 迭代器结构统一,方便使用,使用者无需知道遍历细节便可遍历集合
  3. 符合开闭原则,可以按照需求自己开发迭代器,无需改动集合类
  4. 符合里氏替换原则,可以方便的进行迭代方案的更换

通过UML可发现设计思路:迭代器中需要定义first()、isDone()、currentItem()、next() 四个最基本的方法。待遍历的集合对象通过依赖注入传递到迭代器类中。集合可通过CreateIterator() 方法来创建迭代器。

应用场景

迭代器模式一般在library中使用的比较多,毕竟library提供的大多是基础结构。实际业务场景中,很少需要自己编写迭代器。但代码还是要写的,这次写图集合与深度优先遍历迭代器,大家如果对其它类型的图迭代器感兴趣的话,可自行编写。

代码实现

对于二维数组,从[0,0]开始,以广度优先顺序遍历。如对于

1 2

3 4

广度优先遍历顺序为1 2 3 4。

package main
import (
	"fmt"
	"math/rand"
)

/**
 * @Description: 二维数组,当做图集合,写个真正的图集合太麻烦了
 */
type TwoDimensionalArray struct {
	row   int64
	col   int64
	array [][]int64
}

/**
 * @Description: 设置尺寸
 * @receiver t
 * @param row
 * @param col
 */
func (t *TwoDimensionalArray) SetSize(row int64, col int64) {
	t.row = row
	t.col = col
	t.array = make([][]int64, row)
	var i int64 = 0
	for i = 0; i < row; i++ {
		t.array[i] = make([]int64, col)
	}
}

/**
 * @Description: 初始化数据
 * @receiver t
 */
func (t *TwoDimensionalArray) InitDefault() {
	if t.row <= 0 || t.col <= 0 {
		return
	}
	var i, j int64 = 0, 0
	for i = 0; i < t.row; i++ {
		for j = 0; j < t.col; j++ {
			t.array[i][j] = rand.Int63n(200)
		}
	}
}

/**
 * @Description: 格式化输出。不能为指针。
 * @receiver t
 * @return string
 */
func (t TwoDimensionalArray) String() string {
	s := ""
	var i int64 = 0
	for i = 0; i < t.row; i++ {
		s += fmt.Sprintf("%v \n", t.array[i])
	}
	return s
}

/**
 * @Description: 迭代器接口
 */
type Iterator interface {
	First()
	IsDone() bool
	CurrentItem()
	Next()
}

type Pos struct {
	x, y int64
}

/**
 * @Description: 广度优先遍历
 */
type BFSIterator struct {
	data     *TwoDimensionalArray
	used     [][]bool
	queue    []Pos
	index    int64 //queue遍历的位置
	bfsIndex int64 //记录做广度优先遍历的位置
}

/**
 * @Description: 赋值
 * @receiver d
 * @param data
 */
func (d *BFSIterator) Create(data *TwoDimensionalArray) {
	d.data = data
	var i int64 = 0
	d.used = make([][]bool, data.row)
	for i = 0; i < data.row; i++ {
		d.used[i] = make([]bool, data.col)
	}
	d.used[0][0] = true
	d.queue = make([]Pos, 1)
	d.queue[0] = Pos{0, 0}
	d.index = 0
	d.bfsIndex = 0
}

/**
 * @Description: 初始数据
 * @receiver d
 */
func (d *BFSIterator) First() {
	fmt.Println(d.data.array[0][0])
}

/**
 * @Description: 是否遍历结束
 * @receiver d
 * @return bool
 */
func (d *BFSIterator) IsDone() bool {
	if d.index == d.data.col*d.data.row {
		return true
	}
	return false
}

/**
 * @Description: 当前数值
 * @receiver d
 */
func (d *BFSIterator) CurrentItem() {
	pos := d.queue[d.index]
	fmt.Println(d.index, ":", d.data.array[pos.x][pos.y])
}

/**
 * @Description: 移动
 * @receiver d
 */
func (d *BFSIterator) Next() {
	if d.index >= d.data.row*d.data.col {
		fmt.Println("已到最后")
		return
	}
	//说明已经没有了,需要再加几个
	if d.index >= int64(len(d.queue))-1 {
		for d.bfsIndex < int64(len(d.queue)) && d.index < int64(len(d.queue)) {
			curI, curJ := d.queue[d.bfsIndex].x, d.queue[d.bfsIndex].y
			if curJ+1 < d.data.col && d.used[curI][curJ+1] == false {
				d.queue = append(d.queue, Pos{curI, curJ + 1})
				d.used[curI][curJ+1] = true
			}
			if curI+1 < d.data.row && curJ+1 < d.data.col && d.used[curI+1][curJ+1] == false {
				d.queue = append(d.queue, Pos{curI + 1, curJ + 1})
				d.used[curI+1][curJ+1] = true
			}
			if curI+1 < d.data.row && d.used[curI+1][curJ] == false {
				d.queue = append(d.queue, Pos{curI + 1, curJ})
				d.used[curI+1][curJ] = true
			}
			d.bfsIndex++
		}

	}
	d.index++
}

func main() {
	t := TwoDimensionalArray{}
	t.SetSize(3, 3)
	t.InitDefault()
	fmt.Printf("%s", t)

	iterator := BFSIterator{}
	iterator.Create(&t)
	for iterator.IsDone() != true {
		iterator.CurrentItem()
		iterator.Next()
	}
}

输出:

➜ myproject go run main.go

[10 151 21]

[51 137 120]

[158 148 16]

0 : 10

1 : 151

2 : 137

3 : 51

4 : 21

5 : 120

6 : 16

7 : 148

8 : 158

代码写的比较简单,但是仍然能看到迭代器模式的优点。

  1. 可以轻易的变更遍历算法
  2. TwoDimensionalArray可继承于接口,面向接口编程,扩展性会进一步增强

实例

下面是一个简单的自定义数组类型的例子

代码

package iterator

// Iterator 迭代器接口
type Iterator interface {
	HasNext() bool
	Next()
	// 获取当前元素,由于 Go 1.15 中还没有泛型,所以我们直接返回 interface{}
	CurrentItem() interface{}
}

// ArrayInt 数组
type ArrayInt []int

// Iterator 返回迭代器
func (a ArrayInt) Iterator() Iterator {
	return &ArrayIntIterator{
		arrayInt: a,
		index:    0,
	}
}

// ArrayIntIterator 数组迭代
type ArrayIntIterator struct {
	arrayInt ArrayInt
	index    int
}

// HasNext 是否有下一个
func (iter *ArrayIntIterator) HasNext() bool {
	return iter.index < len(iter.arrayInt)-1
}

// Next 游标加一
func (iter *ArrayIntIterator) Next() {
	iter.index++
}

// CurrentItem 获取当前元素
func (iter *ArrayIntIterator) CurrentItem() interface{} {
	return iter.arrayInt[iter.index]
}

单元测试

package iterator

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestArrayInt_Iterator(t *testing.T) {
	data := ArrayInt{1, 3, 5, 7, 8}
	iterator := data.Iterator()
	// i 用于测试
	i := 0
	for iterator.HasNext() {
		assert.Equal(t, data[i], iterator.CurrentItem())
		iterator.Next()
		i++
	}
}

总结

迭代器模式可能对于大部分研发同学来说是不需要的,但对于搞基础框架、搞语言的同学来说应该经常会用。对于迭代器模式,并不是说学习怎么使用,更重要的一点是需要感知设计模式的思想内核。