Six interesting containers in Golang

  • From pkg/container
    • container/list
    • container/ring
    • container/heap
  • Built in
    • map
    • slice
  • Channels as quenues

Container

Container — 容器数据类型:该包实现了三个复杂的数据结构:堆、链表、环

List

Go 语言标准库的 container/list 代码包提供的对 链表 的实现。 这个代码包中有两个公开的程序实体: ListElement, List 实现了一个双向链表,而 Element 则代表了链表中元素的结构。

源码定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// Element 表示链表的一个元素
type Element struct {
	next, prev *Element    // 上一个和下一个元素指针
	list       *List       // 元素所在的链表
	Value      interface{} // 元素值
}

// List 表示一个双向链表
type List struct {
	root Element // 链表的根元素
	len  int     // 链表的长度
}

Demo Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
package main

import (
	"container/list"
	"fmt"
)

func main() {
	var l = list.New()
	e0 := l.PushBack(42)
	e1 := l.PushFront(13)
	e2 := l.PushBack(7)

	l.InsertBefore(3, e0)
	l.InsertAfter(196, e1)
	l.InsertAfter(1729, e2)

	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("%#v\n", e.Value.(int))
	}
}

方法集

List 对应的方法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
type Element
    func (e *Element) Next() *Element                                   // 返回该元素的下一个元素,如果没有下一个元素则返回 nil
    func (e *Element) Prev() *Element                                   // 返回该元素的前一个元素,如果没有前一个元素则返回nil

type List                               
    func New() *List                                                    // 返回一个初始化的list
    func (l *List) Back() *Element                                      // 获取list l的最后一个元素
    func (l *List) Front() *Element                                     // 获取list l的最后一个元素
    func (l *List) Init() *List                                         // list l 初始化或者清除 list l
    func (l *List) InsertAfter(v interface{}, mark *Element) *Element   // 在 list l 中元素 mark 之后插入一个值为 v 的元素,并返回该元素,如果 mark 不是list中元素,则 list 不改变
    func (l *List) InsertBefore(v interface{}, mark *Element) *Element  // 在 list l 中元素 mark 之前插入一个值为 v 的元素,并返回该元素,如果 mark 不是list中元素,则 list 不改变
    func (l *List) Len() int                                            // 获取 list l 的长度
    func (l *List) MoveAfter(e, mark *Element)                          // 将元素 e 移动到元素 mark 之后,如果元素e 或者 mark 不属于 list l,或者 e==mark,则 list l 不改变
    func (l *List) MoveBefore(e, mark *Element)                         // 将元素 e 移动到元素 mark 之前,如果元素e 或者 mark 不属于 list l,或者 e==mark,则 list l 不改变
    func (l *List) MoveToBack(e *Element)                               // 将元素 e 移动到 list l 的末尾,如果 e 不属于list l,则list不改变             
    func (l *List) MoveToFront(e *Element)                              // 将元素 e 移动到 list l 的首部,如果 e 不属于list l,则list不改变             
    func (l *List) PushBack(v interface{}) *Element                     // 在 list l 的末尾插入值为 v 的元素,并返回该元素              
    func (l *List) PushBackList(other *List)                            // 在 list l 的尾部插入另外一个 list,其中l 和 other 可以相等               
    func (l *List) PushFront(v interface{}) *Element                    // 在 list l 的首部插入值为 v 的元素,并返回该元素              
    func (l *List) PushFrontList(other *List)                           // 在 list l 的首部插入另外一个 list,其中 l 和 other 可以相等              
    func (l *List) Remove(e *Element) interface{}                       // 如果元素 e 属于list l将其从 list 中删除并返回元素 e 的值

问题:可以把自己生成的 Element 类型的值传给链表吗?

  • 这里给出一个 典型回答:不会接受,这些上述的方法将不会对链表做出任何改动。 因为我们自己生成的 Element 值并不在链表中,所以也就谈不上 “在链表中移动元素”。更何况链表不允许我们把自己生成的 Element 值插入其中。
  • 问题解析:在 List 包包含的方法中,用于插入新元素的那些方法都只接受 interface{} 类型的值。这些方法在内部会使用 Element 值,包装接收到的新元素。 这样做正是为了避免直接说使用我们自己生成的元素,主要原因是避免链表的内部关联,遭到外界的破坏,这对于链表本身以及我们这些使用者来说都是有益的。

扩展阅读:

  • Wiki: 链表(Linked list):是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。
  • Wiki: 双向链表:又称为双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

知识扩展

问题1:为什么链表可以做到开箱即用?

List 和 Element 都是结构体类型。结构体类型有一个特点,那就是它们的零值都会拥有特定结构,但是没有任何定制化内容的值,相当于一个空壳。值中的字段也都会被分别赋予各自类型的零值。

那么,经过语句 var l list.List 声明的变量 l 的值将会是什么呢?

  • 这个零值将会是一个长度为 0 的链表,这个链表持有的根元素也将会是一个空壳,其中只会包含缺省的内容。那,这样的链表我们可以直接拿来使用吗?
  • 答案是:可以的。这被称为 开箱即用。 这种通过语句 var l list.List 声明的链表 l 可以直接使用的原因就是在于它的 延迟初始化 机制。

延迟初始化

所谓的 延迟初始化:你可以理解为把初始化操作延后,仅在实际需要的时候才进行。延迟初始化的优点在于 “延后”,它可以分散初始化操作带来的计算量和存储空间消耗。

