Slice是长度可变的元素序列(数组不可变),每个元素都有相同的类型。slice类型写作[]T,其中T代表slice中的元素类型;slice和数组写法很像,只是没有指定长度。
数组和slice之间的联系非常紧密。slice是非常轻量的数据结构,它是引用类型,指向底层的一个数组,该数组被称之为slice的底层数组,slice可以访问底层数组的某个子序列,也可以访问整个数组。一个slice由三个部分组成:指针、长度、容量,指针指向了slice中第一个元素对应的底层数组元素的地址,因为slice未必是从数组第一个元素开始,因此slice中的第一个元素未必是数组中的第一个元素。长度对应slice中的元素数目,长度是不能超过容量的;容量一般是从slice中第一个元素对应底层数组中的开始位置,到底层数组的结尾的长度。内置函数len和cap分别返回一个slice的长度和容量。
多个slice可以共享底层的数组,甚至它们引用的底层数组部分可以重叠。图4.1表示了一个数组,它的元素是每个月份的字符串名,还有两个slice,它们重叠引用了底层数组。数组定义:
months := [...]string{1: "January", /* ... */, 12: "December"}
这里一月份是months[1],十二月是months[12]。通常来说,数组第一元素索引从0开始,但是月份一般是从1月开始到12月,因此在声明数组时,我们跳过了第0个元素,这里,第0个元素会被默认初始化为""(空字符串)。
下面介绍切片操作s[i:j],这里0 ≤ i≤ j≤ cap(s),该操作会创建一个新的slice,引用s中从第i个元素到第j-1个元素的字序列,新的slice有j-i个元素。如果省略下标i:s[:j],实际上代表s[0:j];如果省略下标j:s[i:],代表s[0:len(s)]。因此months[1:13]操作将引用全部月份,和months[1:]操作等价。months[:]则是引用整个数组。下面分别表示第二个季度和北方的夏天:
Q2 := months[4:7]
summer := months[6:9]
fmt.Println(Q2) // ["April" "May" "June"]
fmt.Println(summer) // ["June" "July" "August"]
两个slice有重叠部分:六月份,下面是一个包含相同月份的测试(性能不高):
for _, s := range summer {
for _, q := range Q2 {
if s == q {
fmt.Printf("%s appears in both\n", s)
}
}
}
如果slice操作的下标超过cap(s)将导致panic,如果超过len(s)则意味着扩展slice(不能超过cap(s)),因为新slice的长度会变大:
fmt.Println(summer[:20]) // panic: out of range
endlessSummer := summer[:5] // 在容量允许内扩展summer
fmt.Println(endlessSummer) // "[June July August September October]"
另外,字符串的slice操作和[]byte的slice操作是很相似的。它们都表现为x[m:n],并且都返回原始序列的子序列,底层数组也都是原始的序列,因此slice操作是常量级别的时间复杂度。若x[m:n]的目标是字符串,则生成一个子串;若目标是[]byte,则生成新的[]byte。
因为slice引用包含了指向底层数组的指针,因此向函数传递slice后,函数可以在内部对slice的底层数组进行更改。换而言之,复制slice就是为底层数组创建一个新的引用,代价是非常低的(其实就是复制一个含有三个字段的struct)。下面的reverse函数对[]int类型的slice进行就地反转(无内存分配),它可以用于任意长度的slice:
// reverse reverses a slice of ints in place.
func reverse(s []int) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
反转数组:
a := [...]int{0, 1, 2, 3, 4, 5}
reverse(a[:])
fmt.Println(a) // "[5 4 3 2 1 0]"
如果要将slice的前n个元素和后面所有的元素调换位置的话(以第n个元素为支点,向左旋转),其中一个办法是调用三次reverse函数,第一次是反转前n个元素,然后是反转剩下所有元素,最后是反转整个slice.(如果是向右旋转,则将第一个和第三个函数对调位置即可)。
s := []int{0, 1, 2, 3, 4, 5}
// Rotate s left by two positions.
reverse(s[:2])
reverse(s[2:])
reverse(s)
fmt.Println(s) // "[2 3 4 5 0 1]"
要注意上面slice和数组初始化语法的差异。虽然它们的语法很类似,都是用花括号包含的元素序列,但是slice是不需要指明长度的,因此这会隐式的创建一个合适的底层数组,然后slice内的指针会指向这个数组。初始化slice就和初始化数组一样,可以使用值序列或者使用索引-值列表(见3.1节)。
在3.1节中,我们提到了若数组的类型可以比较,那数组可以比较,但是slice之间是不能通过==操作符进行比较的!标准库中提供了高度优化的bytes.Equal函数,可以用来判断两个[]byte是否相等,但是对于其它类型的slice,我们必须实现自己的比较函数:
func equal(x, y []string) bool {
if len(x) != len(y) {
return false
}
for i := range x {
if x[i] != y[i] {
return false
}
}
return true
}
为什么Go语言不支持slice的比较运算呢?第一个原因,slice是引用类型,一个slice甚至可以引用自身。虽然有很多解决办法,但是没有一个是简单有效的。第二个原因,因为slice是间接引用,因此一个slice在不同时间可能包含不同的元素-底层数组的元素可能被修改;只要一个数据类型可以比较相等性,那么就可以用来做map的key,map这种数据结构对key的要求是:如果最开始key就相等,那在map的生命周期内,key要一直相等,因此key是不可以变的。而对于指针或chan这类引用类型,==可以判断两个指针是否引用了想同的对象,是有用的,但是slice的相等测试充满了不确定性,因此,安全的做法是禁止slice之间的比较操作。
唯一的例外是:slice可以和nil比较,例如,
if summer == nil { /* ... */ }
因为slice是引用类型,因此它的零值是nil。一个nil slice是没有底层数组的,它的长度和容量都是0,但是也有非nil的slice长度和容量也是0,例如[]int{}或make([]int, 3)[3:]。我们可以通过[]int(nil)这种类型转换来生成一个[]int类型的nil值。
var s []int // len(s) == 0, s == nil
s = nil // len(s) == 0, s == nil
s = []int(nil) // len(s) == 0, s == nil
s = []int{} // len(s) == 0, s != nil
因此,由上可知,如果要测试一个slice是否为空,要使用len(s) == 0。除了可以和nil做相等比较外,一个nil值的slice,它的行为和其它0长度的slice一样:例如,之前的函数reverse(nil)就是安全的。除非包文档特别说明,否则所有的Go函数都应该以相同的方式对待nil值slice和0长度slice(byte包中的部分函数会对nil值slice做特殊处理)。
内置函数make可以用于创建一个指定类型、长度、容量的slice。很多时候,容量参数可以省略,这种情况下,容量等于长度:
make([]T, len)
make([]T, len, cap) // same as make([]T, cap)[:len]
实际上,make会创建一个匿名的底层数组,然后返回一个slice值,只有通过该值才能引用匿名的底层数组。在上面第一条语句中,slice的范围和底层数组范围一致;在第二条语句中,slice引用了底层数组用前len个元素,但是slice的容量和底层数组的长度一致,因此slice可以在len不够用时,自动增长,只要长度不超过cap即可。
4.2.1. append函数
内置函数append用于向slice的尾端追加元素:
var runes []rune
for _, r := range "Hello, 世界" {
runes = append(runes, r)
}
fmt.Printf("%q\n", runes) // "['H' 'e' 'l' 'l' 'o' ',' ' ' '世' '界']"
上面的循环使用append构建了包含9个rune的slice(这个问题可以直接通过[]rune("Hello,世界")来解决)。
理解append对于理解slice的底层原理是非常有帮助的,下面是appendInt 1.0版本,用于处理[]int类型的slice:
func appendInt(x []int, y int) []int {
var z []int
zlen := len(x) + 1
if zlen <= cap(x) {
// There is room to grow. Extend the slice.
z = x[:zlen]
} else {
// There is insufficient space. Allocate a new array.
// Grow by doubling, for amortized linear complexity.
zcap := zlen
if zcap < 2*len(x) {
zcap = 2 * len(x)
}
z = make([]int, zlen, zcap)
copy(z, x) // a built-in function; see text
}
z[len(x)] = y
return z
}
每次调用appendInt,先检测slice的底层数组容量是否足够。如果足够,直接扩展slice(仍然在底层数组中),将y元素复制过去,这时x和z共享底层数组。
如果没有足够的容量,appendInt会重新分配一个足够大的数组,创建slice,然后将x全部复制过去,再在尾部添加y。这时,x和z引用的是不同的底层数组。
上面那种通过循环来一个一个复制元素虽然很直接很简单,但是内置函数copy更适合这种场景。copy可以将一个slice复制给另一个同类型的slice,copy第一个参数是目标slice,第二个参数是源slice,可以通过这种方式来记住参数顺序: dst = src,将src'赋给'dst。dst和src两个slice可以共享底层数组,甚至重叠。copy将返回复制的元素个数,这个值等于两个slice中较小的长度,所以不用担心越界问题。
为了减少内存分配次数、提升利用率,新分配的数组的长度要大于x + y的长度,有个简单的办法,每次扩展数组时将长度翻倍,这样减少了多次内存分配,也保证了添加元素是常数时间操作:
func main() {
var x, y []int
for i := 0; i < 10; i++ {
y = appendInt(x, i)
fmt.Printf("%d cap=%d\t%v\n", i, cap(y), y)
x = y
}
}
容量的每次变化都会导致内存分配和内存拷贝,因为需要创新新的底层数组,并拷贝元素过去:
0 cap=1 [0]
1 cap=2 [0 1]
2 cap=4 [0 1 2]
3 cap=4 [0 1 2 3]
4 cap=8 [0 1 2 3 4]
5 cap=8 [0 1 2 3 4 5]
6 cap=8 [0 1 2 3 4 5 6]
7 cap=8 [0 1 2 3 4 5 6 7]
8 cap=16 [0 1 2 3 4 5 6 7 8]
9 cap=16 [0 1 2 3 4 5 6 7 8 9]
先看一下i=3那一次循环,循环开始前x包含了[0 1 2]三个元素,容量是4,因此底层数组末尾还有一个位置可以将新元素拷贝进来,不需要内存分配,循环后,y的长度和容量都是4并且x和y引用相同的底层数组:
再来看i=4这次循环,循环开始前,x的底层数组没有新空间了,因此appendInt重新创建一个容量为8的底层数组,将x的所有元素都复制过去,然后在末尾添加新元素4。循环后,y的长度是5,容量是8,因此还有3个空闲位置,后面的三次循环都不需要重新分配底层数组。在i=4这次循环中,y和x引用了不同的底层数组:
内置函数append使用了比appendInt更复杂的扩展策略,因此我们无法知道append调用是否导致了新的内存分配,也不能确定新的slice和旧的slice是否引用相同的底层数组,同时我们也不能确定在旧的slice上操作是否会影响新的slice。因此我们一般这样使用append:
runes = append(runes, r)
将值直接赋给旧的slice。这种更新slice变量的写法在调用append时是必要的。在实际应用中,除了append,其它任何可能导致长度、容量或底层数组变化的操作,都需要更新旧的slice变量。slice是引用类型,虽然访问底层数组的元素是间接访问的,但是slice本身就是一个结构体,是一个值类型,里面包含了指针、长度、容量字段,因此要更新slice就要像上面那样有显式的赋值操作。从这个角度来说,slice并不是一个纯粹的引用类型,它是结构体:
type IntSlice struct {
ptr *int
len, cap int
}
我们的appendInt函数每次只能添加一个元素,而append函数可以添加多个,甚至是一个slice:
var x []int
x = append(x, 1)
x = append(x, 2, 3)
x = append(x, 4, 5, 6)
x = append(x, x...) // 追加slice x
fmt.Println(x) // "[1 2 3 4 5 6 1 2 3 4 5 6]"
现在我们将appendInt进行完善,以达到append函数类似的效果。其中用到了变参函数,在下一章中会详细解释:
func appendInt(x []int, y ...int) []int {
var z []int
zlen := len(x) + len(y)
// ...expand z to at least zlen...
copy(z[len(x):], y)
return z
}
4.2.2. 一些就地操作的技巧
再来看看更多的slice就地操作的例子,例如旋转、反转、修改元素。给定一个字符串列表,nonempty将在原有slice空间内进行操作,然后返回不包含空字符串的列表:
// Nonempty is an example of an in-place slice algorithm.
package main
import "fmt"
// nonempty returns a slice holding only the non-empty strings.
// The underlying array is modified during the call.
func nonempty(strings []string) []string {
i := 0
for _, s := range strings {
if s != "" {
strings[i] = s
i++
}
}
return strings[:i]
}
这里比较精妙的地方是,输入slice和输出slice共享底层数组,这样就避免了重新分配一个数组,不过造成的问题是原来的数据可能会被覆盖:
data := []string{"one", "", "three"}
fmt.Printf("%q\n", nonempty(data)) // `["one" "three"]`
fmt.Printf("%q\n", data) // `["one" "three" "three"]`
根据4.2.1的内容,我们通常会这样使用nonempty函数:
data = nonempty(data)
。
nonempty函数也可以使用append实现:
func nonempty2(strings []string) []string {
out := strings[:0] // zero-length slice of original
for _, s := range strings {
if s != "" {
out = append(out, s)
}
}
return out
}
无论采用哪种实现方式,按这种方式重用数组要求每个输入值最多只有一个输出值,这种模式对很多算法都是适用的:过滤一个值序列或者合并值序列中的相邻元素。这种用法是较为复杂的,也是较为少见的,但是在某些场合中可以发挥奇效。
可以用slice来模拟栈(stack)。给定一个空的slice,它对应空stack,然后使用append函数将新值入栈:
stack = append(stack, v) // push v
栈顶对应的是slice最后一个元素:
top := stack[len(stack)-1] // top of stack
通过slice操作可以弹出栈顶元素:
stack = stack[:len(stack)-1] // pop
要删除slice某个元素i并保存原有的元素顺序,可以通过copy将i后面的元素依次向前移动一位:
func remove(slice []int, i int) []int {
copy(slice[i:], slice[i+1:])
return slice[:len(slice)-1]
}
func main() {
s := []int{5, 6, 7, 8, 9}
fmt.Println(remove(s, 2)) // "[5 6 8 9]"
}
如果删除元素且不用保持原有顺序,可以用最后一个元素覆盖被删除的元素:
func remove(slice []int, i int) []int {
slice[i] = slice[len(slice)-1]
return slice[:len(slice)-1]
}
func main() {
s := []int{5, 6, 7, 8, 9}
fmt.Println(remove(s, 2)) // "[5 6 9 8]
}
练习 4.3: 重写reverse函数,使用数组指针代替slice。
练习 4.4: 编写一个rotate函数,通过一次循环完成旋转。
练习 4.5: 写一个函数,就地消除[]string中相邻的重复字符串
练习 4.6: 编写一个函数,给定一个UTF-8编码的[]byte类型的slice,就地将该slice中的相邻的两个Unicode空格(参见unicode.IsSpace)替换成一个ASCII空格
练习 4.7: 修改reverse函数,给定一个[]byte,对应的是UTF-8编码的字符串,然后就地反转。是否可以做到无内存分配?
有疑问加站长微信联系(非本文作者)