Go 切片的使用和内部实现

本文是翻译自 Go 官方的博客 Go Slices: usage and internals

介绍

Go 的切片类型提供了一种方便高效的方法来处理类型化数据序列。切片类似于其他语言中的数组，但具有一些不寻常的属性。本文将介绍什么是切片以及它们的使用方式

数组

切片类型是建立在 Go 的数组类型之上的抽象类型，因此要理解切片，我们必须首先了解数组。

数组类型定义指定长度和元素类型。例如，该类型 [4]int 表示一个由四个整数组成的数组。数组的大小是固定的; 它的长度是其类型的一部分（ [4]int 和 [5]int 是两个不同的、不兼容的类型）。数组可以按通常的方式进行索引，因此表达式 s[n] 从零开始访问第 n 个元素。

var a [4]int
a[0] = 1
i := a[0]
// i == 1

数组不需要显式初始化; 数组的零值是一个现成的, 可以直接使用的数组，其中元素的值为元素类型本身的零值

// a[2] == 0, int 类型的零值

[4]int 在内存中的表现形式为, 按照顺序排列的四个 int 值

Go 语言中的数组是值类型。这意味着数组变量本身代表整个数组，而不是指向数组第一个元素的指针 (就像 C 语言中的数组一样)。因此，当你赋值或传递数组的值时，会复制它的所有内容。(如果你想避免复制，可以传递数组的指针，但这样一来你传递的不是数组本身，而是指向数组的指针。) 我们也可以将数组理解为一种特殊的结构体，只不过它的成员不是通过名称访问，而是通过索引访问。它本质上是一个固定大小的复合值。

数组字面量可以使用以下方式指定：

b := [2]string{"Penn", "Teller"}

或者, 你可以让编译器为你计算数组元素的数量:

b := [...]string{"Penn", "Teller"}

在上面两个例子中, b 的类型都是 [2]string

Go 语言中的数组是值类型。这意味着数组变量本身代表整个数组，而不是指向数组第一个元素的指针 (就像 C 语言中的数组一样)。因此，当你赋值或传递数组的值时，会复制它的所有内容。(如果你想避免复制，可以传递数组的指针，但这样一来你传递的不是数组本身，而是指向数组的指针。) 我们也可以将数组理解为一种特殊的结构体，只不过它的成员不是通过名称访问，而是通过索引访问。它本质上是一个固定大小的复合值。

数组字面量可以使用以下方式指定：

b := [2]string{"Penn", "Teller"}

或者, 你可以让编译器为你计算数组元素的数量:

b := [...]string{"Penn", "Teller"}

在上面两个例子中, b 的类型都是 [2]string

切片

数组在 Go 语言中占有一席之地，但它们有点缺乏灵活性，因此在 Go 代码中并不常见。而切片则无处不在，它们以数组为基础，提供了强大的功能和便利性。

切片的类型指定为 []T，其中 T 表示切片元素的类型。与数组类型不同，切片类型没有指定长度。

声明切片字面量的方式与声明数组字面量的方式类似，只是省略了元素个数的指定

letters := []string{"a", "b", "c", "d"}

切片可以通过调用内置的 make 函数来创建, 函数签名是

func make([]T, len, cap) []T

T 表示被创建切片的元素类型.

函数 make 接受类型、长度和可选容量。调用时，make 会分配一个数组并返回指向该数组的切片

var s []byte
s = make([]byte, 5, 5)
// s == []byte{0, 0, 0, 0, 0}

如果省略 capacity 参数，则默认为指定的长度。下面是相同代码的更简洁版本

s := make([]byte, 5)

可以使用内置的 len 和 cap 函数检查切片的长度和容量

len(s) == 5
cap(s) == 5

接下来两节, 我们将讨论长度和容量之间的关系。

空切片的零值为 nil。len 和 cap 函数对空切片都将返回 0。

还可以通过“切片”现有切片或数组来形成切片。切片通过指定一个由冒号分隔的两个索引的左闭右开区间来完成。例如，表达式 b[1:4] 创建了一个包含 b 中 1 到 3 的元素的切片（结果切片的索引将是 0 到 2）

b := []byte{'g', 'o', 'l', 'a', 'n', 'g'}
// b[1:4] == []byte{'o', 'l', 'a'}, 和 b 共享低层存储

这也是在给定数组的情况下创建切片的语法:

x := [3]string{"Лайка", "Белка", "Стрелка"}
s := x[:] // 一个指向 x 的存储空间的切片

切片内部

切片是数组段的描述符. 它由指向数组的指针, 段的长度和容量(段的最大长度) 组成.

!https://go.dev/blog/slices-intro/slice-struct.png

我们通过 make([]byte, 5) 创建的变量 s, 它的结构像下面这样:

!https://go.dev/blog/slices-intro/slice-1.png

长度是切片引用的元素数。容量是基础数组中的元素数（从切片指针引用的元素开始）。长度和容量之间的区别将在我们接下来的几个示例中明确。

当我们对 s 做切片操作时, 观察切片数据结构的变化以及和低层数组的关系

