container包中的那些容器

Golang
Golang
发布日期:   2024-09-20
更新日期:   2024-09-20
文章字数:   4.7k
阅读时长:   17 分
阅读次数:  

我们在上次讨论了数组和切片，当我们提到数组的时候，往往会想起链表。Go 语言的链表实现在标准库的container/list代码包中。

这个代码包中有两个公开的程序实体——List和Element，List 实现了一个双向链表（以下简称链表），而 Element 则代表了链表中元素的结构，类似于节点。

那么，我今天的问题是：可以把自己生成的Element类型值传给链表吗？

我们在这里用到了List的四种方法。

  • MoveBefore方法和MoveAfter方法，它们分别用于把给定的元素移动到另一个元素的前面和后面。
  • MoveToFront方法和MoveToBack方法，分别用于把给定的元素移动到链表的最前端和最后端。

在这些方法中，“给定的元素”都是*Element类型的，*Element类型是Element类型的指针类型，*Element的值就是元素的指针。

1
2
3
4
5
func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveAfter(e, mark *Element)

func (l *List) MoveToFront(e *Element)
func (l *List) MoveToBack(e *Element)

具体问题是，如果我们自己生成这样的值，然后把它作为“给定的元素”传给链表的方法，那么会发生什么？链表会接受它吗？

这里，给出一个典型回答：不会接受，这些方法将不会对链表做出任何改动。因为我们自己生成的Element值并不在链表中，所以也就谈不上“在链表中移动元素”。更何况链表不允许我们把自己生成的Element值插入其中。

举例如下：

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
package main

import (
    "container/list"
    "fmt"
)

func main() {
    // 创建一个新的链表
    l := list.New()

    // 向链表添加元素
    e1 := l.PushBack(1)

    // 输出当前链表的元素
    fmt.Println("Current List:")
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }

    // 自己创建一个 Element
    customElement := &list.Element{Value: 10}

    // 尝试将自定义的 Element 移动到链表中
    // 这里将报错或者不产生任何效果
    // 因为 customElement 不在链表中
    l.MoveBefore(customElement, e1) // 这行代码不会有任何效果

    // 再次输出链表的元素
    fmt.Println("After trying to move custom Element:")
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }

    // 结果显示链表内容没有改变
}

输出结果：

image-20240920140909089

问题解析

在List包含的方法中，用于插入新元素的那些方法都只接受interface{}类型的值。这些方法在内部会使用Element值，包装接收到的新元素。

这样做正是为了避免直接使用我们自己生成的元素，主要原因是避免链表的内部关联，遭到外界破坏，这对于链表本身以及我们这些使用者来说都是有益的。

List的方法还有下面这几种：

Front和Back方法分别用于获取链表中最前端和最后端的元素， InsertBefore和InsertAfter方法分别用于在指定的元素之前和之后插入新元素，PushFront和PushBack方法则分别用于在链表的最前端和最后端插入新元素。

1
2
3
4
5
6
7
8
func (l *List) Front() *Element
func (l *List) Back() *Element

func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) InsertAfter(v interface{}, mark *Element) *Element

func (l *List) PushFront(v interface{}) *Element
func (l *List) PushBack(v interface{}) *Element

这些方法都会把一个Element值的指针作为结果返回，它们就是链表留给我们的安全“接口”。拿到这些内部元素的指针，我们就可以去调用前面提到的用于移动元素的方法了。

知识扩展

1. 问题：为什么链表可以做到开箱即用？

List和Element都是结构体类型。结构体类型有一个特点，那就是它们的零值都会是拥有特定结构，但是没有任何定制化内容的值，相当于一个空壳。值中的字段也都会被分别赋予各自类型的零值。

广义来讲，所谓的零值就是只做了声明，但还未做初始化的变量被给予的缺省值。每个类型的零值都会依据该类型的特性而被设定。

比如，经过语句var a [2]int声明的变量a的值，将会是一个包含了两个0的整数数组。又比如，经过语句var s []int声明的变量s的值将会是一个[]int类型的、值为nil的切片。

