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 代码包提供的对链表的实现。这个代码包中有两个公开的程序实体： List 和 Element, 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 例子：

https://golang.org/pkg/container/heap/#pkg-examples

思考题

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

精选留言：

Somebody A:

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

Somebody B:

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

『Go核心36讲』| 03 - Container 包中的那些容器

Contents

Container

List

源码定义

方法集

扩展阅读：

知识扩展

延迟初始化

Ring

源码定义

方法集

Heap

思考题

See Also