container 包详解

Go 语言中有一个 container 包，如果只是看这个包名，可能很容易让人误解，但这个 container 和 Docker 之类的容器没有关系。

在 container 包中，有三种开箱即用的数据结构，可以直接使用，分别是 heap、list 和 ring。

heap

heap 中提供了一个堆的实现，可以直接使用。如果想创建一个堆，只需要先实现一些方法，这里以整数堆为例：

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

在上面的实现中，没有对堆的实现，因为 heap 包已经把这些实现抽象出来了，在使用的时候，只需要自己实现堆中数据比较大小的逻辑。上面的代码写完之后，就可以来初始化并使用堆：

h := &IntHeap{2, 1, 5}
heap.Init(h) // 初始化堆

heap.Push(h, 3) // 入堆
heap.Pop(h) // 出堆，拿出堆顶的第一个元素

在 Go 的官方文档中，甚至使用 heap 包实现了一个优先级队列，如果在业务场景中有这个需求，都可以直接使用了。具体见：https://golang.google.cn/pkg/container/heap/

list

list 是一个双向链表的实现，这个数据结构的使用就更简单了，开箱即用：

l := list.New()  // 创建一个双向链表
e4 := l.PushBack(4) // 从后面加入元素
e1 := l.PushFront(1) // 从前面加入元素
l.InsertBefore(3, e4) // 在某个元素之前插入
l.InsertAfter(2, e1) // 在某个元素之后插入

// 按照链表的顺序，从前向后遍历
for e := l.Front(); e != nil; e = e.Next() {
      fmt.Println(e.Value)
}

ring

ring 这个数据结构有点特殊，是一个环状的双向链表，这个数据结构在有些场景下很有用，比如用作任务队列。

这个结构有个好处是内存在初始化的时候申请一次就可以了，其中的内存式可以重复利用了。

使用起来也比较方便，可以使用 Next 和 Prev 方法去获取前面和后面的元素:

r := ring.New(5) // 创建一个大小为 5 的ring

n := r.Len() // 获取 ring 的长度

// 向 ring 中填充数据
for i := 0; i < n; i++ {
    r.Value = i
    r = r.Next()
}

// 打印 ring 中的数据
r.Do(func(p interface{}) {
    fmt.Println(p.(int))
})

ring 中还提供了两个特殊的方法：Link 和 UnLink。

Link 方法可以把两个 ring 连接起来:

r := ring.New(2)
s := ring.New(2)

lr := r.Len()
ls := s.Len()

for i := 0; i < lr; i++ {
    r.Value = 0
    r = r.Next()
}

for j := 0; j < ls; j++ {
    s.Value = 1
    s = s.Next()
}

rs := r.Link(s)

rs.Do(func(p interface{}) {
    fmt.Println(p.(int))
})

UnLink 方法是从 ring 摘除调一些节点，Unlink 的参数是整数 n ，表示从 r.Next 开始，摘除三个元素:

r := ring.New(6)

n := r.Len()

for i := 0; i < n; i++ {
    r.Value = i
    r = r.Next()
}

r.Unlink(3)

r.Do(func(p interface{}) {
    fmt.Println(p.(int))
})

文 / Rayjun