在 Go 中，当你声明一个链表时，实际上只创建了一个空的链表结构，但链表的内部状态（如头指针、尾指针等）并没有被初始化。

那么经过语句var l list.List声明的变量l的值将会是什么呢？这个零值将会是一个长度为0的链表。这个链表持有的根元素也将会是一个空壳，其中只会包含缺省的内容。那这样的链表我们可以直接拿来使用吗？

答案是，可以的。这被称为“开箱即用”。Go 语言标准库中很多结构体类型的程序实体都做到了开箱即用。这也是在编写可供别人使用的代码包（或者说程序库）时，我们推荐遵循的最佳实践之一。那么，语句var l list.List声明的链表l可以直接使用，这是怎么做到的呢？

关键在于它的“延迟初始化”机制。

所谓的延迟初始化，你可以理解为把初始化操作延后，仅在实际需要的时候才进行。延迟初始化的优点在于“延后”，它可以分散初始化操作带来的计算量和存储空间消耗。

例如，如果我们需要集中声明非常多的大容量切片的话，那么那时的 CPU 和内存空间的使用量肯定都会一个激增，并且只有设法让其中的切片及其底层数组被回收，内存使用量才会有所降低。

如果数组是可以被延迟初始化的，那么计算量和存储空间的压力就可以被分散到实际使用它们的时候。这些数组被实际使用的时间越分散，延迟初始化带来的优势就会越明显。

实际上，Go 语言的切片就起到了延迟初始化其底层数组的作用，你可以想一想为什么会这么说的理由。

延迟初始化的缺点恰恰也在于“延后”。你可以想象一下，如果我在调用链表的每个方法的时候，它们都需要先去判断链表是否已经被初始化，那这也会是一个计算量上的浪费。在这些方法被非常频繁地调用的情况下，这种浪费的影响就开始显现了，程序的性能将会降低。

在这里的链表实现中，一些方法是无需对是否初始化做判断的。比如Front方法和Back方法，一旦发现链表的长度为0, 直接返回nil就好了。

又比如，在用于删除元素、移动元素，以及一些用于插入元素的方法中，只要判断一下传入的元素中指向所属链表的指针，是否与当前链表的指针相等就可以了。

如果不相等，就一定说明传入的元素不是这个链表中的，后续的操作就不用做了。反之，就一定说明这个链表已经被初始化了。

原因在于，链表的PushFront方法、PushBack方法、PushBackList方法以及PushFrontList方法总会先判断链表的状态，并在必要时进行初始化，这就是延迟初始化。

而且，我们在向一个空的链表中添加新元素的时候，肯定会调用这四个方法中的一个，这时新元素中指向所属链表的指针，一定会被设定为当前链表的指针。所以，指针相等是链表已经初始化的充分必要条件。

明白了吗？List利用了自身以及Element在结构上的特点，巧妙地平衡了延迟初始化的优缺点，使得链表可以开箱即用，并且在性能上可以达到最优。

在 Go 的链表实现中，特别是 list.List 类型，链表的方法如 PushFront、PushBack 等会在添加元素时自动进行初始化。这些方法的设计思路如下：

  1. 状态检查：
    • 每当调用这些方法时，首先会检查链表的状态（是否为空）。如果链表为空（即未初始化），这些方法会自动进行初始化。
    • 例如，PushBack 会检查链表的 Head 是否为 nil，如果是，就会初始化链表。（简单的说，就是声明的时候并没有初始化变量，而是等到实际使用的时候才会初始化他，这个分配空间的思路和C++的vector很类似，都是由STL负责申请内存空间，然后释放空间，这个延迟初始化和Java的Stream流很类似）
  2. 指向链表的指针：
    • 当元素被添加到链表中时，新的 Element 中的指针会指向当前链表。这确保了每个元素都知道它所属的链表。
    • 例如，调用 PushBack 时，新的元素会设置其 List 字段为当前链表的指针。

这里举一个例子说明一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import (
    "container/list"
    "fmt"
)

