数组、切片(以及字符串): append内置函数的运作机制

介绍

数组是编程语言中最常用到的功能之一. 数组看起来是比较简单，但在一个语言要实现一个数组的时候，有些问题必须要解决，如：:

• 固定大小或可变大小?
• 是类型的一部分?
• 多为数组的模型?
• 空数组的意义?

这些问题的解决影响着数组仅是语言的一个功能还是其设计的核心部分.

在早期的Go语言发展中，在设计数组前大约用了1年的时间来决定这些问题. 关键的一步就是引入片, 可以在一个固定大小的数组上有一个灵活可扩展的数据结构. 是该类型的大小的一部分，新的Go程序员通常对片的工作原理十分困惑。也许其他编程语言对他们思想影响太深.

在这篇中将理清这些混乱. 我们将通过构建块来解释附加内置函数是如何工作的,以及为什么它的工作原理是这样的。

数组

数组是 Go语言的一个重要模块, 就像基础模块一样他们往往隐藏在一些可见组件中. 在我们转到更有趣，功能更强大更突出的片之前，我们必须先简单说一说这些组件。

数组不知经常出现在  Go语言程序中，因为数组的是他类型的一部分大小，这限制了数组的功能.

声明

var buffer [256]byte

声明了256个字节的变量缓冲区。这个类型的缓冲区包含它的大小,[256]字节。用512字节数组是不同的类型[512]字节。

与数组有关的数据仅仅是一个数组的元素。如下所示,类似数组缓冲池在内存中的样子，

buffer: byte byte byte ... 256 times ... byte byte byte

分片：分片头

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

在这个代码片段中，我们使用了完整的变量声明。变量slice是被声明为byte[]类型，它被初始化为一个buffer数组类型，包括100到150个slice元素。更通用的语法是丢掉类型，它通过初始化表达式进行设置。

var slice = buffer[100:150]

在一个函数我们可以使用简短的声明形式,

slice := buffer[100:150]

到底slice变量是什么呢？它虽然不是非常的完整，但是我们现在觉得slice作为一个小的数据结构拥有2个元素：一个长度和一个指针数组。你可以把它想象成是下面的样子：

type sliceHeader struct {
    Length        int
    ZerothElement *byte
}

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

当然，上面的只是一个说明。不管怎样这片代码结构对编程者是不可见的，元素指针的类型取决于元素的类型,但是给出了技术性的一个一般思想。

到目前为止，我们在数组上对slice进行操作，但是我们也可以切片一个slice：

slice2 := slice[5:10]

正如前面的一样，这种操作创建了一个新的slice，在这种情况下，原始slice拥有5到9（包括9）个元素，这就意味着原始数组有105到109个元素。slice2变量的形式和下面的sliceHeader结构体一样：

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

注意，这个头仍然指向底层相同的数组，存储buffer数组变量。

我们也重新切片，意思就是说我们截取一个slice，然后把截取后的结果返回到最初的结构中。

slice = slice[5:10]

slice变量的Headerstructure结构体看起来和slice2的一样。你将会看到会经常重复使用它们，例如截取一个slice。下面的截取是去掉了第一个和最后一个元素：

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

[练习，写出上面这种形式的结构体，作为之后的作业]

你会经常听到Go语言的程序员讲  "slice header"因为他确实是储存在切片变量里. 例如, 当你调用一个函数，它接受一个切片作为参数，如 bytes.IndexRune,在调用的时候，header是传递给行数的,

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

切片参数被传递到IndexRune这个函数 , 实际上传递的是 "slice header".

在切片头有更多数据，下面将会谈到, 但先让我们看看当你的程序用到了切片，切片头有什么意义.

给函数传递分片

理解这一点是很重要的：虽然片段包含指针，但是它本身却是只是一个值。解开这个秘密：它是一个含有指针和长度的结构的值。它不是一个指向结构的指针。

这一点非常重要。

当我们在前面的例子里调用IndexRune的时候,传递给它的是分片头的一个拷贝。这种行为可以得到重要的结果。

看看下面这个简单的函数：

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

试试这个例子：

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)
}

函数的参数实际上是一个拷贝，如下面的例子所示：

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))
}

