Golang 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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ETEgmIvD9Raj1D0rWWRFeg

猜你喜歡