list: 迭代器设计 #118
Comments
|
我思路是这样的，主要是分两步：
1. 设计一个常规的迭代器业务逻辑一个常规的迭代器，即不允许在一个迭代器的遍历过程中（即遍历没到底， 原因在于，若允许集合新增元素，则遍历时可能正常，也可能重复遍历同一个元素；若允许集合删除原色，则遍历时可能正常，也可能漏掉元素。 所以，如果允许遍历时增删元素，遍历结果不可预期，代码实现中要避免这种情况发生。我们可以设计为，遍历过程中，发生集合元素的增删时，遍历报错。伪码如下： c := Collection()
itr := c.Iterator()
el, ok := itr.Next() // ok==true
// 迭代器遍历开始后，集合增加新元素
c.Add(data)
el, ok := itr.Next() // ok == false设计实现迭代器里要有一个 执行迭代器的 2. 在这个迭代器上增加
|
|
设计迭代器，我觉得最主要的作用是，为各种集合类型，提供统一的遍历抽象吧。然后像那些非线性数据结构的集合类型，用for循环也没法遍历，把遍历统一到迭代器，可维护性、可扩展性都更好 |
|
迭代器是提供遍历和修改双重功能的东西。尤其是侧重修改。如果只是单纯的遍历，那么不管是 AsSlice 还是我们额外提供一个 func (list) Iterate(fn func(idx, val)) {
}都可以。现在实际上困扰的是修改的场景。我在前面讲到删除是一个例子，其实还有增加的例子。对于大部分场景来说，如果我们提供一个额外的索引方法： func (list) Index(val) int {}然后用户是可以考虑利用现有的 Add 或者 Delete 方法的。但是在连续操作的时候，也就是连续添加或者删除的时候，这就不适合了。尤其是部分实现它不知道随机访问， 例如 linked list，都是需要从头找过去，那么性能会很差。 |
type IteratedCollection struct{
Collection
}
func (i *IteratedCollection) NewIterator() Iterator {}
type Iterator[T any] interface {
// error 主要有两种：errOverflow, errCollectionSizeChanged
HasNext() error
Next() T, error
}
type CollectionIterator[T any] {
collection Collection[T]
expectedSize int
// 游标字段，这里用数组类结构的集合示意
curIndex int
}
func(c *CollectionIterator[T]) HasNext() error {}
func(c *CollectionIterator[T]) Next() T, error {}这里我的困惑就是，返回 bool 还是返回 error。按照道理来说返回 error 肯定能表达 bool 的语义，但是我主要是顾忌到很多框架类似设计都是返回了 bool，这对于用户来说，看起来会有一点懵逼 |
只校验个数，这种约束较弱也容易被绕过，用户可以通过集合上的增加、删除接口绕过，比如连续调用 我们需要明确一个问题，在迭代期间是否允许集合上能够改变集合状态（元素个数+元素值）的其他操作穿插调用。 如果不允许，那么就要提供检测机制，一旦用户在迭代期间穿插调用集合上的方法就报错。然后在迭代器上实现可以改变集合状态的操作，Delete/Add （相当于一个代理，比较好实现）这种方式实现简单但也比较“侵入”，需要在迭代器和集合内部各自添加，检查机制用以报错”在迭代期间，集合上的操作被调用“ 如果允许，那就要明确迭代器重复遍历、丢数据的情况。 |
不允许。当有一个迭代器实例的时候，只能通过迭代器来修改。 |
|
但是有一些问题，如果我们确实没有办法做到，那么就在注释里面解释清楚，比如说提到先删除一个元素，然后又插入一个一样的元素。如果很难检测这种情况，那么就可以告诉用户。 另外，这里我们在非线程安全的结构里，依旧保持非线程安全的设计，也就是说不要引入原子操作或者加锁。用户应该使用线程安全的数据结构，如果他们希望线程安全的特性 |
这种因数据结构自身实现方式而导致的操作效率问题，不是迭代器能够改变的。如果大部分场景 另外，上面列举的迭代期间删除的例子，我认为是用户自己实现的问题： l := len(list)
for i :=0; i < l; i ++ {
if list[i] == xxx {
list.Delete(i)
}
}
// 相信用户在找到这个bug后，可以改为
l := len(list)
for i :=0; i < l; {
if list[i] == xxx {
list.Delete(i)
l = len(list)
} else {
i ++
}
} |
前面是按bool写的，最后那里考虑，要不要改成error，把两种不同的情况暴露给用户，就改了error。 |
这里，我那个设计是允许的，由于迭代器上调用 |
对，只校验个数不够充分，这里检测的目的是，确保集合没有做过增删操作，以避免上面提到的问题。怎么检查更合理还要再想一下
这个设计，是按线程不安全来设计的，相当于基本面，先把基准的业务逻辑理顺。线程安全的，可以后面再封装 所以，这里考虑的“迭代期间是否允许集合上能够改变集合状态（元素个数+元素值）的其他操作”，主要指， 因此，这里主要考虑类似如下场景，要怎么处理 iter := Collection.Iterator()
el := iter.Next()
// 有迭代器时，这种操作能不能执行，如何判断有没有未执行完的迭代器
Collection.Delete(0)
// 如果能执行上面删除，这里如何保证遍历不丢数据，或者直接报错，废弃这个迭代器
el := iter.Next() |
|
判断有没有迭代器这个，看起来非常困难。除非我们要求使用迭代器的人要调用类似 close 的方法。但是这个就是很恶心。 如果我们认为这个结构始终保持线程不安全的状态，那么我们如果不做任何校验呢？ 对于我们来说，结果就是完全不可预测。但是我们可以通过文档或者注释的形式，告诉用户说你不能这么用。只不过在代码里面，我们就不做校验 |
|
看你们的讨论，感觉你们迭代器和其他语言的不太一样，而且龙跃的例子中，很明显的面向过程的写法： l := len(list)
for i :=0; i < l; i ++ {
if list[i] == xxx {
list.Delete(i)
}
}
// 相信用户在找到这个bug后，可以改为
l := len(list)
for i :=0; i < l; {
if list[i] == xxx {
list.Delete(i)
l = len(list)
} else {
i ++
}
}迭代过程删除代码，为啥要直接delete？按照我的做法，直接链式调用，像 下面是删除不想要数据的例子： list.Filter(func(item any, index int) bool {
return index != xxx // 这里移除不想要的元素
}).Reduce(func(result any, item any, index int) any {
// 这里组装成新的list
}) |
|
LinkList每次需要重新迭代，应该采用重新生成迭代器，而不是直接reset： iter := list.Iter()
iter.Next()
iter.Next()
iter.Next()
iter.Next()
// 重新再生成一个迭代器
iter = list.Iter()
iter.Next()
iter.Next()
iter.Next() |
|
按照我上面提到的，迭代器接口可以只有一个Next的方法 type Iterable interface {
// Next
// 第一个参数: 生成的值 仅第二个参数为false时有效
// 第二个参数: done标记，true表示迭代已结束，第一个返回值不是有效值
Next() (any, bool)
}像 type Iterator struct {
iter types.Iterable
}
func (it *Iterator) Next() (any, bool) {
}
func (it *Iterator) Map(fn func(any) any) *Iterator {
}
func (it *Iterator) Filter(fn func(any) bool) *Iterator {
}
func (it *Iterator) Reduce(base any, fn func(any, any) any) any {
}也可以加上 |
|
说这么多，只是为了推销我的迭代器库[吃瓜] |
|
大佬大佬~~
我先说迭代器：我认为是否支持 Reset 并不是一个关键问题。当然我更加倾向于 xxbiji 的看法，即我们应该新创建一个迭代器，而不是reset。不过我们讨论的问题并不是这个，而是如果我存在一个迭代器的时候，是否应该允许用户通过其它迭代器修改这个结构。如果不允许，是否要考虑禁止的以及如何禁止。这个应该算是我们讨论的核心； 而另外的 map reduce, filter, foreach 方法其实是另外一个主题了，当然从本质上来说我们可以认为迭代器和 StreamAPI 并没太大的区别。如果单纯从语义上来说，我认为迭代器是立刻生效的。也就是如果 iter.Delete()，那么整个数据结构就会立刻发生变更； 而 stream API 是可以通过延迟机制来提高性能的。例如说我们 stream.Filter(p1).Filter(p2).First() 那么直到调用 First 我们才会真的用 p1 和 p2 来过滤数据。 另外从一个修改与否的角度来看，我认为迭代器是可以修改结构的，比如说删除元素。而我更加认为 stream API 应该是只读的。也就是说 map 这种方法，我们并不是修改已有的 stream，而是创建了一个新的 stream。 另外有一个很恶心的限制就是 Go 不支持泛型方法（结构体或者接口本身可以是泛型的），因此类似于 map 之类的 API 其实是设计不出来的： func (s Stream[S]) Map[T any]() Stream[T] // 这种方法是无法通过编译的所以我们现在还是可以先讨论清楚这个问题： |
|
另外就是，泛型的限制导致我们设计的迭代器（stream）API，用户用起来难以避免要做类型断言或者转换之类的东西，我不是很喜欢。 但是如果我们坚持使用泛型，那么就无法保持链式调用并且使用 map 类的方法。 |
|
所以我的迭代器是any到底[吃瓜] 用泛型的话，可以用函数叠加写法，不过，我不喜欢这种写法： Map[int, int](Map[int, int](Filter[int]( Iter , func), func), func)冒失这样写，泛型会自动推导： Map(Map(Filter(iter, func), func), func)但是写法还是很丑 |
|
这种 API 之前我也考虑过，同样觉得很难用。 另外有一个问题，在保持惰性执行这个特性的情况下，怎么解决中途添加元素的问题？例如说我遍历到中间某个元素，我想在后面加一个。这个看起来并不能保持惰性执行的特征。 |
|
我觉得我们可以按照@xxbiji 的做法，将 stream API 做成迭代器。不过还是那个问题： |
我觉得这个直接简单粗暴一点，如果集合对象的数据结构变化了，迭代器需要感知到，然后就fail fast，当然如果结构的变化源自某个迭代器A，那这个迭代器A应该可以自洽，可以让它继续使用 |
我也同意stream是只读的，是可以通过延迟机制来提高性能的，然后我们可以通过stream API对集合做各种处理 不过，我觉得stream和迭代器是不同的，不是同一类东西，但都可以达到类似的目的。 所以这就回到了我上面提到的看法，迭代器的主要作用，是对各种集合类提供统一的遍历抽象，修改集合不是核心职责，甚至为了保证集合修改时迭代器逻辑自洽，还有额外的开销 如果老师的出发点是，遍历集合并做额外的数据处理，可能stream API更能一步到位 |
其实我是同意上面的说法的。迭代器是服务于stream api，迭代器定义的一个数据怎么迭代数据，而stream api怎是处理迭代的数据。 如果担心迭代过程list的数据结构发生变化，那在使用的时候就应该给他加锁： m.Lock()
iter := list.Iter()
list = iter.Map().Filter().Reduce()
m.Unlock() |
这也就是我一直在琢磨的一个问题，就是是否真的有必要去做这种限制。我举个例子来说，我们这个 List 的实现里面相当多的都是非线程安全的实现，即便我们现在增加了这么一个限制，即如果一个迭代器发现用户修改过了这个数据结构，就要报错。那么实际上这是一个典型的check-and-do-something的场景，也就是最少是两个步骤。那么显然不加锁是做不到的。 如果加锁就有另外一个问题：我都是一个非线程安全的结构体，加个屁的锁啊！ 所以我在想，我们的迭代器能不能就将这个问题抛给用户：迭代器一点都不管你会不会一边搞一个迭代器，一边修改原本的数据结构，反正它就是没有感情的执行，不做任何检测。用户自己在使用的时候应该知道，类似于同时使用迭代器和修改原本的结构是不行的，他们需要自己为自己的行为负责。 而站在一个用户的角度来说，我认为初级工程师可能意识不到这个问题。不过也可以预期的是，这一类的场景也不会很多。 |
|
我倾向于用户自己负责 |
|
可以的，那么暂时先不考虑这种禁止修改的问题。用户对此负责 |
|
This issue is inactive for a long time. |
感觉可以不加锁？可以在list里给一个标记位，如果有NewIter就+1，Iter.Next()=false（已经取完的时候）就-1。Delete和Add时候判断一下标记位是否为0。这样是不是就和加锁等价了（非线程安全）？ |
|
尝试给list加一个iterater，写了一个demo。第一次尝试向开源库发pull请求，可能想法比较片面。也希望借此机会学习一些东西。pull request: https://github.com/ecodeclub/ekit/pull/234/files 这个方案可以做到iter的Next和Delete并存，同时约束用户不在有Iter时候Add/Delete。详情见下。
两个接口的实现在IterableListImpl/IterImpl。
|
|
是否可以跟Cpp一样让所有容器提供一个 |
|
其实就是希望提供你说的这种功能。所有的容器类型都支持迭代器，虽然它们的实现不一样，但是 API 英嘎及时一样的 |
|
我感觉稍微有点难，而且现在我也没特别迫切的需求，所以这个 issue 一直停滞不前 |
|
让我思考一下怎么弄 |
|
#255 这个PR里面有我对iterator的设计思路，我觉得tree和list都应该有iterator，可以review下是否合理 |
|
好，我这两天看看 |
|
等我后面再说。 |
仅限中文
使用场景
有一类很常见的需求，就是遍历，发现符合条件的元素，就把它删除。
在目前的 API 里面，很难满足这一类的需求。我们虽然有一个 Delete 的方法，但是 Delete 方法本身接收的是下标。而Delete 本身就可能改变一个元素的下标，所以使用 Delete(idx) 很难达成我们预期的效果。
例如
例如如果我们预期删除 [1, 3, 4] 中的奇数，那么我们这一段类似的代码并不能达成我们的目标，我们会会遗漏，因为当我们删除 1 之后，3 的下标就调整到了 0，而我们已经遍历了下标 0，最终它就会成为漏网之鱼。
我所希望的效果是：
for ele, ok := itr.Next(); ok {
if ele == xxx {
itr.Delete()
}
}
这算是一个比较大的改进，所以如果你想要提供实现，你需要提供一份设计文档。参考
https://github.com/gotomicro/eorm/discussions/66
我们也可以在这里先讨论可行的方案。
你设置的的 Go 环境?
The text was updated successfully, but these errors were encountered: