数组和切片：Append的实现方式

图文无关

本文翻译自Rob Pike的文章《Arrays, slices (and strings): The mechanics of 'append'》，原文地址 https://blog.golang.org/slices。

原博文中出了一些练习，译者提出了自己的解法，原文中并不包含这些解法。

前言

数组是面向过程的的编程语言最常见的特性之一。
数组看起来很简单，不过要在语言中实现这一特性往往要面临很多问题，比如：

• 数组应该是固定长度还是是可变长度？
• 长度应该是数组类型的属性吗？
• 多维数组应该是什么样子？
• 如何定义空数组？

对上面问题的解答，关系着数组是否只是一个feature还是语言设计的核心。
在Go的早期开发中，花了大约一年时间来回答上面的问题。切片的引入是解决问题的关键，它建立在固定大小的数组上，提供了灵活，可扩展的数据结构。但是时至今日，Go语言新手经常在切片的使用上犯错，这可能与他们受过其他语言的影响有关。

在这篇博文中，我们将尝试通过解释内置append函数的工作原理，以及这个函数的设计思想，来帮助新手消除这些误解。

数组

数组是Go语言中的一个重要组成部分，但就像建筑的地基一样，它不容易让使用者觉察到。在深入了解切片之前，我们必须对数组有一个简单的了解。
在Go程序中，数组并不常见，因为长度是数组类型的一部分，而这一点限制了数组的表达能力。

下面语句

var buffer [256]byte

声明了一个占用256个byte，名为buffer的变量，buffer的类型中包含了它的长度，[256]byte。占用512个byte的数组的类型将是[512]byte。

buffer在内存中的表示就像下面这样

buffer: byte byte byte ... 重复256次 ... byte byte byte

buffer包含了256个字节的数据。我们可以通过常见索引的方式来访问这个数据的元素，buffer[0],buffer[1]直到buffer[255]。访问超过索引的元素将会导致程序崩溃。

内置的len函数能返回数组和其他几种类型的长度。对数据来说，len函数的返回时显而易见的，比如len(buffer)会返回256。

数组时很有用的，它可以用来表示转换矩阵。但是在Go语言中，数组最常见的作用是存储切片的数据。

切片

切片头

切片是本文讨论的重点，要想合理地使用它，必须先理解它的工作方式。

切片是描述与切片变量本身分开存储的数组的连续部分的数据结构。切片不是数组。切片描述了数组的一部分。

我们可以通过下面的方式创建一个切片，这个切片描述了buffer数组第100(闭区间)到150(开区间)之间的元素

var slice []byte = buffer[100:150]

变量slice的类型是[]byte，它从buffer数组中初始化。更加通用的初始化语句如下：

var slice = buffer[100:150]

在函数内部可以定义的更简短些

slice := buffer[100:150]

这个slice变量到底是什么呢？现在设想切片是一个包含两个元素的的数据结构：长度和指向数组某个元素的指针。可以认为就像下面的结构体一样

type sliceHeader struct {
    Length              int
    ZerothElement       *byte
}

slice := sliceHeader {
    Length:         50
    ZeroElement     &buffer[100],
}

当然，真正的实现肯定不是这样的。尽管sliceHeader对程序员是不可见的，并且指针和指向的元素类型有关，但是上面的代码展示了实现的正确思路。

之前我们对一个数据进行了切片操作，其实我们也可以对一个切片进行切片，比如下面这样

slice2 := slice[5:10]

和之前一样，这行代码创建了一个新的切片，指向原来切片的5到9(闭)之间的元素，也就是说指向了buffer数组的105到109之间的元素。slice2的sliceHeader结构就像下面这样

slice := sliceHeader{
    Length:         5,
    ZerothElement       &buffer[105],
}

我们也可以执行reslice操作，即对一个切片进行切片操作，并把返回值传给之前的切片

slice = slice[5:10]

这时slice就和slice2的结构一样了。reslice操作对截断一个切片是很有用的，比如下面的代码中截掉了第一个和最后一个元素

slice = slice[1:len(slice)-1]

你能经常听到有经验的Go程序员谈论slice header，因为这就是切片变量存储的形式。举个例子，当你调用一个传入一个切片作为参数的函数，比如bytes.IndexRune，实际上传入的就是一个slice header

slashPos := bytes.IndexRune(slice, '/')

练习：写出经过上面操作后slice变量的sliceHeader

slice := sliceHeader{
    Length:         3,
    ZerothElement       &buffer[106],
}

将切片作为参数传入

有必要知道，即使切片包含了一个指针，它本身也是有值的，它是一个包含一个指针和一个长度数值的结构体实例，并不是一个指向这个结构体实例的指针。

在上面的例子中，indexRune函数传入了一个slice header的拷贝。这很重要。

考虑下面的函数。

func AddOneToEachElement(slice []byte){
    for i:= range slice {
        slice[i++]
    }
}

函数功能就是遍历切片中的元素，每个元素加1.

实际跑跑看：

func main(){
    slice := buffer[10:20]
    for i := 0; i < len(slice); i++ {
        slice[i] = byte(i)
    }
    fmt.Println("before", slice)
    AddOneToEachElement(slice)
    fmt.Println("after", slice)
}

// before [0 1 2 3 4 5 6 7 8 9]
// after [1 2 3 4 5 6 7 8 9 10]

尽管slice header是通过传值的方式传给函数，但是因为header中包含了指向某个数组的指针，所以原始的header和作为参数传入函数header的拷贝其实描述的都是同一个数组。因此当函数返回时，可以通过原始slice变量查看修改后的元素。

传入函数的参数实际上是一个复制，比如下面的例子：

func SubtractOneFromLength(slice []byte) []byte {
    slice = slice[0 : len(slice)-1]
    return slice
}

func main() {
    fmt.Println("Before: len(slice) =", len(slice))
    newSlice := SubtractOneFromLength(slice)
    fmt.Println("After: len(slice)=", len(slice))
    fmt.Println("After: len(newSlice) =", len(newSlice))
}

// Before: len(slice) = 50
// After:  len(slice) = 50
// After:  len(newSlice) = 49

我们可以看到切片指向的内容能够被函数改变，而切片的header不能被函数改变。slice变量中长度属性不会被函数修改，因为传入函数的是切片header的一份拷贝，并不是header本身。因此。如果想写一个函数修改header，就必须将修改后的header作为结果返回。在上面的例子中，slice变量本身并没有被改变，但是返回的切片有了新的长度，这个返回存在了newSlice中。

指向切片的指针

另外一种可以在函数中改变切片header的方式就是传入指向切片的指针。下面是一个例子。

func PtrSubtractOneFromLength(slicePtr *[]byte) {
    slice := *slicePtr
    *slicePtr = slice[0 : len(slice)-1]
}

func main() {
    fmt.Println("Before: len(slice) =", len(slice))
    PtrSubtractOneFromLength(&slice)
    fmt.Println("After: len(slice) =", len(slice))
}

// Before: len(slice) = 50
// After:  len(slice) = 49

上面的例子看起来有点傻，特别是增加了一个临时变量来改变切片的长度。处理切片指针是很常见的情况，通常，在修改切片的函数中，都会使用一个指针接收器。

假设我们想实现一个方法，截断切片中最后一个'/'及其后面的元素，可以这样写

type path []byte

func (p *path) TruncateAtFinalSlash() {
    i := bytes.LastIndex(*p, []byte("/"))
    if i >= 0 {
        *p = (*p)[0:i]
    }
}

func main() {
    pathName := path("/usr/bin/tso")
    pathName.TruncateAtFinalSlash()
    fmt.Println("%s\n", pathName)
}

// /usr/bin

练习：将接收器的类型由指针修改为值，然后再跑一遍
修改后的函数为

func (p path) TruncateAtFinalSlash() {
    i := bytes.LastIndex(p, []byte("/"))
    if i >= 0 {
        p = p[0:i]
    }
}

// /usr/bin/tso
// 因为传入的是pathName的拷贝，main函数中的pathName的长度并没有发生改变

另一方面，如果想实现一个方法，将path中的ASCII值变为大写，那么可以传入一个值，因为传入的值依然会指向同一个数组。

type path []byte

func (p path) ToUpper(){
    for i, b := range p {
        if 'a' <= b && b <= 'z' {
            p[i] = b + 'A' - 'a'
        }
    }
}

func main() {
    pathName := path("/usr/bin/tso")
    pathName.ToUpper()
    fmt.Println("%s\n", pathName)
}

// /USR/BIN/TSO

练习： 修改ToUpper方法，使用指针接收器，看看结果会不会有变化

func (p *path) ToUpper() {
    for i, b := range *p {
        if 'a' <= b && b <= 'z' {
            (*p)[i] = b + 'A' - 'a'
        }
    }
}

// /USR/BIN/TSO
结果没有变化

容量

下面这个函数每次都会为一个切片添加一个元素。

func Extend(slice []int, element int) []int {
    n := len(slice)
    slice = slice[0 : n+1]
    slice[n] = element
    return slice
}

func main() {
    var iBuffer [10]int
    slice := iBuffer[0:0]
    for i := 0; i < 20; i++ {
        slice = Extend(slice, i)
        fmt.Println(slice)
    }
}

// [0]
// [0 1]
// [0 1 2]
// [0 1 2 3]
// [0 1 2 3 4]
// [0 1 2 3 4 5]
// [0 1 2 3 4 5 6]
// [0 1 2 3 4 5 6 7]
// [0 1 2 3 4 5 6 7 8]
// [0 1 2 3 4 5 6 7 8 9]
// panic: runtime error: slice bounds out of range

// goroutine 1 [running]:
// panic(0x1022c0, 0x1040a018)
//  /usr/local/go/src/runtime/panic.go:500 +0x720
// main.main()
//  /tmp/sandbox219409371/main.go:27 +0x1e0

现在该聊一聊slice header的第三个属性--容量了。除了数组指针和长度，slice header也存储了容量。

type sliceHeader struct {
    Length          int
    Capacity        int
    ZerothElement   *byte
}

Capacity属性记录了切片指向的数组实际占有的空间，它是Length的最大值。如果切片的长度超过了容量，会导致程序的崩溃。

在执行下面的语句后

slice := iBuffer[0:0]

slice的header结构如下

slice := sliceHeader{
    Length:         0,
    Capacity:           10,
    ZerothElement:  &iBuffer[0],
}

属性Capacity的值为指向数组的长度减去切片指向的第一个元素在数组中的索引值。可以使用内置的cap函数获取切片的容量。

if cap(slice) == len(slice) {
    fmt.Println("slice is full!")
}

Make方法

如果想要扩展切片使其大于本身的容量呢？不可能！容量一定是切片大小所能达到的极限值。但是可以通过创建一个新的数组，将原来数组中的元素复制过去，然后让切片来描述这个新数组。

我们可以使用内置的new函数来生成一个更大的数组，然后对其切片，但是使用内置的make函数会更简单一些。make函数会创建一个新的数组的同时，创建一个切片来描述这个数组。make函数接受三个参数：切片的类型，长度，容量，容量也就是创建的数组的大小。

下面的代码会创建一个长度为10，容量为15的切片。

slice := make([]int, 10, 15)
fmt.Println("len %d, cap: %d\n", len(slice), cap(slice))

// len: 10, cap: 15

下面的代码会让slice的容量加倍，但是长度不变

slice := make([]int, 10 ,15)
fmt.Println("len: %d, cap: %d\n", len(slice), cap(slice))
newSlice := make([]int, len(slice), 2*cap(slice))
for i := range slice {
    newSlice[i] = slice[i]
}
slice = newSlice
fmt.Println("len: %d, cap: %d", len(slice), cap(slice))

// len: 10, cap: 15
// len: 10, cap: 30

当创建切片时，经常需要长度和容量一致，在这种情况下，可以不传入容量，容量值默认为长度值。

gophers := make([]Gopher, 10)
// gophers 的容量和长度都为10

Copy

在上面的例子中，当容量增倍时，使用了一个循环将旧切片中的值，传给了新的切片。Go有一个内置copy函数来简化这一操作。copy函数接受两个切片，将右边切片的内容复制给左边的切片。示例代码如下

newSlice := make([]int, len(slice), 2*cap(slice))
copy(newSlice, slice)

copy方法是很智能的，它会关注两边切片的长度，复制能复制的部分。换句话说，它复制的元素个数等于两个切片长度的较小值。这能帮助使用者省不少事。copy函数会返回复制的元素个数，尽管有时候并没有必要进行相应的检查。