这时我们可以看到由函数修改的分片参数的内容，不过分片头没有更改。存储在分片变量里的长度也不能通过调用函数而修改，这是因为传递给函数的是分片头的一个拷贝，不是原来的分片头。因此，如果我们想编写一个修改分片头的函数，那么我们必须把它当作结果参数返回，这儿我们就是这样做的。分片变量是无法做更改的，不过返回值具有新的长度，然后把这个返回值存储在新的分片中。

分片指针：方法中的接收者

让函数修改分片头的另一个方法是给这个函数传送指针。下面是前面例子的一次修改，实现了给函数传递指针：

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))
}

在这个例子里，这么做似乎很笨拙，尤其是在对额外增加的中间层的处理上（临时变量实现），不过，在这儿，你可以看到指向分片的指针却是很常见的。对要修改分片的函数来说，使用指针实现参数接收是常见的做法。

让我们说说我们需要一个在最后一个斜杠处截短分片的方法。我们如下编写：

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") // Conversion from string to path.
    pathName.TruncateAtFinalSlash()
    fmt.Printf("%s\n", pathName)
}

[练习：改变接收者的类型为一个数值而不是一个指针，然后继续运行。解释一下发生了什么]

另一方面，如果我们想要写一个方法来处理路径并把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.Printf("%s\n", pathName)
}

ToUpper方法在for循环构造器中用了两个变量来获得索引和切片元素。循环的形式防止在函数体中给p[i]中多次写值。

[练习：将ToUpper方法改变为用指针接收值，看看结果是否变化了]

[高级练习：口说梦话ToUpper方法改变为处理Unicode字符，而不只是ASCII]

容量

下面的函数通过传入一个元素扩展它的slice参数：

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

（为什么它需要返回一个已经修改过的slice呢？）现在运行它：

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

查看slice的值是怎么变化的。

是时候谈论切片头的第三个组件了：它的容量。除了数组指针和长度，切片头还存储它的容量：

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

在我们的例子中slice是通过下面的方式创建的：

slice := iBuffer[0:0]

它的头部像下面的样子：

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

Capacity字段和底层数组的长度减去slice的第一个元素的数组索引值是相等的（0在这种情况下存在）。如果你想探究一个slice的容量，使用cap函数：

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

Make方法

如果我们想增大分片，却超出分片本身的容量，怎么办呢？你不能这么做。根据分片的定义，容量限制了分片的增长。不过，你可以通过新创建一个数组，把分片数据拷贝到数组，然后修改分片使其指向新的数组而得到相同的结果。

让我们开始创建数组 。我们可以使用内置函数new来创建一个更大一点的数组，然后对所得的数组进行分片。不过实现这个更简单的方法是使用内置的make函数替代new函数。这个函数创建了一个新数组，然后创建了一个指向数组的分片头，所有这些一次完成。make函数使用了三个参数：分片类型，分片初始长度和make创建的用来保存分片数据的数组的长度，即分片容量。下面的调用创建了一个长度为10，且多余5个空间（10-15）的分片，运行它，你就会看到结果：

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

