Golang中的container

Posted on Edited on In Views:
golang中的container是源码包的container目录中，主要有三个部分：heap、list、ring。

heap

堆，一种常用的数据结构，最小二叉树，根节点比左节点和右节点都要小。

堆是实现优先级队列的常用方法。

实现interface方法即可使用heap

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

包含了sort的interface

1
2
3
4
5
type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

也就是

1
2
3
4
5
 Push(x any)
 Pop() any
Len() int
Less(i, j int) bool
Swap(i, j int)

实现上述五个方法之后，就实现了堆，可以将最大值或者最小值排列在最前面。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
type student struct {
    id  int
    age int
}

type myHeap []student

func (h *myHeap) Less(i, j int) bool {  // init的时候，将最小的数字放到最前面
    return (*h)[i].age < (*h)[j].age      // 取age的最小值
}

func (h *myHeap) Swap(i, j int) {     
    (*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *myHeap) Len() int {
    return len(*h)
}

func (h *myHeap) Pop() (v any) {
    *h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
    return
}

func (h *myHeap) Push(v any) {
    *h = append(*h, v.(student))
}

func main() {
    students := &myHeap{}
    heap.Init(students) // 初始化heap
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < 10; i++ {
        s := student{
            id:  i,
            age: rand.Intn(100),
        }
        heap.Push(students, s) // 压入数据
    }
    fmt.Println("start: ", students) // 压入数据之后，其实还是数组
    for students.Len() > 0 {         // 当有数据，则继续便利
        fmt.Printf("%+v\n", heap.Pop(students)) // 弹出数据
        fmt.Println("pop after:", students)     // 弹出数据之后
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
start:  &[{2 2} {8 23} {1 51} {3 36} {4 63} {5 98} {6 90} {7 97} {0 94} {9 88}]
{id:2 age:2}
pop after: &[{8 23} {3 36} {1 51} {9 88} {4 63} {5 98} {6 90} {7 97} {0 94}]
{id:8 age:23}
pop after: &[{3 36} {4 63} {1 51} {9 88} {0 94} {5 98} {6 90} {7 97}]
{id:3 age:36}
pop after: &[{1 51} {4 63} {6 90} {9 88} {0 94} {5 98} {7 97}]
{id:1 age:51}
pop after: &[{4 63} {9 88} {6 90} {7 97} {0 94} {5 98}]
{id:4 age:63}
pop after: &[{9 88} {0 94} {6 90} {7 97} {5 98}]
{id:9 age:88}
pop after: &[{6 90} {0 94} {5 98} {7 97}]
{id:6 age:90}
pop after: &[{0 94} {7 97} {5 98}]
{id:0 age:94}
pop after: &[{7 97} {5 98}]
{id:7 age:97}
pop after: &[{5 98}]
{id:5 age:98}
pop after: &[]

弹出的数据是首位最小的数字，这个顺序通过Less方法定义。

heap本身提供的方法

1
2
3
4
5
func Fix(h Interface, i int) {} // 第i个值改动之后，修正堆平衡
func Init(h Interface) {}            // 初始化类型
func Pop(h Interface) any {}    // 从顶取出数据
func Push(h Interface, x any) {}    // 压入数据
func Remove(h Interface, i int) any {}     // 从指定位置删除数据，并且返回删除的数据

核心源码：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
func Init(h Interface) {
    // heapify
    n := h.Len()
    for i := n/2 - 1; i >= 0; i-- {  // 便利所有的节点，满足根节点在树中最大或者最小。
        down(h, i, n)
    }
}

// 向上保证，满足h.Less的判断
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
    }
}

// 向下保证，满足h.Less的判断
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
}

初始化、压入、弹出、删除的过程都会通过向上、向下判断，修正树结构。

在优先级队列中的使用方式，与上面的例子类似，区别是优先级可能会被修改，就会使用到Fix。

List

链表，而且是一种双向链表得数据结构

结构体如下

