slice

slice 又称动态数组，依托数组实现，可以方便地进行扩容和传递，实际使用时比数组更灵活

正因为灵活，实际使用时容易出错，避免出错的方法之一便是了解其实现原理

热身测验

(1) 题目一

下面的函数输出什么？

func SliceCap() {
    var array [10]int
    var slice = array[5:6]

    fmt.Printf("len(slice) = %d\n", len(slice))
    fmt.Printf("cap(slice) = %d\n", cap(slice))
}

解答:
本题考察 slice 的基本内存布局
函数输出:

1 2	`len(slice) = 1 cap(slice) = 5`

(2) 题目二

下面的函数输出什么(单选)？

func SliceRise(s []int) {
    s = append(s, 0)
    for i := range s {
        s[i]++
    }
}

func SlicePrint() {
    s1 := []int{1, 2}
    s2 := s1
    s2 = append(s2, 3)
    SliceRise(s1)
    SliceRise(s2)
    fmt.Println(s1, s2)
}

A: [2,3] [2,3,4]
B: [1,2] [1,2,3]
C: [1,2] [2,3,4]
D: [2,3,1] [2,3,4,1]

解答:
本题考察内置函数 append() 操作切片时的细节
函数输出: [1 2] [2 3 4]

(3) 下面一段代码的输出结果是什么？

https://mp.weixin.qq.com/s/kEQI74ge6VhvNEr1d3JW-Q

package main

import "fmt"

func main() {
    sl := make([]int, 0, 10)
    var appenFunc = func(s []int) {
        s = append(s, 10, 20, 30)
        fmt.Println(s)
    }
    fmt.Println(sl)
    appenFunc(sl)
    fmt.Println(sl)
    fmt.Println(sl[:10])
}

看上去的结果:

[]
[10 20 30]
[]
[]

正确的结果:

[]
[10 20 30]
[]
[10 20 30 0 0 0 0 0 0 0]

为什么输出 sl 和 sl[:10] 的结果差别这么大，这与预期的输出结果不一致。

核心要记住的是：slice 真正存储数据的地方，是一个数组。slice 的结构中存储的是指向所引用的数组指针地址。

实质上在调用 appenFunc(sl) 函数时，实际上修改了底层所指向的数组，自然也就会发生变化，也就不难理解为什么 10, 20, 30 元素会出现了。

那为什么 sl 变量的长度是 0，甚至有人猜测是不是扩容了，这其实和上面的问题还是一样，因为是值传递，自然也就不会发生变化。

要记住一个关键点：如果传过去的值是指向内存空间的地址，是可以对这块内存空间做修改的。反之，你也改不了。

当是切片（slice）时，表达式 s[low : high] 中的 high，最大的取值范围对应着切片的容量（cap），不是单纯的长度（len）。
因此调用 fmt.Println(sl[:10]) 时可以输出容量范围内的值，不会出现越界。

相对的 fmt.Println(sl) 因为该切片 len 值为 0，没有指定最大索引值，high 则取 len 值，导致输出结果为空。

我们要牢记：如果传过去的值是指向内存空间的地址，是可以对这块内存空间做修改的。这在多种应用场景下都是适用的。

所谓的最大取值范围，除非官方给你写定 len 或 cap，否则不要过于主观的认为，因为他会根据访问的数据类型和访问定位等改变。

特性速览

初始化

声明和初始化切片的方式主要有以下几种:

变量声明
字面量
使用内置函数 make()
从切片和数组中切取

(1) 变量声明:

1	`var s []int`

这种方式声明的切片变量与声明其他类型变量一样，变量值都为零值，对于切片来讲零值为 nil

(2) 字面量

1 2	`s1 := []int{} // 空切片 s2 := []int{1, 2, 3} // 长度为 3 的切片`

也可以使用字面量初始化切片，需要了解的是空切片是指长度为空，其值不是 nil

声明长度为 0 的切片时，推荐使用变量声明的方式获得一个 nil 切片，而不是空切片，因为 nil 切片不需要内存分配

(3) 内置函数 make()

1 2	`s1 := make([]int, 12) // 指定长度 s2 := make([]int, 10, 100) // 指定长度和空间`

内置函数 make() 可以创建切片，切片元素均初始化为相应类型的零值
推荐指定长度的同时指定预估空间，客有效地减少切片扩容时内存分配及拷贝次数。

(4) 切取

array := [5]int{1, 2, 3, 4, 5}
s1 := array[0:2]   // 从数组中切取
s2 := s1[0:1]  // 从切片中切取
fmt.Println(s1)  // [1 2]
fmt.Println(s2)  // [1]

切片可以基于数组和切片创建，需要了解的是切片与原数组或切片共享底层空间，修改切片会影响原数组或切片

切片表达式 [low:high] 表示的是左闭右开 [low, high) 区间，切取的长度为 high - low。
另外，适用于任意类型的内置函数 new() 也可以创建切片

1	`s := *new([]int)`

此时创建的切片值为 nil

切片操作

内置函数 append() 用于向切片中追加元素

