go 学习笔记一 —— slice 和 append

go 里面很重要的两个概念是 slice 和 array。
一般来说，slice 较 array 更常被使用，搞清楚这两种的区别，以及一些基本操作很有必要。

[TOC]

slice initialization

1
2
3
4
5
6
7
8
9
10
11
12
13
// slice initialization
a := make([]int, 2, 10)
fmt.Println(a)
fmt.Printf("len: %v, cap: %v\n", len(a), cap(a))
b := make([]int, 2)
fmt.Println(b)
fmt.Printf("len: %v, cap: %v\n", len(b), cap(b))
c := []int{}
fmt.Println(c)
fmt.Printf("len: %v, cap: %v\n", len(c), cap(c))
d := []int{1, 2}
fmt.Println(d)
fmt.Printf("len: %v, cap: %v\n", len(d), cap(d))

第一种 make 方法，可以指定底层数组的 len 和 cap，并用 slice 类型的默认值进行初始化。

第二种方法，是比较简洁的初始化方法，可以指定初始值，且其 len 和 cap 比较直观。

虽然本文不对 array 进行过多讨论，但其初始化方法与 slice 进行对比以便理解，还是很有必要的。

array initialization

array 是 slice 的底层数据结构，可以和 c 里面的数组类比理解。

1
2
3
4
5
6
7
8
9
// array initialization
var a [10]int
fmt.Println(a)

b := [10]int{1,2,3}
fmt.Println(b)

c := [...]int{1,2,3}
fmt.Println(c)

array 初始化与 slice 最大的区别就是指定了长度。第三种方法本质上长度还是固定的，只不过是根据后面的初始化列表推断的。

一种简单的判别 array 和 slice 的方法就是看初始化的时候有没有固定长度。

append

append 是 操作 slice 最常用的操作，也是本文的重点。

normal usage

1
2
3
4
5
6
// normal usage
var a []int
fmt.Println(a)
a = append(a, 5)
a = append(a, 6, 7)
fmt.Println(a)

append 扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
var a []int
fmt.Println(a)
fmt.Printf("len: %v, cap: %v\n", len(a), cap(a))

a = append(a, 5)
fmt.Println(a)
fmt.Printf("len: %v, cap: %v\n", len(a), cap(a))
fmt.Printf("address: %v\n", &a[0])

a = append(a, 10)
fmt.Println(a)
fmt.Printf("len: %v, cap: %v\n", len(a), cap(a))
fmt.Printf("address: %v\n", &a[0])

a = append(a, 1)
fmt.Println(a)
fmt.Printf("len: %v, cap: %v\n", len(a), cap(a))
fmt.Printf("address: %v\n", &a[0])

a = append(a, 6, 7)
fmt.Println(a)
fmt.Printf("len: %v, cap: %v\n", len(a), cap(a))
fmt.Printf("address: %v\n", &a[0])
/* result
[]
len: 0, cap: 0
[5]
len: 1, cap: 1
address: 0xc000100018
[5 10]
len: 2, cap: 2
address: 0xc000100040
[5 10 1]
len: 3, cap: 4
address: 0xc000112020
[5 10 1 6 7]
len: 5, cap: 8
address: 0xc000114000
*/

首先， append 是会改变 slice 底层数组, 当底层数组容量不够 append 后的长度时，会触发扩容机制： 申请更大的一个数组，并执行拷贝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// grow grows the slice s so that it can hold extra more values, allocating
// more capacity if needed. It also returns the old and new slice lengths.
func grow(s Value, extra int) (Value, int, int) {
    i0 := s.Len()
    i1 := i0 + extra
    if i1 < i0 {
        panic("reflect.Append: slice overflow")
    }
    m := s.Cap()
    if i1 <= m {
        return s.Slice(0, i1), i0, i1
    }
    if m == 0 {
        m = extra
    } else {
        for m < i1 {
            if i0 < 1024 {
                m += m
            } else {
                m += m / 4
            }
        }
    }
    t := MakeSlice(s.Type(), i1, m)
    Copy(t, s)
    return t, i0, i1
}

数组容量扩充的代码如上所示。

简单来说，原数组容量为0则最终容量等于扩充后的长度；小于1024的时候成倍增长，不小于1024时以25%的速率上升到不小于扩充后长度。

append 的具体实现

首先，得提一下 go 是没有范型支持，在这个前提上为什么 append 可以传入任何类型的 slice 并正确运行呢？

1
func append(slice []Type, elems ...Type) []Type

append 的接口定义如上所示，那么 Type 是什么为什么可以接受所有类型呢？是 interface{} 嘛？

其实答案也很简单，并不是。因为 go 没有范型支持，所以 append 是由编译器进行支持的。

其次，想弄明白 append 具体做了什么, 要提到一个小问题：回答下面程序的输出结果。

1
2
3
4
5
6
7
8
9
10
a := make([]int, 5, 10)
b := a
// fmt.Println(len(a), cap(a), &a[0])
// fmt.Println(len(b), cap(b), &b[0])
a = append(a, 1, 1, 1)
b = append(b, 2, 2)
fmt.Println(a)
fmt.Println(len(a), cap(a))
fmt.Println(b)
fmt.Println(len(b), cap(b))

如果你最后搞明白了这个程序的结果，那你就完全明白 slice 和 append 了。

首先， slice 相对于 C 里面的指针，其多了两个功能：当前数组的长度和最大容量。
第一步，用 slice a 初始化 b，此时 b 的 len、 cap 和指针都和 a 相同。
第二步，对 slice a 进行 append，底层数组的第5-7位（从0计数）被填充对应的值。此时 slice b 三个数值没有任何变化，即还是指向了和 slice a 一样的空间。
第三步，对 slice b 进行 append，底层数组的第5-6位被填充对应的值。

此时 slice a 和 b 的底层数组的指针还是一样的，即指向了同一片空间。所以输出结果乍一看有点反常理，其实理解了 slice 的机制也很容易想明白。

1
2
3
4
5
6
// answer
5 10
[0 0 0 0 0 2 2 1]
8 10
[0 0 0 0 0 2 2]
7 10

以下是从 blog 中找到了 go 1.13 的 具体实现，可以与上面的进行印证。

1
2
3
4
5
6
7
8
func Append(s Value, x ...Value) Value {
    s.mustBe(Slice)
    s, i0, i1 := grow(s, len(x)) // i0 为 append 前 len， i1 为 append 后 len
    for i, j := i0, 0; i < i1; i, j = i+1, j+1 {
        s.Index(i).Set(x[j])
    }
    return s
}

2021.03.11 补充
前段时间，同事问了一个问题：

1
2
3
4
5
6
a := []int{1}
a = append(a, 1)
fmt.Printf("len: %v, cap: %v\n%v\n", len(a), cap(a), a)

a = append(a, 3, 4, 5)
fmt.Printf("len: %v, cap: %v\n%v\n", len(a), cap(a), a)

答案为什么是

1
2
3
4
len: 2, cap: 2
[1 1]
len: 5, cap: 6
[1 1 3 4 5]

这个问题我们研究了好久，也没有得出最后的结论。

而如果分开 append， 则会出现预期的 cap 为 8 的结果。

查阅了 go 的相关源码并没有发现相关的细节。留个坑以后有空了汇编读一下，看看能不能找到具体的原因。