当源切片和目的切片在内容上有重合时，copy也能正确工作，也就是说我们可以使用copy来进行移位操作。下面是一个使用copy来在切片中间插入一个元素的例子。

// 在指定的index处插入一个值
// 这个index必须在容量范围内
func Insert(slice []int, index, value int) []int {
    slice = slice[0 : len(slice)+1]
    copy(slice[index+1:], slice[index:])
    slice[index] = value
    return slice
}

上面的函数中有一些需要注意的。首先，它返回了一个长度被改变的切片；其次，上面例子中使用了一个简写。表达式

slice[i:]

和表达式

slice[i:len(slice)]

产生的效果是一样的。同样的，也可以把冒号左边的值留空，它默认为0。
所以slice[:]就是他本身。

现在将Insert函数跑起来

slice := make([]int, 10, 20)
for i := range slice {
    slice[i] = i
}
fmt.Println(slice)
slice = Insert(slice, 5, 99)
fmt.Println(slice)

// [0 1 2 3 4 5 6 7 8 9]
// [0 1 2 3 4 99 5 6 7 8 9]

Append

上面的例子中，我们写一个Extend函数将一个元素添加到切片。这个函数是有bug的，当切片的容量太小时，程序会崩溃掉(Insert函数也有同样的问题)。现在来写一个更加健壮的函数来实现向[]int类型的切片添加元素的功能

func Extend(slice []int, element int) []int {
    n := len(slice)
    if n == cap(slice) {
        newSlice := make([]int, len(slice), 2*len(slice)+1)
        copy(newSlice, slice)
        slice = newSlice
    }
    slice = slice[0 : n+1]
    slice[n] = element
    return slice
}

上面的函数重新分配了一个数组，所以必须将新生成切片返回。下面的代码会调用Extend函数

slice := make([]int, 0, 5)
for i:= 0; i < 10; i++ {
    slice = Extend(slice, i)
    fmt.Printf("len=%d cap=%d slice=%v\n", len(slice), cap(slice), slice)
    fmt.Println("address of 0th element:", &slice[0])
}

// len=1 cap=5 slice=[0]
// address of 0th element: 0x10432200
// len=2 cap=5 slice=[0 1]
// address of 0th element: 0x10432200
// len=3 cap=5 slice=[0 1 2]
// address of 0th element: 0x10432200
// len=4 cap=5 slice=[0 1 2 3]
// address of 0th element: 0x10432200
// len=5 cap=5 slice=[0 1 2 3 4]
// address of 0th element: 0x10432200
// len=6 cap=11 slice=[0 1 2 3 4 5]
// address of 0th element: 0x10436120
// len=7 cap=11 slice=[0 1 2 3 4 5 6]
// address of 0th element: 0x10436120
// len=8 cap=11 slice=[0 1 2 3 4 5 6 7]
// address of 0th element: 0x10436120
// len=9 cap=11 slice=[0 1 2 3 4 5 6 7 8]
// address of 0th element: 0x10436120
// len=10 cap=11 slice=[0 1 2 3 4 5 6 7 8 9]
// address of 0th element: 0x10436120

可以看到，在初始的容量5被占满后，新切片的容量，和指向的第一个元素的地址都变化了。

继承上面Extend函数的思路，我们甚至可以实现一个方法来在切片添加多个元素。要实现这样的功能，需要用到Go语言讲参数列表转换为切片的特性。也就是Go语言的可变参数特性。

新的函数叫做Append。在第一个版本中，我们直接多次调用Extend来实现相应的功能。Append函数的声明如下：

func Append(slice []int, items ...int) []int

实现如下

func Append(slice []int, items ...int) []int {
    for _, item := range items {
        slice = Extend(slice, item)
    }
}

实际跑一跑

slice := []int{0, 1, 2, 3, 4}
fmt.Println(slice)
slice = Append(slice, 5, 6, 7, 8)
fmt.Println(slice)

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

Append函数还有另外一个有意思的特性。我们不仅可以追加单个元素，还能够追加另外一个切片。

slice1 := []int{0, 1, 2, 3, 4}
slice2 := []int{55, 66, 77}
fmt.Println(slice1)
slice1 = Append(slice1, slice2...)
fmt.Println(slice1)

