Go: 迭代器

Posted on Edited on In , , Word count in article: 1.2k Reading time ≈ 5 mins.

迭代器

range

特定数据结构的迭代

  • 在一开始，range只能用于数组、切片、字符串、map、可读chan的迭代

  • 数组/切片：

    1
    2
    for idx, val := range slice {
    }

  • map：

    1
    2
    for key, val := range mapp {
    }

  • 字符串：

    1
    2
    for idx, bt := range str {
    }

  • 可读通道

    1
    2
    for elem := range channel {
    }

整型迭代

  • Go 1.22+引入了整型迭代语法糖

  • 1
    2
    3
    4
    5
    for i := range n {
    }
    // 等价于
    for i = 0; i < n; i++ {
    }

  • 同时引入了不含索引变量的版本：

    1
    2
    for range n {
    }

迭代器函数

推送式迭代器

  • 在Go 1.22，引入了Range over func，即迭代器函数，迭代器函数会降低一定的可读性

  • 推送式迭代器函数的形式：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    func Func(...any) func(yield func(T) bool) {
    	// 环境声明...
    	var a T
    	// 返回闭包
    	// 若干次调用 yield(a) ... a 即推送给 临时变量 v 的值
    	return func(yield func(T) bool) {
    		// for 中的 break / return 将使 yield() 返回 false
    		if !yield(a) {
    			return // return 退出闭包函数, 外部 for 结束
    		}
    		// 迭代 a
    		a = DoSth(a)
    	}
    }

    func A() {
    	// 使用
    	for v := range Func(n) {
    		// body
    	}
    }

  • 迭代器函数返回一个闭包函数，闭包函数返回空，接收一个回调函数yield

    回调函数yield由运行时自动注入，是外部开发者定义的for块，即：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for v := range Func(n) {
    	// body
    }
    // 等价于
    iterator := Func(n) // 获取提供了指定环境的闭包函数
    // 传递 for 块作为 yield 传递给闭包函数
    // 其中 v 在闭包中由开发者主动推送
    iterator(func(v T) bool {
    	// body
    	return true
    })

  • for体默认在结尾返回true，在遇到break、return等时，体现在yield()里则是返回false

  • 在一切正常时(for体没有break和return)，for执行多少次完全取决于闭包函数内yield()被调用了多少次

    简单的理解就是：range后跟自定义的迭代器函数，迭代器函数返回一个闭包函数

    闭包函数提供v的序列，通过yield()一轮一轮地推送

    yield()是for内的代码块，在结尾自动添加return true以及在特定关键字后添加return false

  • yield()最多支持两个参数，允许只接收一个参数但没有意义

  • Go 1.23引入了iter.Seq[T any]与iter.Seq2[T, S any]，它们简化了迭代器函数的返回值，推送式迭代器和原生的for range的性能相差不大

拉取式迭代器

  • 推送式迭代器的迭代逻辑全部位于闭包函数内，而很多时候迭代器需要由for块主动调用，这种迭代器称为拉取式迭代器

  • Go 1.23引入了iter.Pull[V any](seq Seq[V]) (next func() (V, bool), stop func())和iter.Pull2(...)...，用于将推送式迭代器转化为拉取式迭代器

  • 这个实现原理是：推送式作为生产者会不断调用yield，而Pull在中间添加了一个协程，用于伪装一个yield(并不是for体)，这个协程提供的yield收到推送式迭代器提供的参数后转发给next()，并阻塞式地等待返回值，从而实现阻塞式地迭代

    那么在调用next()时，推送式迭代器调用的yield就是协程提供的yield

  • 但是这种实现方式并不常用，因为先实现一个推送式迭代器再启用一个协程带来更大的复杂度和性能损耗，但和使用闭包并没有很大的区别

  • stop()则是向生产者协程主动发送停止信号，让它停止阻塞式地等待消费者的信号

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    import "iter"

    func A() {
    	next, stop := iter.Pull[int](seq)
    	defer stop()

    	for range n {
    		v := next()
    	}
    }

标准库的迭代器

slices

  • All[Slice ~[]E, E any](s Slice) iter.Seq2[int, E]：将切片转换成切片迭代器，内部实际上就是for range s，一般用于数据流处理
  • Values[Slice ~[]E, E any](s Slice) iter.Seq[E]：转换成不返回索引的切片迭代器
  • Chunk[Slice ~[]E, E any](s Slice, n int) iter.Seq[Slice]：返回若干子切片，切片最多含有n个元素
  • Collect[E any](iter.Seq[E]) []E：将切片迭代器收集成切片

maps

  • Keys()：返回键的迭代器
  • Values()：返回值的迭代器
  • All()：返回键值对的迭代器，和直接使用for range类似，一般用于数据流处理
  • Collect()：将映射表迭代器收集成映射表

流式处理

  • Go采用返回闭包并封装成标准库函数的形式实现迭代器函数，而不是声明一个流对象并以流对象作为接收者和返回值来实现(像Java那样)
  • 因此Go的标准库并不提供链式调用的流式处理，因此调用链长度较长时可读性会下降
  • 因此需要自己实现流式调用形式的，即自己定义一个流对象并封装一系列它的方法，在内部调用slices和maps提供的方法
  • Go目前还不支持匿名函数的简写，需要完整写完函数定义和函数体