延迟初始化的缺点恰恰也在于“延后”。你可以想象一下,如果我在调用链表的每个方法的时候,它们都需要先去判断链表是否已经被初始化,那这也会是一个计算量上的浪费。在这些方法被非常频繁地调用的情况下,这种浪费的影响就开始显现了,程序的性能将会降低。

Some links:

Ring

container/ring 包中的 Ring 类型实现的是一个循环链表,也就是我们俗称的环。其实 List 在内部就是一个循环链表。它的根元素永远不会持有任何实际的元素值,而该元素的存在就是为了连接这个循环链表的首尾两端。

所以,也可以说:List 的零值是一个只包含了根元素,但不包含任何实际元素值的空链表。那么,既然 Ring 和 List 的本质上都是循环链表,它们到底有什么不同呢?

Ring 和 List 的不同有以下几种:

  • Ring 类型的数据结构仅由它自身即可代表,而 List 类型则需要由它以及 Element 类型联合表示。这是表示方式上的不同,也是结构复杂度上的不同。
  • 一个 Ring 类型的值严格来讲,只代表了其所属的循环链表中的一个元素,而一个 List 类型的值则代表了一个完整的链表。这是表示维度上的不同。
  • 在创建并初始化一个 Ring 值得时候,我们可以指定它包含的元素数量,但是对于一个 List 值来说却不能这样做(也没必要这样做)。循环链表一旦被创建,其长度是不可变的。这是两个代码包中 New 函数在功能上的不同,也是两个类型在初始化值方面的第一个不同
  • 仅通过 var r ring.Ring 语句声明的 r 将会是一个长度为 1 的循环链表,而 List 类型的零值则是一个长度为 0 的链表。别忘了,List 中的根元素不会持有实际元素的值,因此计算长度时不会包含它。这是两个类型在初始化值方面的第二个不同。
  • Ring 值得 Len 方法的算法复杂度是 O(N) 的,而 List 值得 Len 方法的算法复杂度是 O(1)的。这是两者在性能方面最显而易见的差别。

源码定义

1
2
3
4
type Ring struct {
    next, prev  *Ring
    Value       interface{}
}

我们初始化环的时候,需要定义好环的大小,然后对环的每个元素进行赋值。环还提供了一个 Do 方法,能遍历一边环,对每个元素执行一次 func。一个 Demo 如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package main

import (
    "container/ring"
    "fmt"
)

func main() {
	// 创建一个环, 包含 3 个元素
	r := ring.New(3)
	fmt.Printf("ring: %+v\n", *r)

	// 初始化
	for i := 1; i <= 3; i++ {
		r.Value = i
		r = r.Next()
	}
	fmt.Printf("init ring: %+v\n", *r)

	// sum
	s := 0
	r.Do(func(i interface{}) {
        fmt.Println(i)
		s += i.(int)
	})
	fmt.Printf("sum ring: %d\n", s)
}

方法集

Ring 包含的方法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
type Ring
    func New(n int) *Ring               // 用于创建一个新的 Ring, 接收一个整形参数,用于初始化 Ring 的长度  
    func (r *Ring) Len() int            // 环长度
    
    func (r *Ring) Next() *Ring         // 返回当前元素的下个元素
    func (r *Ring) Prev() *Ring         // 返回当前元素的上个元素
    func (r *Ring) Move(n int) *Ring    // 指针从当前元素开始向后移动或者向前(n 可以为负数)

    // Link & Unlink 组合起来可以对多个链表进行管理
    func (r *Ring) Link(s *Ring) *Ring  // 将两个 ring 连接到一起 (r 不能为空)
    func (r *Ring) Unlink(n int) *Ring  // 从当前元素开始,删除 n 个元素

    func (r *Ring) Do(f func(interface{}))  // Do 会依次将每个节点的 Value 当作参数调用这个函数 f, 实际上这是策略方法的引用通过传递不同的函数以在同一个 ring 上实现多种不同的操作

通过 Next & Prev 方法也可以对一个 ring 进行便利,首先保存当前节点,然后依次访问下一个节点,直到回到其实节点,Demo 如下:

1
2
3
4
5
6
7
p := ring.Next()
// do something with the first element

for p != ring {
    // do something with current element
    p = p.Next()
}

Heap

container/heap 中堆使用的数据结构是最小二叉树,即根节点比左边子树和右边子树的所有值都要小。 Go 的堆包只是实现了一个接口,其定义如下:

1
2
3
4
5
type Interface interface {
    sort.Interface
    Push(x interface{})     // Add x as element Len()
    Pop() interfaceP{}      // remove and return element Len() -1.
}

可以看出,这个堆结构继承自 sort.Interface,回顾下 sort.Interface, 它需要实现三个方法

  • Len() int
  • Less(i, j int) bool
  • Swap(i, j int)

加上堆接口定义的两个方法

  • Push(x interface{})
  • Pop() interface{}

就是说你定义了一个堆,就要实现 5 个方法,package doc 的 example 例子:

思考题

  1. container/ring 包中的循环链表的适用场景都有哪些?
  2. 你使用过 container/heap 包中的堆吗? 它的适用场景又有那些呢?

精选留言:

Somebody A:

  • list可以作为queue和 stack 的基础数据结构
  • ring可以用来保存固定数量的元素,例如保存最近100条日志,用户最近10次操作
  • heap可以用来排序。游戏编程中是一种高效的定时器实现方案

Somebody B:

  • list的一个典型应用场景是构造FIFO队列;
  • ring的一个典型应用场景是构造定长环回队列,比如网页上的轮播;
  • heap的一个典型应用场景是构造优先级队列

See Also

Thanks to the authors 🙂