// [0 1 2 3 4]
// [0 1 2 3 4 55 66 77]

当然，可以在不调用Extend的情况下，实现Append。

func Append(slice []int, elements ...int) []int {
    n := len(slice)
    total := len(slice) + len(elements)
    if total > cap(slice) {
        newSize := total*3/2 + 1
        newSlice := make([]int, total, newSize)
        copy(newSlice, slice)
        slice = newSlice
    }
    slice = slice[:total]
    copy(slice[n:], elements)
    return slice
}

注意新版的Append调用了两次copy，第一次将旧切片的内容复制到新切片，第二次将要加入的元素复制到新切片。

slice1 := []int{0, 1, 2, 3, 4}
slice2 := []int{55, 66, 77}
fmt.Println(slice1)
slice1 = Append(slice1, slice2...)
fmt.Println(slice1)

// [0 1 2 3 4]
// [0 1 2 3 4 55 66 77]

内置的Append函数

现在终于谈到内置的Append函数了。内置的Append和上面的示例实现一样的功能，并且对任何类型都适用。

要记住的是，在调用Append后切片的header会改变，所以需要保存返回的切片。事实上，如果调用了Append而没有保存结果的话，编译的时候就会报错。

下面是一些使用的例子

slice := []int{1, 2, 3}
slice2 := []int{55, 66, 77}
fmt.Println("Start slice: ", slice)
fmt.Println("Start slice2: ", slice2)

// Start slice: [1, 2, 3]
// Start slice2: [55, 66, 77]

slice = append(slice, 4)
fmt.Println("Add one item:", slice)

// Add one item: [1, 2, 3, 4]

slice = append(slice, slice2...)
fmt.Println("Add one slice:", slice)

// Add one slice: [1, 2, 3, 4, 55, 66, 77]

slice3 := append([]int(nil), slice...)
fmt.Println("Copy a slice:", slice3)

// Copy a slice: [1, 2, 3, 4, 55, 66, 77]

fmt.Println("Before append to self:", slice)
slice = append(slice, slice...)
fmt.Println("After append to self:", slice)

// After append to self: [1 2 3 4 55 66 77 1 2 3 4 55 66 77]

Nil

现在来看值为nil的切片。很自然的，nil是slice header的零值

sliceHeader{
    Length:     0,
    Capacity:       0,
    ZerothElement: nil,
}

或者

sliceHeader{}

元素指针也是nil。

由数组array[0:0]创建的切片，长度为0（甚至容量也是0），但是元素指针不是nil，因此它不是nil切片，容量可以扩大。而值为nil的切片容量不可能扩大，因为它没有指向任何数组元素。

这也就是说，nil切片在功能上等同于零长度的切片，即使它没有指向任何数组。它的长度为0，可以被通过重新分配来扩展。

字符串

在了解了切片的基础上，我们来聊聊字符串。
字符串实际上非常简单：它是只读的切片，类型为byte，并且有着语法层面上的一些特性。

因为字符串是只读的，不能被修改，所以没必要考虑容量。

可以通过索引的方式访问其中的元素

slash := "/usr/ken"[0]
// /

可以通过切片来获取子串

usr := "/usr/ken"[0:4]
// /user

可以通过byte切片来创建一个字符串

str := string(slice)

或者通过字符串来创建一个切片

slice += []byte(usr)

对使用者来说，字符串对应的数组是不可见的，只能操作字符串来访问其中的元素。这意味着，由字符串转切片或者由切片转字符串，必须创建一份数组的拷贝。当然，Go语言已经处理好了这一切，使用者不用再操心。在转换完成后，修改切片指向的数组不会影响到原始的字符串。

使用类似切片的方式来构建字符串又一个很明显的好处，就是创建子字符串的操作非常高效。并且由于字符串是只读的，字符串和子串可以安全地共享共同的数组。

结语

理解切片的实现方式，对理解切片是如何工作是非常有帮助的。当理解了切片的工作方式，切片可以在使用者手里变的简单又高效。

“本译文仅供个人研习、欣赏语言之用，谢绝任何转载及用于任何商业用途。本译文所涉法律后果均由本人承担。本人同意简书平台在接获有关著作权人的通知后，删除文章。”