因为数组大小是固定的,当数据元素特别多时,固定的数组无法储存这么多的值,所以可变长数组出现了,这也是一种数据结构。在 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
  2. import "fmt"
  3. func main() {
  4. // 创建一个容量为2的切片
  5. array := make([]int, 0, 2)
  6. fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  7. // 虽然 append 但是没有赋予原来的变量 array
  8. _ = append(array, 1)
  9. fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  10. _ = append(array, 1)
  11. fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  12. _ = append(array, 1)
  13. fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  14. fmt.Println("-------")
  15. // 赋予回原来的变量
  16. array = append(array, 1)
  17. fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  18. array = append(array, 1)
  19. fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  20. array = append(array, 1)
  21. fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  22. array = append(array, 1, 1, 1, 1)
  23. fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  24. array = append(array, 1, 1, 1, 1, 1, 1, 1, 1, 1)
  25. fmt.Println("cap", cap(array), "len", len(array), "array:", array)
  26. }

输出:

  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. )
  4. // 可变长数组
  5. type Array struct {
  6. array []int // 固定大小的数组,用满容量和满大小的切片来代替
  7. len int // 真正长度
  8. cap int // 容量
  9. lock sync.Mutex // 为了并发安全使用的锁
  10. }

1.1. 初始化数组

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

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

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

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

1.2. 添加元素

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

首先添加一个元素到可变长数组里,会加锁,这样会保证并发安全。然后将值放在数组里: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. // 增加多个元素
  2. func (a *Array) AppendMany(element ...int) {
  3. for _, v := range element {
  4. a.Append(v)
  5. }
  6. }

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

1.3. 获取指定下标元素

  1. // 获取某个下标的元素
  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. // 返回真实长度
  2. func (a *Array) Len() int {
  3. return a.len
  4. }
  5. // 返回容量
  6. func (a *Array) Cap() int {
  7. return a.cap
  8. }

时间复杂度为 O(1)

1.5. 示例

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

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

将打印出:

  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 自动提供了这一数据类型:切片(可变长数组)。大家一般开发过程中,直接使用这一类型即可。