slice := make([]int, 10, 15)
fmt.Printf("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.Printf("len: %d, cap: %d\n", len(slice), cap(slice))

运行这段代码后，slice在需要重新分配之前拥有更多的增长空间。

当创建slices的时候，slice的长度和它的容量是相同的。通用情况下在make内置一个数组。参数的长度默认就是它的容量，所有你可以把它们设置为相同的值。

gophers := make([]Gopher, 10)

复制

当我们把上一节中的slice的容量扩大两倍的时候，我们写了一个循环把以前的数据复制到新的slice中。Go有一个内置的copy函数，使这个实现更加简单。它的参数有2个sclice，它把右边参数的数据复制到左边参数中来。下面是使用copy函数写的一个例子：

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

copy函数很好用。它只复制它能够复制的，请注意两个参数的长度。换句话说，它复制的元素数量是两个slice中长度最小的那个。这可以节省一点效率。另外，copy函数会返回一个整数值，代表复制元素的数量。尽管它并不值得时时去检测。

// Insert向分片的指定位置插入值,
// 位置必须在有效范围内.
// 分片必须有空间增加新元素.
func Insert(slice []int, index, value int) []int {
    // 给分片增加一个元素的空间.
    slice = slice[0 : len(slice)+1]
    //使用copy函数移动分片的前面部分，打开一个缺口.
    copy(slice[index+1:], slice[index:])
    // 存储新值.
    slice[index] = value
    // 返回结果
    return slice
}

上面的函数中有两点要注意。第一点当然是这个函数必须返回已经更新的分片，因为分片的长度已经更改。第二点是这个函数使用了很方便的简写。表达式

slice[i:]

slice[i:len(slice)]

slice[:]

就意味着整个分片，这在对整个数组进行分片时很有用。这个表达式是说明“指向整个数组元素的分片”：

array[:]

现在，所有的问题已经说明白了，让我们运行一下Insert函数。

slice := make([]int, 10, 20) //注意：容量要大于长度，这样才有空间增加新元素.
for i := range slice {
slice[i] = i
}
fmt.Println(slice)
slice = Insert(slice, 5, 99)
fmt.Println(slice)

Append：一个例子

在前面几节中，我们通过一个元素，写了一个扩展函数来扩展slice。尽管它有点问题，因为如果slice的容量太小的时候，这个函数就会崩溃。（我们内置的例子也有这个问题）。现在我们有方法来修复它，让我们为整数slices写一个健壮的实现。

func Extend(slice []int, element int) []int {
    n := len(slice)
    if n == cap(slice) {
        // Slice is full; must grow.
        // We double its size and add 1, so if the size is zero we still grow.
        newSlice := make([]int, len(slice), 2*len(slice)+1)
        copy(newSlice, slice)
        slice = newSlice
    }
    slice = slice[0 : n+1]
    slice[n] = element
    return slice
}

这种情况下，返回slice特别的重要，因为当重新分配结果slice的时候，描述了一个完全不同的数组。下面的一小片代码展示在slice填满的时候发生了什么。

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])
}

要注意到当初始化一个大小为5的一个数组时空间已经重新分配了。当新的数组被分配后，其容量和首元素地址都会改变。

在健壮的Extend函数的指导下我们可以写出一个更好的可以让我们按照多元素的方式扩展切片。为了能实现这个目标，我们用Go的特性将函数参数列表转换为一个切片。这就是我们运用了Go函数多变的技巧。

让我调用Append函数吧。在第一个版本中，我们可以只重复调用Extend来清除variadic函数机制。Append的签名方式如下：

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

有人说Append有一个参数，而一个切片拥有0个或者更多的整形参数。那些参数是一个整形切片并实现了Append所关注的，如下面的形式：

// 给切片追加元素
// 第一个版本：循环调用Extend
func Append(slice []int, items ...int) []int {
    for _, item := range items {
        slice = Extend(slice, item)
    }
    return slice
}

注意在参数列表元素中循环迭代的范围，它是隐式[]int类型。也要注意用了一个空白的标识_抛弃循环的索引，这个例子中我们不需要这个标识。

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

由于下面的原因，其中的Append函数也让我们很感兴趣。我们不仅仅可以用它来添加分片中的元素，而且还可以通过在调用处使用...符号给分片“激增”参数方法给分片增加第二个分片：

slice1 := []int{0, 1, 2, 3, 4}
slice2 := []int{55, 66, 77}
fmt.Println(slice1)
slice1 = Append(slice1, slice2...) //“...”很重要!
fmt.Println(slice1)

当然，我们还可以让Append更高效，在函数内部进行扩展，对其一次性分配足够的空间：

// Append给分片增加元素.
// 高效版本.
func Append(slice []int, elements ...int) []int {
    n := len(slice)
    total := len(slice) + len(elements)
    if total > cap(slice) {
        //重新分配空间，扩展为新给定大小的1.5倍，这样我们让然可以再对它进行扩展.
        newSize := total*3/2 + 1
        newSlice := make([]int, total, newSize)
        copy(newSlice, slice)
        slice = newSlice
    }
    slice = slice[:total]
    copy(slice[n:], elements)
    return slice
}

