Go container包的介绍

目录

• 1.简介

• 2.list

• 2.1数据结构

• 2.2插入元素

• 3.ring

• 3.1数据结构

• 4.heap

• 4.1数据结构

1.简介

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

• List：Go中对链表的实现，其中List：双向链表，Element：链表中的元素

• Ring：实现的是一个循环链表，也就是我们俗称的环

• Heap：Go中对堆的实现
  

2.list

简单实用：

func main()  {
// 初始化双向链表
l := list.New()
// 链表头插入
l.PushFront(1)
// 链表尾插入
l.PushBack(2)
l.PushFront(3)
// 从头开始遍历
for head := l.Front();head != nil;head = head.Next() {
 fmt.Println(head.Value)
}
}

方法列表：

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 的值

2.1数据结构

节点定义：

type Element struct {
// 后继指针，前向指针
next, prev *Element

// 链表指针，属于哪个链表
list *List

// 节点value
Value interface{}
}

双向链表定义：

type List struct {
 // 根元素
root Element // sentinel list element, only &root, root.prev, and root.next are used
// 实际节点数量
 len  int     // current list length excluding (this) sentinel element
}

初始化：

// 通过工厂方法返回list指针
func New() *List { return new(List).Init() }

func (l *List) Init() *List {
l.root.next = &l.root
l.root.prev = &l.root
l.len = 0
return l
}

这里可以看到root节点作为一个根节点，不承担数据，也不是实际的链表节点，节点数量len没算上它，再初始化的时候，root节点会成为一个只有一个节点的环（前后指针都指向自己）

2.2插入元素

头插法:

func (l *List) Front() *Element {
if l.len == 0 {
 return nil
}
return l.root.next
}

func (l *List) PushFront(v interface{}) *Element {
l.lazyInit()
return l.insertValue(v, &l.root)
}

尾插法:

func (l *List) Back() *Element {
if l.len == 0 {
 return nil
}
return l.root.prev
}

func (l *List) PushBack(v interface{}) *Element {
l.lazyInit()
return l.insertValue(v, l.root.prev)
}

在指定元素后新增元素:

func (l *List) insert(e, at *Element) *Element {
e.prev = at
e.next = at.next
e.prev.next = e
e.next.prev = e
e.list = l
l.len++
return e
}

这里有个延迟初始化的逻辑：lazyInit，把初始化操作延后，仅在实际需要的时候才进行

func (l *List) lazyInit() {
if l.root.next == nil {
 l.Init()
}
}

移除元素：

// remove 从双向链表中移除一个元素e，递减链表的长度，返回该元素e
func (l *List) remove(e *Element) *Element {
 e.prev.next = e.next
 e.next.prev = e.prev
 e.next = nil // 防止内存泄漏
 e.prev = nil // 防止内存泄漏
 e.list = nil
 l.len --
 return e
}

3.ring

Go中提供的ring是一个双向的循环链表，与list的区别在于没有表头和表尾，ring表头和表尾相连，构成一个环

使用demo：

func main()  {

// 初始化3个元素的环，返回头节点
r := ring.New(3)
// 给环填充值
for i := 1;i <= 3;i++{
 r.Value = i
 r = r.Next()
}
sum := 0
// 对环的每个元素进行处理
r.Do(func(i interface{}) {
 sum = i.(int) + sum
})
fmt.Println(sum)
}

方法列表：

type Ring
   func New(n int) *Ring  // 初始化环
   func (r *Ring) Do(f func(interface{}))  // 循环环进行操作
   func (r *Ring) Len() int // 环长度
   func (r *Ring) Link(s *Ring) *Ring // 连接两个环
   func (r *Ring) Move(n int) *Ring // 指针从当前元素开始向后移动或者向前（n 可以为负数）
   func (r *Ring) Next() *Ring // 当前元素的下个元素
   func (r *Ring) Prev() *Ring // 当前元素的上个元素
   func (r *Ring) Unlink(n int) *Ring // 从当前元素开始，删除 n 个元素

3.1数据结构

环节点数据结构：

type Ring struct {
next, prev *Ring // 前继和后继指针
Value      interface{} // for use by client; untouched by this library
}

初始化一个环：后继和前继指针都指向自己

func (r *Ring) init() *Ring {
r.next = r
r.prev = r
return r
}

初始化指定数量个节点的环

func New(n int) *Ring {
if n <= 0 {
 return nil
}
r := new(Ring)
p := r
for i := 1; i < n; i++ {
 p.next = &Ring{prev: p}
 p = p.next
}
p.next = r
r.prev = p
return r
}

遍历环，对个元素执行指定操作：

func (r *Ring) Do(f func(interface{})) {
if r != nil {
 f(r.Value)
 for p := r.Next(); p != r; p = p.next {
  f(p.Value)
 }
}
}

4.heap

Go中堆使用的数据结构是最小二叉树，即根节点比左边子树和右边子树的所有值都小

使用demo：需要实现Interface接口，go中堆都是实现这个接口，定义了排序，插入和删除方法

type Interface interface {
   sort.Interface
   Push(x interface{}) // add x as element Len()
   Pop() interface{}   // remove and return element Len() - 1.
}

实现接口：

// An IntHeap is a min-heap of ints.
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{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*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
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func Example_intHeap() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
fmt.Printf("minimum: ％d\n", (*h)[0])
for h.Len() > 0 {
 fmt.Printf("％d ", heap.Pop(h))
}
// Output:
// minimum: 1
// 1 2 3 5
}

4.1数据结构

上浮：

func Push(h Interface, x interface{}) {
h.Push(x)
up(h, h.Len()-1)
}

func up(h Interface, j int) {
for {
 i := (j - 1) / 2 // parent
 if i == j || !h.Less(j, i) {
  break
 }
 h.Swap(i, j)
 j = i
}
}

下沉：

func Pop(h Interface) interface{} {
n := h.Len() - 1
h.Swap(0, n)
down(h, 0, n)
return h.Pop()
}

func down(h Interface, i0, n int) bool {
i := i0
for {
 j1 := 2*i + 1
 if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
  break
 }
 j := j1 // left child
 if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
  j = j2 // = 2*i + 2  // right child
 }
 if !h.Less(j, i) {
  break
 }
 h.Swap(i, j)
 i = j
}
return i > i0
}

来源：https://blog.csdn.net/weixin_41922289/article/details/121592261