Go 系列数据结构-slice

Slice又称动态数组，依托数组实现，可以方便的进行扩容、传递等，实际使用中比数组更灵活。

正因为灵活，如果不了解其内部实现机制，有可能遭遇莫名的异常现象。

实例

题目一

下面程序输出什么？

package main 
import ( 
  "fmt" 
) 

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

  fmt.Println("lenth of slice: ", len(slice)) 
  fmt.Println("capacity of slice: ", cap(slice)) 
  fmt.Println(&slice[0] == &array[5]) 
}

程序解释：main 函数中定义了一个 10 个长度的整型数组 array，然后定义了一个切片 slice，切取数组的第 6 个元素，最后打印 slice 的长度和容量，判断切片的第一个元素和数组的第 6 个元素地址是否相等。

参考答案：slice 跟据数组 array 创建，与数组共享存储空间，slice 起始位置是 array[5]，长度为 1，容量为 5， slice[0]和 array[5] 地址相同。

题目二

下面程序输出什么？

package main
import (
  "fmt"
)

func AddElement(slice []int, e int) []int { 
  return append(slice, e) 
}

func main() { 
  var slice []int 

  slice = append(slice, 1, 2, 3) 
  
  newSlice := AddElement(slice, 4) 
  
  fmt.Println(&slice[0] == &newSlice[0]) 
}

程序解释：函数 AddElement() 接受一个切片和一个元素，把元素 append 进切片中，并返回切片。main()函数中定义一个切片，并向切片中 append 3 个元素，接着调用 AddElement() 继续向切片 append 进第 4 个元素同时定义一个新的切片 newSlice。最后判断新切片 newSlice 与旧切片 slice 是否共用一块存储空间。

参考答案：append 函数执行时会判断切片容量是否能够存放新增元素，如果不能，则会重新申请存储空间，新存储空间将是原来的 2 倍或 1.25 倍（取决于扩展原空间大小），本例中实际执行了两次 append 操作，第一次空间增长到 4，所以第二次 append 不会再扩容，所以新旧两个切片将共用一块存储空间。程序会输出 ”true”。

题目三

下面程序由Golang源码改编而来，程序输出什么？

package main 
import ( 
  "fmt" 
) 

func main() { 
  orderLen := 5 
  order := make([]uint16, 2 * orderLen) 
  pollorder := order[:orderLen:orderLen] 
  lockorder := order[orderLen:][:orderLen:orderLen] 
  
  fmt.Println("len(pollorder) = ", len(pollorder)) 
  fmt.Println("cap(pollorder) = ", cap(pollorder)) 
  fmt.Println("len(lockorder) = ", len(lockorder)) 
  fmt.Println("cap(lockorder) = ", cap(lockorder)) 
}

程序解释：该段程序源自 select 的实现代码，程序中定义一个长度为 10 的切片 order，pollorder 和 lockorder 分别是对order 切片做了 order[low:high:max]操作生成的切片，最后程序分别打印pollorder和lockorder的容量和长度。

参考答案：order[low:high:max]操作意思是对order进行切片，新切片范围是[low, high),新切片容量是 max。order长度为2倍的orderLen，pollorder切片指的是order的前半部分切片，lockorder指的是order的后半部分切片，即原order分成了两段。所以，pollorder和lockerorder的长度和容量都是orderLen，即5。

Slice实现原理

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

Slice数据结构

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

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

从数据结构看 Slice 很清晰, array 指针指向底层数组，len 表示切片长度，cap 表示底层数组容量。

使用make创建Slice

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

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

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

使用数组创建Slice

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

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

切片从数组array[5]开始，到数组array[7]结束（不含array[7]），即切片长度为2，数组后面的内容都作为切片的预留内存，即capacity为 5。

数组和切片操作可能作用于同一块内存，这也是使用过程中需要注意的地方。

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 倍；

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

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

Slice Copy

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

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

也就是说，copy 过程中不会发生扩容。

特殊切片

跟据数组或切片生成新的切片一般使用 slice := array[start:end] 方式，这种新生成的切片并没有指定切片的容量，实际上新切片的容量是从start开始直至array的结束。

比如下面两个切片，长度和容量都是一致的，使用共同的内存地址：

sliceA := make([]int, 5, 10) 
sliceB := sliceA[0:5]

根据数组或切片生成切片还有另一种写法，即切片同时也指定容量，即slice[start:end:cap], 其中 cap 即为新切片的容量，当然容量不能超过原切片实际值，如下所示：

sliceA := make([]int, 5, 10) //length = 5; capacity = 10 
sliceB := sliceA[0:5] //length = 5; capacity = 10 
sliceC := sliceA[0:5:5] //length = 5; capacity = 5 

这切片方法不常见，在 Golang 源码里能够见到，不过非常利于切片的理解。

编程Tips

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

Slice总结

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

实例

题目一

题目二

题目三