go中的slice:用法和原理

原文为https://blog.golang.org/go-slices-usage-and-internals

一篇不错的博客文章,所以翻译下。
slice中文可以翻译成分片,不过这种词我觉得还是用英文单词好。

介绍

go的slice类型提供一种方便有效的方法来处理类型数据序列。slice和其他语言里的数组类似,但是有一些不同的属性。这篇文章将会带你领略什么是slice以及如何使用。

数组

slice是一个基于go的数组类型的抽象,所以想要理解slice就得先理解数组。
一个数组类型定义指定了长度和元素类型。比如,[4]int 类型相当于一个包含4个整数的数组。一个数组的大小是固定的;它的长度是它类型的一部分([4]int 和[5]int 是不同不兼容的类型)。数组可以用通常的方法索引访问,所以表达式s[n]可以访问第n个元素,从下标0开始。

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

数组不需要显示初始化;数组的零值是一个随时能用的本身就为零值的数组:

1
// a[2] == 0, the zero value of the int type

[4]int 在内存上的表现形式就是4个整数值顺序排列

go的数组就是值。一个数组变量表示整个数组;它不是指向数组第一个元素的指针(比如c语言)。意思是当你分配或者传递一个数组值时你将是复制它的内容。(为了避免这种情况,你可以传递数组的指针,但那就是一个数组的指针而不是数组了)。对数组的认知可以是一种结构,使用索引而不是命名字段:一个固定大小的复合值。
一个数组字面量可以被这样指定:

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

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

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

上面两种,b的类型都是[2]string

slices

数组有他们自己的用处,但是有点不灵活,所以在go的代码里不常见。slice比较常见,基于数组提供更强大和方便的功能。
一个slice的类型规范是[]T,T是slice元素的类型。和数组不同,slice没有指定长度。
slice的定义和数组一样,除了忽略元素数量。

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

slice可以被内置函数make创建,make有签名,

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

T代表slice的元素类型。make函数需要一个类型、长度和可选的容量参数。当调用时,make分配一个数组,返回关联这个数组的slice.

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

当没有提供容量参数时,默认是指定的长度。下面是一个更简明的代码:

1
s := make([]byte, 5)

长度和容量可以用内置函数len和cap来检查。

1
2
len(s) == 5
cap(s) == 5

接下来的两部分将会讨论长度和容量之间的关系。
slice的零值为nil。对于一个nil slice,len和cap函数都返回0。
slice也可以对一个已经存在的slice或者数组切片来形成,用两个冒号分割的索引指定一个半开区间来完成分片。例如,表达式b[1:4]创建了一个包含元素1到3的slice(slice的结果索引将是0到2)

1
2
b := []byte{'g', 'o', 'l', 'a', 'n', 'g'}
// b[1:4] == []byte{'o', 'l', 'a'}, sharing the same storage as b

一个slice表达式的开始和结束索引是可选的:默认是0和slice的长度:

1
2
3
// b[:2] == []byte{'g', 'o'}
// b[2:] == []byte{'l', 'a', 'n', 'g'}
// b[:] == b

下面的也是给定一个数组创建一个slice的语法:

1
2
x := [3]string{"Лайка", "Белка", "Стрелка"}
s := x[:] // a slice referencing the storage of x

slice原理

slice是一个数组段的描述。它由数组指针,数组段长度和容量(数组段的最大长度)组成。

早先由make([]byte, 5)创建的变量s,结构如下:

长度是slice引用的元素数量。容量是底层数组的元素数量(开始于silce指针引用的元素,注意这个并不一定是最初的数组容量)。长度和容量的区别通过下面几个例子将会更清晰。
如果我们分片s,可以注意到slice中的数据结构和底层数组的关系:

1
s = s[2:4]

分片并没有复制slice的数据。它创建了一个新的slice值指向原来的数组。这使得slice操作和操作数组索引一样方便。因此,修改新分片的slice元素就是修改了原slice的元素:

1
2
3
4
5
6
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的长度比容量小。我们也可以增大它直到达到它的容量:

1
s = s[:cap(s)]

一个slice不能增长超过它的容量。企图这样做将会引发运行错误,和索引超过slice或者数组边界一样。类似的,slice不能用小于0再次分片来访问数组之前的元素。

slice增长(copy和append函数)

为了增加slice的容量,必须创建一个新的更大一点的slice,然后复制原来的slice内容进去。这是其他语言的动态数组实现的幕后技术。下面的例子就是把s的容量增大了两倍,通过新建一个slice t,复制s的内容进t,然后分配slice值t给s:

1
2
3
4
5
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实现。同样的建议,从源slice复制内容到目的slice。返回复制的元素数量。

1
func copy(dst, src []T) int

copy函数支持在不同长度slice指尖复制(它只会复制到较少数量的元素)。另外,copy可以操作源和目的slice共享相同的底层数组,正确的处理覆盖slice。
使用copy,我们可以用简短的代码实现上面的操作:

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

一个常见操作是增加数据到一个slice的末尾,下面这个函数给一个字节slice增加字节元素,如果需要的话增大slice,返回更新之后的slice值:

1
2
3
4
5
6
7
8
9
10
11
12
13
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的一个场景如下:

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

AppendByte方法很有用,因为它可以完全控制slice的增长方式。根据程序的特性,可能需要分配更小或更大的块,或者给重新分配的大小设置一个上限。(这个可以看看redis的sds预分配空间的做法)

但是大多数程序不需要完全控制,所以go提供了一个内置函数append适用于大部分场景;它的签名:

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

这个append函数把元素x加到s的末尾,如果需要更大容量就增长slice。

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

如果要添加一个slice到另一个slice,用…作为第二个参数。

1
2
3
4
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"}

因为一个slice的零值(nil)就像一个0长度的slice,你可以定义一个slice并且在循环里添加进去:

1
2
3
4
5
6
7
8
9
10
11
// 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
}

一个可能的坑

之前提到的,重新切片一个slice,不会复制原来的底层数组。整个数组会保持在内存中直到不再被引用。偶尔这会导致程序在内存中保持所有的数据,但是只有一小片是需要的(其实就是浪费内存)

例如,下面的FindDigits函数把一个文件加载进内存,然后搜寻第一组连续数字,然后返回一些新slice。

1
2
3
4
5
6
var digitRegexp = regexp.MustCompile("[0-9]+")

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

这段代码表现和广告一样(这什么意思。。。),但是返回的[]bytes指向一个包含全部文件的数组。因为这个slice关联原来的数组,只要slice一直保持,gc就不能释放这个数组;少量有用的文件字节在内存里保持着整个内容。
为了解决这个问题,在返回时可以复制数据到一个新的slice:

1
2
3
4
5
6
7
func CopyDigits(filename string) []byte {
b, _ := ioutil.ReadFile(filename)
b = digitRegexp.Find(b)
c := make([]byte, len(b))
copy(c, b)
return c
}

这个函数更简洁的版本是使用append,这给读者留下来做练习。