s = s[2:4]

切片操作不会拷贝原有切片的数据. 它会创建一个指向原始数组的新切片值。这使得切片操作与操作数组索引一样高效。因此，修改重新切片的元素（而不是切片本身）会修改原始切片的元素：

d := []byte{'r', 'o', 'a', 'd'}
e := d[2:]
// e == []byte{'a', 'd'}
e[1] = 'm'
// e == []byte{'a', 'm'}
// d == []byte{'r', 'o', 'a', 'm'}

早些时候， s 我们切成比其容量短的长度。我们可以通过再次切片来增加它的容量：

s = s[:cap(s)]

切片无法超出其容量进行扩容。尝试这样做会引发运行时错误，就像访问超出切片或数组边界时的错误一样。 类似地，切片也不能向下重新切片到负索引来访问数组中更早的元素。

切片扩容

为了增加切片的容量，需要创建一个新的更大容量的切片，然后将原始切片的内容复制到新切片中。这种技术与其他语言中动态数组的实现方式类似。以下示例通过创建一个新切片 t，将 s 的内容复制到 t 中，然后将切片值 t 赋值给 s，从而将 s 的容量翻倍：

t := make([]byte, len(s), (cap(s)+1)*2) // +1 in case cap(s) == 0
for i := range s {
        t[i] = s[i]
}
s = t

这个常见操作的循环部分通过内置的 copy 函数变得更加容易。顾名思义，copy 将数据从源切片复制到目标切片。它返回复制的元素数量

func copy(dst, src []T) int

copy 函数支持不同长度切片之间的复制（仅复制较少元素的数量）。此外，copy 可以处理共享相同底层数组的源和目标切片，并正确处理重叠切片。

使用 copy，我们可以简化上面的代码片段

t := make([]byte, len(s), (cap(s)+1)*2)
copy(t, s)
s = t

一种常见操作是向切片末尾追加数据。该函数将字节元素追加到字节切片，并在必要时扩容切片，并返回更新后的切片值。

func AppendByte(slice []byte, data ...byte) []byte {
    m := len(slice)
    n := m + len(data)
    if n > cap(slice) { // if necessary, reallocate
        // allocate double what's needed, for future growth.
        newSlice := make([]byte, (n+1)*2)
        copy(newSlice, slice)
        slice = newSlice
    }
    slice = slice[0:n]
    copy(slice[m:n], data)
    return slice
}

我们可以像下面这样使用 AppendByte

p := []byte{2, 3, 5}
p = AppendByte(p, 7, 11, 13)
// p == []byte{2, 3, 5, 7, 11, 13}

像 AppendByte 这样的函数之所以有用，是因为它们可以完全控制切片增长的方式。根据程序的特性，可能需要以更小或更大的块分配空间，或者对重新分配的大小设置上限。

但是大多数程序不需要完全控制，因此 Go 提供了内置的 append 函数，适用于大多数情况；它的签名为：

func append(s []T, x ...T) []T

append 函数将元素 x 追加到切片 s 的末尾，并在必要时对切片扩容

a := make([]int, 1)
// a == []int{0}
a = append(a, 1, 2, 3)
// a == []int{0, 1, 2, 3}

要将一个切片追加到另一个切片，请使用 … 将第二个参数展开为参数列表。

a := []string{"John", "Paul"}
b := []string{"George", "Ringo", "Pete"}
a = append(a, b...) // equivalent to "append(a, b[0], b[1], b[2])"
// a == []string{"John", "Paul", "George", "Ringo", "Pete"}

由于切片的零值 (nil) 的行为类似于零长度的切片，因此你可以先声明一个切片变量，然后在循环中追加元素

// Filter returns a new slice holding only
// the elements of s that satisfy fn()
func Filter(s []int, fn func(int) bool) []int {
    var p []int // == nil
    for _, v := range s {
        if fn(v) {
            p = append(p, v)
        }
    }
    return p
}

一个潜在的“陷阱”

正如之前提到的，重新切片不会复制底层数组。整个数组将一直保存在内存中，直到不再被引用。有时这会导致程序在只需要一小部分数据时，却将所有数据保存在内存中。

例如，这个 FindDigits 函数将一个文件加载到内存中，并搜索其中第一组连续的数字字符，然后将它们作为新的切片返回。

var digitRegexp = regexp.MustCompile("[0-9]+")

func FindDigits(filename string) []byte {
    b, _ := ioutil.ReadFile(filename)
    return digitRegexp.Find(b)
}

这段代码确实按照预期工作，但返回的 []byte 指向包含整个文件的数组。由于切片引用原始数组，只要切片存在，垃圾回收器就无法释放数组；文件中少量有用的字节会将整个内容保留在内存中。

为了解决这个问题，可以在返回数据之前将其复制到一个新的切片中：

func CopyDigits(filename string) []byte {
    b, _ := ioutil.ReadFile(filename)
    b = digitRegexp.Find(b)
    c := make([]byte, len(b))
    copy(c, b)
    return c
}

通过使用 append 可以构建一个更简洁的版本。这部分可以留给读者作为练习。