1
2
3
4
5
6
7
8
9
10
11
12
// 链表中的元素
type Element struct {
    next, prev *Element  	// 下一个、上一个节点
    list *List        		// 数组
    Value any							// 值
}

// 链表结构体
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插入到前或者后。

元素的方法

1
2
(e *Element) Next() *Element     // 获取下一个元素
(e *Element) Prev() *Element    // 获取上一个元素

链表的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(l *List) Init()                         // 初始化链表，用New方法创建会使用到
(l *List) Len() int                    // 获取链表长度
(l *List) Front() *Element    // 获取链表最前面的一个的元素
(l *List) Back() *Element        // 获取链表最后一个元素
(l *List) Remove(e *Element) any    // 删除一个元素
(l *List) PushFront(v any) *Element    // 从头部插入数据
(l *List) PushBack(v any) *Element    // 从尾部插入数据
(l *List) InsertBefore(v any, mark *Element) *Element    // 在某个元素前面插入数据
(l *List) InsertAfter(v any, mark *Element) *Element     // 在某个元素后面插入数据
(l *List) MoveToFront(e *Element)    // 将某个元素移动到头部
(l *List) MoveToBack(e *Element)    // 将某个元素移动到尾部
(l *List) MoveBefore(e, mark *Element)    // 将某个元素移动到另一个元素的前面
(l *List) MoveAfter(e, mark *Element)        // 将某个元素移动到另一个元素的后面
(l *List) PushBackList(other *List)            // 将另外的链表拷贝，放到本链表后面
(l *List) PushFrontList(other *List)        // 将另外的链表拷贝，放到本链表前面

用法

1
2
3
4
5
6
7
8
9
10
11
12
l := list.New()
rand.Seed(time.Now().UnixNano())
for i := 0; i < 10; i++ {
    s := student{
        id:  i,
        age: rand.Intn(100),
    }
    l.PushFront(s) // 压入数据
}
for e := l.Front(); e.Next() != nil; e = l.Front() {
    fmt.Println(l.Remove(e))
}

Ring

环形链表，也是一个双向的。

数据结构

1
2
3
4
type Ring struct {
    next, prev *Ring		// 前后节点
    Value      any // for use by client; untouched by this library
}

方法

1
2
3
4
5
6
7
(r *Ring) Next() *Ring // 返回下一个节点
(r *Ring) Prev() *Ring // 返回上一个节点
(r *Ring) Move(n int) *Ring // 将指针移动到第几个节点（取模，小于0往前取，大于0往后取）
(r *Ring) Link(s *Ring) *Ring // 将一个环插入到另一个环
(r *Ring) Unlink(n int) *Ring    // 与长度取模，从下一个开始到第n个位置的节点去掉
(r *Ring) Len() int        // 获取环长度
(r *Ring) Do(f func(any))    // 环中所有节点调用f方法
1
2
3
4
5
6
7
8
9
10
11
12
r := ring.New(5)
for i := 0; i < 5; i++ {
    r.Value = i
    r = r.Next()
}
for i := 0; i < 7; i++ {
    fmt.Println(r.Value)
    r = r.Next()
}
r.Do(func(a any) {
    fmt.Printf("do : %v\n", a)
})

约瑟夫问题：在一个环中，从1开始计数，计算到某个数时，标识这个数

隔4个标记为删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
r := ring.New(10)
for i := 0; i < 10; i++ {
    r.Value = i
    r = r.Next()
}
for {
    for i := 0; i < 4; i++ {
        r = r.Next()
    }
    if r.Value == -1 {
        break
    }
    r.Value = -1
}

r.Do(func(a any) {
    fmt.Printf("%v\n", a)
})

或者，在环中删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
r := ring.New(10)
for i := 0; i < 10; i++ {
    r.Value = i
    r = r.Next()
}
for {
    for i := 0; i < 3; i++ {
        r = r.Next()
    }
    if r.Len() == 1 {
        break
    }
    r.Unlink(1)
}

r.Do(func(a any) {
    fmt.Printf("%v\n", a)
})

最终留下 5