可变长数组

因为数组大小是固定的，当数据元素特别多时，固定的数组无法储存这么多的值，所以可变长数组出现了，这也是一种数据结构。在 Golang语言中，可变长数组被内置在语言里面：切片 slice。

slice 是对底层数组的抽象和控制。它是一个结构体：

  1. type slice struct {
  2.     array unsafe.Pointer
  3.     len   int
  4.     cap   int
  5. }
  1. 指向底层数组的指针。( Golang 语言是没有操作原始内存的指针的，所以 unsafe 包提供相关的对内存指针的操作，一般情况下非专业人员勿用)
  2. 切片的真正长度，也就是实际元素占用的大小。
  3. 切片的容量，底层固定数组的长度。

每次可以初始化一个固定容量的切片，切片内部维护一个固定大小的数组。当 append 新元素时，固定大小的数组不够时会自动扩容，如：

  1. package main
  3. import "fmt"
  5. func main() {
  6.     // 创建一个容量为2的切片
  7.     array := make([]int, 0, 2)
  8.     fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  10.     // 虽然 append 但是没有赋予原来的变量 array
  11.     _ = append(array, 1)
  12.     fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  13.     _ = append(array, 1)
  14.     fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  15.     _ = append(array, 1)
  16.     fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  18.     fmt.Println("-------")
  20.     // 赋予回原来的变量
  21.     array = append(array, 1)
  22.     fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  23.     array = append(array, 1)
  24.     fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  25.     array = append(array, 1)
  26.     fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  27.     array = append(array, 1, 1, 1, 1)
  28.     fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  29.     array = append(array, 1, 1, 1, 1, 1, 1, 1, 1, 1)
  30.     fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  31. }

输出：

  1. cap 2 len 0 array: []
  2. cap 2 len 0 array: []
  3. cap 2 len 0 array: []
  4. cap 2 len 0 array: []
  5. -------
  6. cap 2 len 1 array: [1]
  7. cap 2 len 2 array: [1 1]
  8. cap 4 len 3 array: [1 1 1]
  9. cap 8 len 7 array: [1 1 1 1 1 1 1]
  10. cap 16 len 16 array: [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]

我们可以看到 Golang 的切片无法原地 append，每次添加元素时返回新的引用地址，必须把该引用重新赋予之前的切片变量。并且，当容量不够时，会自动倍数递增扩容。事实上，Golang 在切片长度大于 1024 后，会以接近于 1.25 倍进行容量扩容。

具体可参考标准库 runtime 下的 slice.go 文件。

一、实现可变长数组

我们来实现一个简单的，存放整数的，可变长的数组版本。

因为 Golang 的限制，不允许使用 [n]int 来创建一个固定大小为 n 的整数数组，只允许使用常量来创建大小。

所以我们这里会使用切片的部分功能来代替数组，虽然切片本身是可变长数组，但是我们不会用到它的 append 功能，只把它当数组用。

  1. import (
  2.     "sync"
  3. )
  5. // Array 可变长数组
  6. type Array struct {
  7.     array []int      // 固定大小的数组，用满容量和满大小的切片来代替
  8.     len   int        // 真正长度
  9.     cap   int        // 容量
  10.     lock  sync.Mutex // 为了并发安全使用的锁
  11. }

1.1. 初始化数组

创建一个 len 个元素，容量为 cap 的可变长数组：

  1. // Make 新建一个可变长数组
  2. func Make(len, cap int) *Array {
  3.     s := new(Array)
  4.     if len > cap {
  5.         panic("len large than cap")
  6.     }
  8.     // 把切片当数组用
  9.     array := make([]int, cap, cap)
  11.     // 元数据
  12.     s.array = array
  13.     s.cap = cap
  14.     s.len = 0
  15.     return s
  16. }

主要利用满容量和满大小的切片来充当固定数组，结构体 Array 里面的字段 len 和 cap 来控制值的存取。不允许设置 len > cap 的可变长数组。

时间复杂度为：O(1)，因为分配内存空间和设置几个值是常数时间。

1.2. 添加元素

  1. // Append 增加一个元素
  2. func (a *Array) Append(element int) {
  3.     // 并发锁
  4.     a.lock.Lock()
  5.     defer a.lock.Unlock()
  7.     // 大小等于容量，表示没多余位置了
  8.     if a.len == a.cap {
  9.         // 没容量，数组要扩容，扩容到两倍
  10.         newCap := 2 * a.len
  12.         // 如果之前的容量为0，那么新容量为1
  13.         if a.cap == 0 {
  14.             newCap = 1
  15.         }
  17.         newArray := make([]int, newCap, newCap)
  19.         // 把老数组的数据移动到新数组
  20.         for k, v := range a.array {
  21.             newArray[k] = v
  22.         }
  24.         // 替换数组
  25.         a.array = newArray
  26.         a.cap = newCap
  28.     }
  30.     // 把元素放在数组里
  31.     a.array[a.len] = element
  32.     // 真实长度+1
  33.     a.len = a.len + 1
  35. }

首先添加一个元素到可变长数组里，会加锁，这样会保证并发安全。然后将值放在数组里：a.array[a.len] = element，然后 len + 1，表示真实大小又多了一个。

当真实大小 len = cap 时，表明位置都用完了，没有多余的空间放新值，那么会创建一个固定大小 2*len 的新数组来替换老数组：a.array = newArray，当然容量也会变大：a.cap = newCap。如果一开始设置的容量 cap = 0，那么新的容量会是从 1 开始。