func main() {
    // 声明一个空链表
    var l list.List
    
 	// 尝试访问链表的前端和后端元素
    fmt.Println("Front:", l.Front()) // 输出: Front: <nil>
    fmt.Println("Back:", l.Back())   // 输出: Back: <nil>
    
    // 尝试添加元素，触发延迟初始化
    l.PushBack(1) // 这里链表会被初始化
    l.PushBack(2)

    // 输出链表的元素
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value) // 输出: 1 2
    }
}

运行结果如下图所示：

image-20240920142713385

如果还是有点想不没明白的话，如果你学过Java，那么应该见过很多次的空指针异常吧，其实就是null.方法了，你看上面的，明明是null，但是却可以正常调用方法应该就明白了吧。这才是延迟初始化的实际含义。

问题 2：Ring与List的区别在哪儿？

container/ring包中的Ring类型实现的是一个循环链表，也就是我们俗称的环。其实List在内部就是一个循环链表。它的根元素（即链表的头）永远不会持有任何实际的元素值，而该元素的存在就是为了连接这个循环链表的首尾两端。（这里的根元素有点类似虚拟头节点）

所以也可以说，**List的零值是一个只包含了根元素，但不包含任何实际元素值的空链表**。那么，既然Ring和List在本质上都是循环链表，那它们到底有什么不同呢？

最主要的不同有下面几种。

  1. Ring类型的数据结构仅由它自身即可代表，而List类型则需要由它以及Element类型联合表示。这是表示方式上的不同，也是结构复杂度上的不同。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    type Ring struct {
        // 反正是环，一直往前冲就行了，直接Next，不用管Prev什么的
        Value interface{} // 节点存储的值
        Next  *Ring       // 指向下一个节点
    }

    type Element struct {
        Value interface{}
        Next  *Element
        Prev  *Element
    }

    type List struct {
        Head *Element
        Tail *Element
        Len  int
    }

  2. 一个Ring类型的值严格来讲，只代表了其所属的循环链表中的一个元素，而一个List类型的值则代表了一个完整的链表。这是表示维度上的不同。

  3. 在创建并初始化一个Ring值的时候，我们可以指定它包含的元素的数量，但是对于一个List值来说却不能这样做（也没有必要这样做）。循环链表一旦被创建，其长度是不可变的。这是两个代码包中的New函数在功能上的不同，也是两个类型在初始化值方面的第一个不同。

  4. 仅通过var r ring.Ring语句声明的r将会是一个长度为1的循环链表，而List类型的零值则是一个长度为0的链表。别忘了List中的根元素不会持有实际元素值，因此计算长度时不会包含它。这是两个类型在初始化值方面的第二个不同。

  5. Ring值的Len方法的算法复杂度是 O(N) 的，而List值的Len方法的算法复杂度则是 O(1) 的。这是两者在性能方面最显而易见的差别。

其他的不同基本上都是方法方面的了。比如，循环链表也有用于插入、移动或删除元素的方法，不过用起来都显得更抽象一些，等等。

总结

我们今天主要讨论了container/list包中的链表实现。我们详细讲解了链表的一些主要的使用技巧和实现特点。由于此链表实现在内部就是一个循环链表，所以我们还把它与container/ring包中的循环链表实现做了一番比较，包括结构、初始化以及性能方面。

思考题

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

在这里，我们先不求对它们的实现了如指掌，能用对、用好才是我们进阶之前的第一步。好了，感谢你的收听，我们下次再见。

补充说明：List这个结构体类型有两个字段，一个是Element类型的字段root，另一个是int类型的字段len。顾名思义，前者代表的就是那个根元素，而后者用于存储链表的长度。注意，它们都是包级私有的，也就是说使用者无法查看和修改它们。

像前面那样声明的l，其字段root和len都会被赋予相应的零值。len的零值是0，正好可以表明该链表还未包含任何元素。由于root是Element类型的，**所以它的零值就是该类型的空壳，用字面量表示的话就是Element{}**。