试试下面这段代码；它的执行结果与前面提到的那段代码相同：

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

Append：内置函数

至此，我们已经明白设计append内置函数的动机。这个内置函数所要做的确实如上面的Append例子那样，而且同样高效，不过它可对任何分片类型操作。

Go语言的一个弱点是任何泛类型的操作只有在运行时才能确定。终有一天这会得到更改，不过，迄今为止 ，为了更容易地对分片进行操作，Go语言必须给出内置的泛型append函数。它就像我们上面的int型分片那样运行，不过它针对的是任何分片类型。

记住：由于在调用append的时候总是更改了分片的头，因此你必须在调用之后保存返回的分片。事实上，如果没有保存返回结果的话，编译器是不会让你调用append的。

下面的几段混合有print语句。试试这几段代码，编辑，然后看看运行结果：

// 创建两个最初的分片.
slice := []int{1, 2, 3}
slice2 := []int{55, 66, 77}
fmt.Println("Start slice: ", slice)
fmt.Println("Start slice2:", slice2)

// 给一个分片添加元素.
slice = append(slice, 4)
fmt.Println("Add one item:", slice)

// 继续添加另一个分片.
slice = append(slice, slice2...)
fmt.Println("Add one slice:", slice)

// 拷贝(int型)分片.
slice3 := append([]int(nil), slice...)
fmt.Println("Copy a slice:", slice3)

// 把分片拷贝到自己的尾部.
fmt.Println("Before append to self:", slice)
slice = append(slice, slice...)
fmt.Println("After append to self:", slice)

在由社团构建的"分片使用技巧“维客页面里， 还有许多append、copy和其他使用分片方法的例子。

Nil

另外，发现这样一个知识点：我们要明白nil分片是如何表示的。很自然，它的分片头为零：

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

sliceHeader{}

array[0:0]

应当很清晰了，空分片可以增大（假设它又非零的容量），而nil分片没有存放元素值得数组，而且从不会为了存放元素而增长。

也就是说，nil分片功能上等同于零长度的分片，不同的是它不指向任何东西。它具有零长度，但可以给其分配空间，添加元素。就像上面例子里那样，你可以看看通过给nil分片添加而实现分片拷贝的那一段。

字符串

现在我们在介绍分片的这段中插入一段对Go语言字符串的简短介绍。

字符串实际上很简单：它只是Go语言在句法上有一点额外支持的只读的字节分片。

由于字符串是只读的，因此它没有容量（你就不能对它进行扩展），然而，在大多数情况下，你只要把它当作只读的字节片段看待。

对初学者来说，我们可以通过索引来访问某一个字节：

slash := "/usr/ken"[0] //生成字节值为'/'.

usr := "/usr/ken"[0:4] //生成字符串"/usr"

我们还可以多通常的字节分片进行操作，可以使用简单的转换由字节分片创建字符串：

str := string(slice)

slice := []byte(usr)

切片的一个重要结果就和给字串设计了求子字串函数一样的效果。所有要做的只是创建一个含有2个词的字串头。应为字串是只读的，原始字串和经过切片处理的字串可以共同安全的分享同一个数组。

经验之谈：最先实现的是字串的分配，但是当给语言添加切片时，它提供了一种有效处理字串的模式。从一些基准测试中可以看出它的速度是很快的。

关于字串还有很多，当然，这些只能放到另一篇文章里讲了。

结论

了解切片是如何工作的, 有助于了解他们是怎么实现的. 有一点数据结构，切片头，是与切片关联的项目，在开头也说了数组的独立分配.当我们传递切片值, 切片头会被复制一份，但它指向的数组是共享的.

一旦你明白它们是如何工作的，切片会非常简单易用, 但是功能强大,尤其是对于需要复制和附加的内置函数

更多阅读

有很多在网上找到关于Go语言分片的文章，正如前面提到的 "Slice Tricks"  有很多例子.关于 Go Slices的博客描述了内存布局图清晰的细节. Russ Cox's Go 数据结构 文章包括讨论分片以及一些其他的Go语言的的内部数据结构。.

还有更多的资料，但是最好的学习方式是使用它。

作者 Rob Pike