s := make([]int, 0)
s = append(s, 1)    // 添加 1 个元素
s = append(s, 2, 3, 4)   // 添加多个元素
s = append(s, []int{5, 6}...)  // 添加 1 个切片
fmt.Println(s)  // [1 2 3 4 5 6]

当切片空间不足时，append() 会先创建新的大容量切片，添加元素后再返回新切片

内置函数 len() 和 cap() 分别用于查询切片的长度及容量，由于切片的本质为结构体，结构体中直接存储了切片的长度和容量，所以这两个操作的时间复杂度均为 O(1)

其他操作，比如按下标访问切片元素及遍历与数组操作类似，这里不再赘述

实现原理

slice 依托数组实现，底层数组对用户屏蔽，在底层数组容量不足时可以实现自动重分配并生成新的 slice。
接下来按照实际使用场景分别介绍其实现机制

数据结构

源码包中的 src/runtime/slice.go:slice 定义了 slice 的数据结构:

type slice struct {
    array unsafe.Pointer
    len int
    cap int
}

切片操作

(1) 使用 make() 创建 slice

使用 make() 创建 slice 时，可以同时指定长度和容量，创建时底层会分配一个数组，数组的长度即为容量

例如，slice := make([]int, 5, 10) 语句所创建的 slice 的结构如下图所示

slice创建结构示意图

该 slice 的长度为 5，即可以使用下标 slice[0] ~ slice[4] 来操作里面的元素，capacity 为 10，表示后续向 slice 添加新的元素时可以不必重新分配内存，直接使用预留内存即可，直到预留内存不足时再扩容

(2) 使用数组创建 slice

使用数组创建 slice 时，slice 将与原数组共用一部分内存

例如, slice := array[5:7] 语句所创建的 slice 的结构如下图所示:

使用数组创建slice示意图

数组和数组的切片共享底层存储空间，这是使用过程中需要额外注意的地方

(3) slice 扩容

使用 append 向 slice 追加元素时，如果 slice 空间不足，则会触发 slice 扩容，扩容实际上是重新分配一块更大的内存，将原 slice 的数据拷贝进新 slice，然后返回新 slice，扩容后再将数据追加进去

例如，当向一个 capacity 为 5 且 length 也为 5 的 slice 再次追加 1 个元素时，就会发生扩容，如下图所示

slice扩容示意图

扩容操作只关心容量，会把原 slice 的数据拷贝到新的 slice 中，追加数据由 append 在扩容结束后完成。
由上图可见，扩容后新 slice 的长度仍然是 5，但容量由 5 提升到了 10，原 slice 的数据也都拷贝到了新 slice 指向的数组中

扩容容量的选择遵循以下基本规则:

如果原 slice 的容量小于 1024，则新 slice 的容量将扩大为原来的 2 倍
如果原 slice 的容量大于或等于 1024，则新 slice 的容量将扩大为原来的 1.25 倍

在该规则的基础上，还会考虑元素类型与内存分配规则，对实际扩张值做一些微调。从这个基本规则中可以看出 Go 对 slice 的性能和空间使用率的思考

当切片较小时，采用较大的扩容倍速，可以避免频繁地扩容，从而减少内存分配的次数和数据拷贝的代价
当切片较大时，采用较小的扩容倍速，主要是为了避免浪费空间。

使用 append() 向 slice 添加一个元素的实现步骤如下:

假如 slice 的容量够用，则将新元素追加进去，slice.len++, 返回原 slice
原 slice 的容量不够，则将 slice 先扩容，扩容后得到新 slice
将新元素追加进新 slice，slice.len++，返回新的 slice
slice 拷贝

使用 copy() 内置函数拷贝两个切片时，会将源切片的数据逐个拷贝到目的切片指向的数组中，拷贝数量取两个切片长度的最小值

例如长度为 10 的切片拷贝到长度为 5 的切片中时，将拷贝 5 个元素

也就是说，拷贝过程中不会发生扩容

小结

每个切片都指向一个底层数组
每个切片都保存了当前切片的长度、底层数组和可用容量
使用 len() 计算切片长度的时间复杂度为 O(1)，不需要遍历切片
使用 cap() 计算切片容量的时间复杂度为 O(1)，不需要遍历切片
通过函数传递切片时，不会拷贝整个切片，因为切片本身只是一个结构体而已
使用 append() 向切片追加元素时有可能触发扩容，扩容后会生成新的切片

此处有几个值得注意的编程小建议

创建切片时可根据实际需要预分配容量，尽量避免在追加过程中的扩容操作，有利于提升性能
切片拷贝时需要判断实际拷贝的元素个数
谨慎使用多个切片操作同一个数组，以防读写冲突

切片表达式

slice 表达式可以基于一个字符串生成子字符串，也可以从一个数组或切片中生成切片。Go 语言提供了两种 slice 表达式

简单表达式 a[low : high]
扩展表达式 a[low : high : max]

简单表达式

简单表达式日常使用的频率比较高，其格式为:

