go 实现迭代器

by · 2018年11月19日 · 1138 Words · ~3min reading time | Improve on


原文链接： go 实现迭代器

匿名函数实现

package main
import "fmt"
type Ints []int
func (i Ints) Iterator() func() (int, bool) {
	index := 0
	return func() (val int, ok bool) {
		if index >= len(i) {
			return
		}
		val, ok = i[index], true
		index++
		return
	}
}

func main() {
	ints := Ints{1, 2, 3}
	next := ints.Iterator()
	for {
		val, ok := next()
		if !ok {
			break
		}
		fmt.Println(val)
	}
}

Do实现

这份迭代器实现是最简洁的，代码也很直白，无须多言。如果想加上中断迭代的功能，可以将func(int)改为func(int)bool，Do中根据返回值决定是否退出迭代。

标准库中的container/ring中有Do()用法的例子。

package main

import "fmt"

type Ints []int

func (i Ints) Do(fn func(int)) {
	for _, v := range i {
		fn(v)
	}
}

func main() {
	ints := Ints{1, 2, 3}
	ints.Do(func(v int) {
		fmt.Println(v)
	})
}

上篇写到C语言中的迭代器，今天写写Go语言中实现迭代器模式的方法。Go语言称为next C，在实现迭代器上，完全可以使用C语言中的思路，语法上更简练。但这里不使用这种经典的方式，而是使用Go语言本身带有的特性。我们会使用它的channel特性、goroutine特性和闭包特性。为了简单表达，这里的实现依旧使用双链表，如果要迭代更复杂的数据结构，比如树型结构，只要修改迭代器的算法实现过程即可。
使用channel特性实现迭代器

迭代器创建一个goroutine在后台迭代数据结构对象，把获得的Element发送到channel上，主线程从channel的另外一端取出Element，然后完成对Element的处理。从而，把可迭代对象（数据结构）的迭代和处理分离开来。channel本身在设计上就是线程安全，因此不用添加额外的锁。

package main
import (
	"container/list"
	"fmt"
)
type Iterator chan *list.Element
func NewIterator(list *list.List, buffer int) Iterator {
	if buffer < 0 {
		buffer = 0
	}
	iter := make(Iterator, buffer)
	go func() {
		for e := list.Front(); e != nil; e = e.Next() {
			iter <- e
		}
		close(iter) // 关闭channel，避免一直阻塞goroutine而引起死锁
	}()
	return iter
}
func main() {
	l := list.New()
	l.PushBack("a")
	l.PushBack("b")
	l.PushBack("c")
	l.PushBack("d")
	l.PushBack("f")
	for v := range NewIterator(list, 0) { // update
		fmt.Println(v.Value.(string))
	}

对于其他更复杂数据结构，迭代过程在go块内实现即可。出于安全考虑，我们还可以把NewIterator函数返回单向的channel。

上述的方法甚至可以更OOP，如下：

func (list *LocalList) NewIterator(buffer int) Iterator {
	if buffer < 0 {
		buffer = 0
	}
	iter := make(Iterator, buffer)
	go func() {
		for e := list.Front(); e != nil; e = e.Next() {
			iter <- e
		}
		close(iter)
	}()
	return iter
}

使用闭包实现迭代器

闭包的特性就是携带函数作用域以外的变量，这些变量可以当做闭包的状态。这样，每次调用闭包（函数），修改外部状态，当调用完毕后，函数销毁，但外部状态还存在，下次调用闭包（函数）时，可以从该状态开始继续执行。利用这种原理，每次调用闭包迭代一次，把迭代的位置（即数据结构的位置）保存到外部状态中，下次从新迭代从外部状态中恢复。

package main
import (
	"container/list"
	"errors"
	"fmt"
)
func NewClosureIterator(l *list.List) func() (value *list.Element, err error) {
	var current *list.Element = l.Front()
	var r *list.Element
	fn := func() (value *list.Element, err error) {
		r = current
		if r == nil {
			return nil, errors.New("StopIteration")
		}
		current = current.Next()
		return r, nil
	}
	return fn
}
func main() {
	l := list.New()
	l.PushBack("a")
	l.PushBack("b")
	l.PushBack("c")
	l.PushBack("d")
	l.PushBack("f")
	next := NewClosureIterator(l)
	for {
		v, err := next()
		if err != nil {
			break
		}
		fmt.Println(v.Value.(string))
	}
}

通过上面的代码发现这种实现有点像装饰器模式，但不对，装饰器模式传入的是函数。对于更复杂的数据结构，迭代算法直接在闭包中实现即可。

Tags:

`