Go语言核心之美 3.2－slice切片

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，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) ):

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操作是常量级别的时间复杂度(只是更新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}
// 以2为支点，向左旋转
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) {
        // 还有空间，扩展slice
        z = x[:zlen]
    } else {
        // 空间不足，分配新的数组
        // 新数组的长度按2的倍数增长.
        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会重新分配一个足够大的数组，然后将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

通过切片操作可以弹出栈顶元素：

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编码的字符串，然后就地反转。是否可以做到无内存分配？

文章所有权：Golang隐修会 联系人：孙飞，CTO@188.com！