iterator

README

迭代器模式(Iterator Pattern)

迭代器模式，也叫游标模式，将集合(包含一级数据的容器，如数组、链表、树、图和跳表)的遍历操作，从集合中拆分出来，放到迭代器中，让集合和迭代器的职责变得单一。

一个完整的迭代器模式，包含集合和迭代器两部分。为了达到基于接口而非实现编程的目的，集合又包含集合接口、集合实现类，迭代器又包含迭代器接口、迭代器实现类。

一个迭代器接口（Iterator），包含了访问集合对象元素的方法，例如获取下一个元素、判断是否还有元素等。具体的聚合对象（Aggregate）实现迭代器接口，提供具体的迭代器对象（具体迭代器）来遍历聚合对象的元素。

一般来讲，遍历集合有3种方法：for-loop,foreach-loop,iterator。

迭代器模式用于使用相同方式，迭代不同类型集合或者隐藏集合类型的具体实现。

问题及解决方法

1. 在使用迭代器遍历集合的同时，增加或删除集合中的元素，有可能导致某个元素被重复遍历或遍历不到，产生不可预期的遍历结果。

   实际上，不可预期的结果比直接出错更不可接受。 方案一：在迭代器类中定义一个新接口 finishIteration()，使用它主动告知集合，迭代器已经使用完毕，可以添加或删除元素了。 方案二：在添加或删除元素之后，让迭代器的遍历操作报错。

支持快照功能的迭代器

1. 基于多副本

   在迭代器类中，定义一个快照成员变量，每当创建迭代器时，复制一份集合中的元素并放到快照中，这个快照相当于一个副本，后续的遍历操作都在这个副本上进行。 但创建多副本，内存消耗相当大。

2. 基于时间戳

   为每个元素保存添加、删除时间戳，同时每个迭代器也保存一个快照时间戳。当使用迭代器遍历集合时，只有时间戳满足添加<快照<删除的元素，才是这个迭代器应该遍历的元素。 不需要维护多个副本，在集合本身上借助时间戳实现了快照功能。

如何上集合既支持快照遍历，又支持随机访问？ 在集合类中存储两个数组，一个数组支持标记删除，用来实现快照遍历功能；另一个数组不支持标记删除，也就是将要删除的数据直接从数组中移除，用来支持按照下标快速访问。

Documentation

Index

• func IteratorPrint(i Iterator)
• type Aggregate
• type Iterator
• type Numbers
  • func NewNumbers(start, end int) *Numbers
  • func (n *Numbers) Iterator() Iterator
• type NumbersIterator
  • func (i *NumbersIterator) First()
  • func (i *NumbersIterator) IsDone() bool
  • func (i *NumbersIterator) Next() any

Examples

• Iterator

Functions

func IteratorPrint

func IteratorPrint(i Iterator)

Types

type Aggregate

type Aggregate interface {
	Iterator() Iterator
}

type Iterator

type Iterator interface {
	First()
	IsDone() bool
	Next() any
}

Iterator 迭代器接口，包含了访问集合对象元素的方法，例如获取下一个元素、判断是否还有元素等。

Example

aggregate := NewNumbers(1, 10)

IteratorPrint(aggregate.Iterator())

Output:
1
2
3
4
5
6
7
8
9
10

type Numbers

type Numbers struct {
	// contains filtered or unexported fields
}

func NewNumbers

func NewNumbers(start, end int) *Numbers

func (*Numbers) Iterator

func (n *Numbers) Iterator() Iterator

type NumbersIterator

type NumbersIterator struct {
	// contains filtered or unexported fields
}

func (*NumbersIterator) First

func (i *NumbersIterator) First()

func (*NumbersIterator) IsDone

func (i *NumbersIterator) IsDone() bool

func (*NumbersIterator) Next

func (i *NumbersIterator) Next() any