添加元素中，耗时主要在老数组中的数据移动到新数组，时间复杂度为：O(n)。当然，如果容量够的情况下，时间复杂度会变为：O(1)。

如何添加多个元素：

  1. // AppendMany 增加多个元素
  2. func (a *Array) AppendMany(element ...int) {
  3.     for _, v := range element {
  4.         a.Append(v)
  5.     }
  6. }

只是简单遍历一下，调用 Append 函数。其中 ...int 是 Golang 的语言特征，表示多个函数变量。

1.3. 获取指定下标元素

  1. // Get 获取某个下标的元素
  2. func (a *Array) Get(index int) int {
  3.     // 越界了
  4.     if a.len == 0 || index >= a.len {
  5.         panic("index over len")
  6.     }
  7.     return a.array[index]
  8. }

当可变长数组的真实大小为0，或者下标 index 超出了真实长度 len ，将会 panic 越界。

因为只获取下标的值，所以时间复杂度为 O(1)。

1.4. 获取真实长度和容量

  1. // Len 返回真实长度
  2. func (a *Array) Len() int {
  3.     return a.len
  4. }
  6. // Cap 返回容量
  7. func (a *Array) Cap() int {
  8.     return a.cap
  9. }

时间复杂度为 O(1)。

1.5. 示例

现在我们来运行完整的可变长数组的例子：

  1. package main
  3. import (
  4.     "fmt"
  5.     "sync"
  6. )
  8. // Array 可变长数组
  9. type Array struct {
  10.     array []int      // 固定大小的数组，用满容量和满大小的切片来代替
  11.     len   int        // 真正长度
  12.     cap   int        // 容量
  13.     lock  sync.Mutex // 为了并发安全使用的锁
  14. }
  16. // Make 新建一个可变长数组
  17. func Make(len, cap int) *Array {
  18.     s := new(Array)
  19.     if len > cap {
  20.         panic("len large than cap")
  21.     }
  23.     // 把切片当数组用
  24.     array := make([]int, cap, cap)
  26.     // 元数据
  27.     s.array = array
  28.     s.cap = cap
  29.     s.len = 0
  30.     return s
  31. }
  33. // Append 增加一个元素
  34. func (a *Array) Append(element int) {
  35.     // 并发锁
  36.     a.lock.Lock()
  37.     defer a.lock.Unlock()
  39.     // 大小等于容量，表示没多余位置了
  40.     if a.len == a.cap {
  41.         // 没容量，数组要扩容，扩容到两倍
  42.         newCap := 2 * a.len
  44.         // 如果之前的容量为0，那么新容量为1
  45.         if a.cap == 0 {
  46.             newCap = 1
  47.         }
  49.         newArray := make([]int, newCap, newCap)
  51.         // 把老数组的数据移动到新数组
  52.         for k, v := range a.array {
  53.             newArray[k] = v
  54.         }
  56.         // 替换数组
  57.         a.array = newArray
  58.         a.cap = newCap
  60.     }
  62.     // 把元素放在数组里
  63.     a.array[a.len] = element
  64.     // 真实长度+1
  65.     a.len = a.len + 1
  67. }
  69. // AppendMany 增加多个元素
  70. func (a *Array) AppendMany(element ...int) {
  71.     for _, v := range element {
  72.         a.Append(v)
  73.     }
  75. }
  77. // Get 获取某个下标的元素
  78. func (a *Array) Get(index int) int {
  79.     // 越界了
  80.     if a.len == 0 || index >= a.len {
  81.         panic("index over len")
  82.     }
  83.     return a.array[index]
  84. }
  86. // Len 返回真实长度
  87. func (a *Array) Len() int {
  88.     return a.len
  89. }
  91. // Cap 返回容量
  92. func (a *Array) Cap() int {
  93.     return a.cap
  94. }
  96. // Print 辅助打印
  97. func Print(array *Array) (result string) {
  98.     result = "["
  99.     for i := 0; i < array.Len(); i++ {
  100.         // 第一个元素
  101.         if i == 0 {
  102.             result = fmt.Sprintf("%s%d", result, array.Get(i))
  103.             continue
  104.         }
  106.         result = fmt.Sprintf("%s %d", result, array.Get(i))
  107.     }
  108.     result = result + "]"
  109.     return
  110. }
  112. func main() {
  113.     // 创建一个容量为3的动态数组
  114.     a := Make(0, 3)
  115.     fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", Print(a))
  117.     // 增加一个元素
  118.     a.Append(10)
  119.     fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", Print(a))
  121.     // 增加一个元素
  122.     a.Append(9)
  123.     fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", Print(a))
  125.     // 增加多个元素
  126.     a.AppendMany(8, 7)
  127.     fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", Print(a))
  128. }

将打印出：

  1. cap 3 len 0 array: []
  2. cap 3 len 1 array: [10]
  3. cap 3 len 2 array: [10 9]
  4. cap 6 len 4 array: [10 9 8 7]

可以看到，容量会自动翻倍。

二、总结

可变长数组在实际开发上，经常会使用到，其在固定大小数组的基础上，会自动进行容量扩展。

因为这一数据结构的使用频率太高了，所以，Golang 自动提供了这一数据类型：切片（可变长数组）。大家一般开发过程中，直接使用这一类型即可。

附录

代码下载： https://github.com/hunterhug/goa.c/blob/master/code/slice/slice_example.go 。