Element类型包含了几个包级私有的字段，分别用于存储前一个元素、后一个元素以及所属链表的指针值。另外还有一个名叫Value的公开的字段，该字段的作用就是持有元素的实际值，它是interface{}类型的。在Element类型的零值中，这些字段的值都会是nil。

这里解释一下所属链表的指针值是什么意思：

所属链表的指针 (List):

  • 这个字段指向包含当前 Element 的链表。它是一个指向 List 类型的指针，表示该元素属于哪个链表。（这里的设计有点类似Redis的raw编码指向SDS的操作）img

参考阅读

切片与数组的比较

切片本身有着占用内存少和创建便捷等特点，但它的本质上还是数组。切片的一大好处是可以让我们通过窗口快速地定位并获取，或者修改底层数组中的元素。

不过，当我们想删除切片中的元素的时候就没那么简单了。元素复制一般是免不了的，就算只删除一个元素，有时也会造成大量元素的移动。这时还要注意空出的元素槽位的“清空”，否则很可能会造成内存泄漏。

另一方面，在切片被频繁“扩容”的情况下，新的底层数组会不断产生，这时内存分配的量以及元素复制的次数可能就很可观了，这肯定会对程序的性能产生负面的影响。

尤其是当我们没有一个合理、有效的”缩容“策略的时候，旧的底层数组无法被回收，新的底层数组中也会有大量无用的元素槽位。过度的内存浪费不但会降低程序的性能，还可能会使内存溢出并导致程序崩溃。

这里写了一段代码便于理解：

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
package main

import (
    "fmt"
)

func main() {
    // 创建一个初始容量为 2 的切片
    s1 := make([]int, 0, 2)
    fmt.Printf("Initial slice: %v, capacity: %d\n", s1, cap(s1))

    // 添加元素，直到触发扩容
    s1 = append(s1, 1, 2)
    fmt.Printf("After adding elements: %v, capacity: %d\n", s1, cap(s1))

    // 继续添加元素，触发扩容
    s2 := append(s1, 3)
    fmt.Printf("After adding one more element: %v, capacity: %d\n", s2, cap(s2))

    // 观察底层数组的内存使用情况
    // 由于 s 已经扩容，原底层数组仍然在内存中，但未被引用
    // 这时，我们手动创建一个新切片以观察内存使用
    oldArraySlice := s1[:2] // 参考旧的底层数组的部分
    fmt.Printf("Old array slice: %v, capacity: %d\n", oldArraySlice, cap(oldArraySlice))

    // 这里 oldArraySlice 仍然引用了旧的底层数组
    // 但 s 现在指向新的底层数组
    // 旧数组未被回收，导致内存浪费
    fmt.Printf("Memory usage demonstration: oldArraySlice keeping reference to old array\n")
}

运行结果如下：

注意切片扩容之后新数组的地址是会变化的，不是一直都在原地扩容，其实叫Clone感觉才更加合理。叫扩容感觉有点误导人了。

image-20240920145613397

由此可见，正确地使用切片是多么的重要。不过，一个更重要的事实是，任何数据结构都不是银弹。不是吗？数组的自身特点和适用场景都非常鲜明，切片也是一样。它们都是 Go 语言原生的数据结构，使用起来也都很方便. 不过，你的集合类工具箱中不应该只有它们。这就是我们使用链表的原因。

不过，对比来看，一个链表所占用的内存空间，往往要比包含相同元素的数组所占内存大得多。这是由于链表的元素并不是连续存储的，所以相邻的元素之间需要互相保存对方的指针。不但如此，每个元素还要存有它所属链表的指针。

有了这些关联，链表的结构反倒更简单了。它只持有头部元素（或称为根元素）基本上就可以了。当然了，为了防止不必要的遍历和计算，链表的长度记录在内也是必须的。

参考文章：08 | container包中的那些容器 | Go语言核心36讲 (gitbook.io)

文章作者: zoloy
文章链接: http://example.com/2024/09/20/Golang08/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 zoloy !
Golang
赏
评论
  目录