1	`a[low : high]`

如果 a 为数组或切片，则该表达式将切取 a 位于 [low, high) 区间的元素并生成一个新的切片。
如果 a 为字符串，稍微有一点特殊的是该表达式会生成一个字符串，而不是切片。
为了叙述方便，下面均以数组和切片为例进行说明

简单表达式生成的切片的长度为 high - low。例如，我们使用简单表达式切取数组 a 并生成新的切片 b:

1 2	`a := [5]int{1, 2, 3, 4, 5} b := a[1:4]`

此时得到的切片 b 的长度为 3，元素分别为:

1
2
3

b[0] == 2
b[1] == 3
b[2] == 4

(1) 底层数组共享

根据之前介绍的切片的数据结构，我们知道每个切片包含三个元素:

type slice struct {
    array unsafe.Pointer   // 切片底层数组的起始位置
    len int  // 切片长度
    cap int // 切片容量
}

这里需要着重强调的是，使用简单表达式生成的切片将与原数组或切片共享底层数组。新切片的生成逻辑可以使用以下伪代码表示:

1
2
3

b.array = &a[low]
b.len = high - low
b.cap = len(a) - low

对于一个长度为 10 的数组，使用简单表达式切取其两个元素生成的新切片的拓扑结构如下图所示:

使用数组创建slice示意图

(2) 边界问题

如果简单表达式切取的对象为字符串或数组，那么在表达式 a[low : high] 中 low 和 high 的取值需要满足以下关系:

0 <= low <= high <= len(a)

如果表达式的边界不满足这个关系，则会发生越界并触发 panic，这是比较容易理解的

如果简单表达式切取的对象为切片，那么在表达式 a[low : high] 中的 low 和 high 的最大取值可为 a 的容量，而不是 a 的长度，即满足以下关系

0 <= low <= high <= cap(a)

low 和 high 的取值可以超越 len(a)，这一点还是值得注意的，实际使用时要慎重，可以使用下面的代码验证它:

// int64 转 string
package main

import (
    "fmt"
)

func SliceCap() {
    baseSlice := make([]int, 0, 10)
    newSlice := baseSlice[2:5]
    fmt.Printf("newSlice: %v", newSlice) // newSlice: [0 0 0]
}

func main() {
    SliceCap()
}
// newSlice: [0 0 0]

(3) 切取 string

表达式 a[low : high] 作用于数组、切片时将产生新的切片，作用于字符串时则会产生新的字符串，而不是切片

这是由 string 和 slice 的类型差异决定的，slice 可以支持随机读写，而 string 则不可以。

// int64 转 string
package main

import (
    "fmt"
    "reflect"
)

func SliceString() {
    baseStr := "Hello World!"
    fmt.Printf("baseStr: %s\n", baseStr)
    fmt.Printf("baseStr type: %s\n", reflect.TypeOf(baseStr))

    newStr := baseStr[0:5]
    fmt.Printf("newStr: %s\n", newStr)
    fmt.Printf("newStr type: %v\n", reflect.TypeOf(newStr))
}

func main() {
    SliceString()
}
// baseStr: Hello World!
// baseStr type: string
// newStr: Hello
// newStr type: string

(4) 默认值

为了使用方便，简单表达式 a[low : high] 中的 low 和 high 都是可以省略的

low 的默认值为 0，而 high 的默认值为表达式作用对象的长度

1
2
3

a[:high] // 等同于 a[0: high]
a[0:]   // 等同于 a[0: len(a)]
a[:]  // 等同于 a[0: len(a)]

扩展表达式

简单表达式生成的新切片与原数组或切片共享底层数组避免了拷贝元素，节约内存空间的同时可能会带来一定的风险

新切片 b(b := a[low : high]) 不仅可以读写 a[low] 至 a[high-1] 之间的所有元素，而且在使用 append(b, x) 函数增加新的元素 x 时，还可能会覆盖 a[high] 及后面的元素。例如:

1
2
3

a := [5]int{1, 2, 3, 4, 5}
b := a[1:4]
b = append(b, 0) // 此时元素 a[4] 将由 5 变成 0

使用新切片覆盖 a[high] 及后面的元素，有可能是非预期的，从而产生灾难性的后果

Go 团队很早就关注到了这个风险，并且在 Go 1.2 中就提供了一种可以限制新切片容量的表达式，即扩展表达式:

1	`a[low : high : max]`

扩展表达式中的 max 用于限制新生成切片的容量，新切片的容量为 max - low，表达式的 low、high 和 max 需要满足以下关系:

0 <= low <= high <= max <= cap(a)

扩展表达式常见于偏底层的代码中，比如 Go 源代码。扩展表达式生成的切片将被限制存储容量，习惯上称其为被 "封印" 的切片。
当使用 append() 函数向被 "封印" 的切片追加新元素时，如果存储容量不足则会产生一个全新的切片，而不会覆盖原始的数组或切片

扩展表达式中的 a[low : high : max] 只有 low 是可以省略的，其默认值为 0。这一点与简单表达式略有不同