Arary & Slice

集合

集合是一个装载很多值的容器。
Go语言的集合有：数组(array)、映射(map)、切片(slice)、列表(list)

有序列表

数组是一种数据结构，是编程语言中最常见的有序列表。

考虑如下两组数据：

[1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]

这两个数据不是同一种数据含义。
其装载的值一致，但是值的顺序不一致。
有序列表，顺序不一致，数据含义就不同。

无序列表

考虑如下两组数据：

{
  name: "Tom",
  age: 12
}

{
  age: 12,
  name: "Tom"
}

键与键之间不存在顺序关联。
数据意义相同。

数组

基本形式

[1, 2, 3, 4, 5]

数组内部存储的值称为元素，元素在数组中的位置称为索引(从0开始)。

特点

数组的有序性：由索引来描述元素在数组中的位置。
数组的可遍历性：通过有序的特征，可以将元素按照索引顺序进行迭代。
数组的定长性：数组在声明定义时，必须指定长度。
数组的类型确定性：数组内部只能装载在定义时指定的类型的元素。
数组是靠长度来规范其是否能添加元素的。
数组必须先分配空间，再存储元素。

声明

数组的类型为：长度 + 元素类型([length]type)

package main

func main() {
  var numbers [3]int 

  numbers[0] = 1
  numbers[1] = 2
  numbers[2] = 3

  // invalid argument: index 3 out of bounds
  numbers[3] = 4
}

[3]表示一个长度为3的数组。
int数组可以存放元素的类型。
[3]int和[4]int是完全不同的类型。

默认值

string类型的默认值为空字符串""。
int类型的默认值为0。
bool类型的默认值false。

初始化

Go语言中，数组初始化有多种方式：

package main

import "fmt"

func main() {
  var arr [3]string
  arr[0] = "a"
  arr[1] = "b"
  arr[2] = "c"

  brr := [3]string{"a", "b", "c"}
  
  // 指定下标
  crr := [3]string{1: "a", 2: "b"}
  
  // 不明确长度的情况下推断长度
  drr := [...]string{"a", "b", "c", "d"}  
  
  fmt.Println(arr)
  fmt.Println(brr)
  fmt.Println(crr)
  fmt.Println(drr)
}

相等性

数组的相等性判断：

数组的元素类型要一致。
数组的长度要一致。
数组相同索引位置的值要一致。

package main

import "fmt"

func main() {
  var arr [2]string
  var brr [2]string
  
  arr[0] = "a"
  arr[1] = "b"
  brr[0] = "a"
  brr[1] = "b"
  fmt.Println(arr == brr) // true
  
  arr[0] = "a"
  arr[1] = "b"
  brr[0] = "b"
  brr[1] = "a"
  fmt.Println(arr == brr) // false
}

元素的类型和数组长度一致，就是一个类型，也就是说是否相等并不影响是否为同一个类型：

package main

import "fmt"

func main() {
  var arr [2]string
  var brr [2]string  

  arr[0] = "a"
  arr[1] = "b"
  brr[0] = "b"
  brr[1] = "a"  
  fmt.Println(arr == brr) // false  
  
  arr = brr
  fmt.Println(arr, brr) // [b a] [b a]
}

数组遍历

可通过for循环和for range来遍历数组：

package main

import "fmt"

func main() {
  var arr [3]string  
  arr[0] = "a"
  arr[1] = "b"
  arr[2] = "c"  

  for i := 0; i < len(arr); i++ {
    fmt.Println(arr[i])
  }  
  
  for _, el := range arr {
    fmt.Println(el)
  }
}

二维数组

二维数组可通过[行数][列数]类型的形式来定义：

//         [行数]  [列数]  类型
// var arr  [3]    [4]   string

package main

import "fmt"

func main() {
  var arr [2][4]string  
  arr[0] = [4]string{"HTML", "CSS", "JavaScript", "Node.js"}
  arr[1] = [4]string{"Java", "Python", "C++", "Golang"}  

  for i := 0; i < len(arr); i++ {
    for j := 0; j < len(arr[i]); j++ {
      fmt.Print(arr[i][j] + " ")
    }
    fmt.Println()
  }

  for _, rowEl := range arr {
    for _, colEl := range rowEl {
      fmt.Print(colEl + " ")
    }
    fmt.Println()
  }
}

杨辉三角

var arr [10][]int

for i := 0; i < len(arr); i++ {
  arr[i] = make([]int, i+1)
  arr[i][0] = 1
  arr[i][i] = 1
  for j := 1; j < len(arr[i])-1; j++ {
    arr[i][j] = arr[i-1][j-1] + arr[i-1][j]
  }
}

for i := 0; i < len(arr); i++ {
  for j := 0; j < (len(arr)-(i+1))*2; j++ {
    fmt.Print(" ")
  }
  for k := 0; k < len(arr[i]); k++ {
    fmt.Print(strconv.Itoa(arr[i][k]) + "   ")
  }
  fmt.Println()
}

切片

切片的本质是动态数组，声明一个切片就是声明一个默认长度为0的数组。
声明切片时，长度不可设置，如果设置了长度会认为是一个数组。
切片的底层是基于数组实现的。
切片进行长度扩容后，再进行存储。

var sliceArr []string

`append`

切片需要使用append进行元素的追加。
append是一个全局方法，并返回新的引用，必须赋值给一个变量。
append会返回一个新的切片，新切片必须赋值给原切片变量，才能做到增加元素。

package main

import "fmt"

func main() {
  var sliceArr []string
  sliceArr = append(sliceArr, "a", "bc", "d")
  fmt.Println(sliceArr)
}

切片比较

切片之间不能进行比较，只能和nil进行比较：

package main

import "fmt"

func main() {
  var sliceArr1 []string
  var sliceArr2 []string  

  // slice can only be compared to nil
  fmt.Println(sliceArr1 == sliceArr2)

  fmt.Println(sliceArr1 == nil) // true
}

初始化

默认长度为0的数组。

package main

func main() {
  var sliceArr []string
  sliceArr = append(sliceArr, "a", "b")
}

定义切片的初始化。

package main

import "fmt"

func main() {
  sliceArr := []string{"a", "b", "c"}
  fmt.Println(sliceArr)
}

make方法初始化存储空间。通过make分配切片的存储空间来指定默认的长度，由于切片需要扩充空间，如果先知道需要存入多少个元素，那么就先指定多少空间，会使得扩容次数变少。

package main

import "fmt"

func main() {
  sliceArr := make([]string, 2)

  sliceArr[0] = "a"
  sliceArr[1] = "b"

  sliceArr = append(sliceArr, "c", "d")  
  fmt.Println(sliceArr)
}

访问元素

可通过[]来访问元素。

package main

import "fmt"

func main() {
  sliceArr := []string{"a", "b", "c"}
  fmt.Println(sliceArr[0]) // a
}

截取元素

截取部分slice[start:end]，从索引start开始，到索引end结束，但不包含end。

package main

import "fmt"

func main() {
  sliceArr := []string{"a", "b", "c", "e", "f", "g"}
  sliceArr1 := sliceArr[1:4]
  fmt.Println(sliceArr1) // [b c e]
}

截取全部slice[0:len(slice)]或者slice[0:]。

package main

import "fmt"

func main() {
  sliceArr := []string{"a", "b", "c", "e", "f", "g"}
  sliceArr1 := sliceArr[0:len(sliceArr)]
  fmt.Println(sliceArr1)
}

如果没有指定end，默认截取到末尾。

package main

import "fmt"

func main() {
  sliceArr := []string{"a", "b", "c", "e", "f", "g"}
  sliceArr1 := sliceArr[1:]
  fmt.Println(sliceArr1) // [b c e f g]
}

如果没有指定start，默认头开始截取。

package main

import "fmt"

func main() {
  sliceArr := []string{"a", "b", "c", "e", "f", "g"}
  sliceArr1 := sliceArr[:3]
  fmt.Println(sliceArr1) // [a b c]
}

如果既没有指定start，也没有指定end，则截取全部。

package main

import "fmt"

func main() {
  sliceArr := []string{"a", "b", "c", "e", "f", "g"}
  sliceArr1 := sliceArr[:]
  fmt.Println(sliceArr1) // [a b c e f g]
}

截取后返回的新的切片变量与原切片是同一个引用，后续的操作会互相影响。

package main

import "fmt"

func main() {
  sliceArr := []string{"a", "b", "c", "e", "f", "g"}
  sliceArr1 := sliceArr[1:4]
  sliceArr1[0] = "aa"
  fmt.Println(sliceArr1) // [aa c e]
  fmt.Println(sliceArr)  // [a aa c e f g]
}

遍历元素

可使用 for 和 for...range 进行切片的遍历：

package main

import "fmt"

func main() {
  sliceArr := []int{1, 2, 3, 4, 5}  

  for i := 0; i < len(sliceArr); i++ {
    fmt.Println(sliceArr[i])
  }  

  for index, el := range sliceArr {
    fmt.Println(index, el)
  }
}

for...range 在值类型上迭代的是副本，因此对循环变量的修改不会改变原始切片。如果需要在迭代期间修改切片元素，请使用基于索引的循环，这可以通过索引直接访问每个元素。

slice := []int{1, 2, 3} 

for _, val := range slice {
  // value is copy
    val *= 2 
}
// slice -> [1 2 3]

for i := range slice {
    // modifies the element in place
    slice[i] *= 2
}
// slice -> [2 4 6]

添加元素

可通过append全局方法对切片进行元素的添加：

package main

import "fmt"

func main() {
  var classSlice []string  

  classSlice = append(classSlice, "张三", "李四", "王五") 

  studentSlice := make([]string, 3)
  studentSlice[0] = "小红"
  studentSlice[1] = "小刚"
  studentSlice[2] = "小王"  

  for i := 0; i < len(studentSlice); i++ {
    classSlice = append(classSlice, studentSlice[i])
  }  

  fmt.Println(classSlice)
}

省略号操作

如上的for循环可使用...语法代替，语法更简洁：

package main

import "fmt"

func main() {
  var classSlice []string  

  classSlice = append(classSlice, "张三", "李四", "王五")  

  studentSlice := make([]string, 3)
  studentSlice[0] = "小红"
  studentSlice[1] = "小刚"
  studentSlice[2] = "小王"  

  classSlice = append(classSlice, studentSlice...)

  fmt.Println(classSlice)
}

删除元素

Go语言没有提供直接的切片元素删除方法，需要通过截取和append方法间接地实现：

package main

import "fmt"

func main() {
  sliceArr := []string{"张三", "李四", "王五", "小刚", "小王"}  

  // 删除第一个
  sliceArr = sliceArr[1:]  

  // 删除最后一个
  sliceArr = sliceArr[:len(sliceArr)-1]  

  // 删除 "王五" "小刚"
  sliceArr = append(sliceArr[:2], sliceArr[4:]...)  

  // 删除全部
  sliceArr = []string{}

  fmt.Println(sliceArr)
}

拷贝元素

切片拷贝可通过内置的copy方法完成，返回拷贝切片元素的长度。
copy方法不会自动扩充切片。
拷贝与被拷贝的切片是两个不同的切片引用，互不影响。

package main

import "fmt"

func main() {
  src := []string{"张三", "李四", "王五", "小刚", "小王"}
  dst := make([]string, len(src))  

  res := copy(dst, src)
  
  fmt.Println(res)
}

值与引用

值传递：对值进行拷贝，然后传递。
引用传递：传递值的地址，共享同一数据。

值与引用

package main

import "fmt"

func setIntSlice(intSlice []int) {
  intSlice[2] = 3
}

func setA(a int) {
  a = 2
}

func main() {
  intSlice := make([]int, 3, 3)
  intSlice[0] = 1
  intSlice[1] = 2

  // 逻辑上是引用传递，底层不完全是
  setIntSlice(intSlice)  

  a := 1
  setA(a)  

  fmt.Println(a)        // 1
  fmt.Println(intSlice) // [1 2 3]
}

存储原理

`slice`结构体

Go语言的底层存在slice类型。
unsafe.Pointer是不受类型系统约束、可以做任何指向的指针。
array是一个指针，指向了一片连续存储空间的起点地址。
通过len确定slice有多少元素可以存储。
通过cap来确定还有多少个空间可以存储元素。

slice存储

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

切片

切片存储在连续内存地址的空间。
其元素索引值对元素进行规范(偏移长度确定元素位置)。
切片的长度和容量可变化。
容量需要根据元素的数量扩充(动态扩容)。

引用传递

在作为参数传递时，传递的是slice结构体的拷贝，起始地址一致，但无法无法操作len和cap：

package main

import "fmt"

func setIntSlice(intSlice []int) {
  /*
    intSlice {
      array 0x001
      len 4
      cap 6
    }
  */
  intSlice = append(intSlice, 4)
  fmt.Println(intSlice) // [0 0 0 4]
}

func main() {
  intSlice := make([]int, 3, 3)
  /*
    传递 slice 结构体的拷贝
    intSlice {
      array 0x001
      len 3
      cap 3
    }
  */
  setIntSlice(intSlice)
  fmt.Println(intSlice) // [0 0 0]
}

长度与容量

对于切片来说，长度是当前存储的元素的实际个数，而容量是最大可存储的元素个数。

package main

import "fmt"

func main() {
  sliceArr := make([]int, 3, 5)  

  for i := 0; i < len(sliceArr); i++ {
    sliceArr[i] = i
  }  

  fmt.Println(sliceArr)      // [0 1 2]
  fmt.Println(len(sliceArr)) // 3
  fmt.Println(cap(sliceArr)) // 5
}

在未指定容量的情况下，切片的容量与切片长度相等：

package main

import "fmt"

func main() {
 intSlice := []int{1, 2, 3}
 // 3, 3
 fmt.Printf("%d, %d\r\n", len(intSlice), cap(intSlice))
}

切片截取是通过len决定元素的个数，而容量是从起始索引到底层数组的末尾，长度不能决定容量：

package main

import "fmt"

func main() {
  intSlice := []int{1, 2, 3, 4, 5}
  tmpSlice1 := intSlice[1:3]
  tmpSlice2 := intSlice[0:2]
  
  fmt.Println(cap(tmpSlice1)) // 4
  fmt.Println(cap(tmpSlice2)) // 5
}

切片扩容

当向一个切片中添加元素时，如果切片的容量不足，Go语言会自动扩充切片的容量，如果切片的容量足以容纳新的元素，则不会引起扩容。

如果没有引起扩容，将返回原切片的引用：

不扩容

如果引起了扩容，那么将重新分配内存空间，并存储元素，最终返回新切片的引用：

开辟一个新的切片连续空间。
将原有空间的元素移动到新的空间。
通过append返回一个新的切片引用。

扩容为什么要开辟新的连续空间?

原有的连续空间不能保证后续的预扩容空间内没有其它值的存储，所以Go语言重新选择开辟一个预容量的连续空间来达到扩容目的。

切片的扩充会导致底层数组的重新分配，因此可能会产生额外的性能开销。因此，在创建切片时，尽量预估好切片的容量，以减少扩充的次数。

扩容策略

1.17版本

当新切片所需的容量大于2倍扩容的容量，则按照新切片所需的容量扩容。
当原切片的容量小于1024时，新切片的容量变成原切片的2倍。
当原切片的容量大于1024时，进入一个循环，每次新切片容量变成原切片的1.25倍，直到满足期望容量。

1.18版本

以256为临界点(threshold):

当新切片所需的容量大于2倍扩容的容量，则按照新切片所需的容量扩容。
当原切片的容量小于临界点时，新切片的容量变成原切片的2倍。
当原切片的容量大于临界点时，进入一个循环，每次容量增加(oldCap + 3 * threshold) / 4。

考虑如下代码，共进行了几次扩容，最终的容量是多少？

package main

import "fmt"

func main() {
  var intSlice []int  

  for i := 0; i < 5; i++ {
    // 1 -> 2 -> 4 -> 8
    intSlice = append(intSlice, i)
  }  

  fmt.Println(cap(intSlice)) // 8
}

截取原理

截取是对空间起始位置的重新指定，并通过len决定具体的元素及个数，在原始切片上进行再切割后的结果。

截取并不是重新开辟新的空间存储对应元素，而是复用原有的内存空间，在一定程度上节省了开销。

截取原理

删除原理

通过append删除元素时，新切片的len和cap已提前计算好，并依次遍历元素添加：

package main

import "fmt"

func main() {
  intSlice := []int{1, 2, 3, 4, 5}
  newIntSlice := append(intSlice[:2], intSlice[3:]...)
  fmt.Println(intSlice)    // [1 2 4 5 5]
  fmt.Println(newIntSlice) // [1 2 4 5]
}

在追加元素时，intSlice[:2]的起始地址为intSlice的第一个元素，len为2，由于内存地址一致，因此在追加元素时，会覆盖原有切片对应位置的元素。

删除原理

nil slice

nil 切片有 nil 的数组指针，而空切片是已初始化的非 nil 指针并且为 0 的切片。

var nilSlice []int                 // -> nil
emptySliceMake := make([]int, 0)   // -> []
emptySliceLiteral := []int{}       // -> []

// nilSlice == nil -> true
// emptySliceMake == nil -> false
// emptySliceLiteral == nil -> false
// len(nilSlice) -> 0

内存泄露

从大切片创建的小切片可以将整个大数组保留在内存中：

func getLargeSlice() []int {
    largeSlice := make([]int, 1_000_000)
    return largeSlice
}

// slice of 1,000,000 ints
largeData := getLargeSlice()
// slice with length=10, cap=999,990
smallSlice := largeData[10:20]

// Setting largeData to nil does not free the large array,
// because smallSlice still references it.
largeData = nil

为了避免内存泄漏，将小切片的数据复制到一个新的独立切片中。这使得如果大型底层数组不再被其他地方引用，可以被垃圾回收。

largeData := getLargeSlice()
// references big array
subset := largeData[10:20]           
// new small array
smallSlice := make([]int, len(subset)) 
copy(smallSlice, subset)               

largeData = nil

切片重叠

当使用 copy 函数时，源切片和目标切片如果有重叠区域，copy 的行为是未定义的，可能导致意外的结果。

data := []int{1, 2, 3, 4, 5} // -> [1 2 3 4 5]
src := data[:]               // -> [1 2 3 4 5]
dst := data[2:]              // -> overlap (dst starts at index 2): [3 4 5]

// Copy from src to dst
copy(dst, src)

// Expected output: data -> [1 2 3 4 5] (if copied correctly)
// Actual output: data -> [1 2 1 2 3] (corrupted)

为了避免数据破坏，最好避免切片重叠，或者使用临时切片来完成操作，确保源切片和目标切片不会同时操作相同的内存区域。

静默截断

copy 会返回复制的元素数量，该数量是 len(dst) 和 len(src) 中较小的值。如果 dst 较短，数据会被截断。

src := []int{1, 2, 3, 4, 5}  // -> [1 2 3 4 5]
dst := make([]int, 3)        // -> [0 0 0] (length 3)

copied := copy(dst, src)

// Expected output: dst -> [1 2 3 4 5], copied -> 5
// Real output:     dst -> [1 2 3], copied -> 3

集合​

有序列表​

无序列表​

数组​

基本形式​

特点​

声明​

默认值​

初始化​

相等性​

数组遍历​

二维数组​

杨辉三角​

切片​

append​

切片比较​

初始化​

访问元素​

截取元素​

遍历元素​

添加元素​

省略号操作​

删除元素​

拷贝元素​

值与引用​

存储原理​

slice结构体​

切片​

引用传递​

长度与容量​

切片扩容​

扩容策略​

1.17版本​

1.18版本​

截取原理​

删除原理​

nil slice​

内存泄露​

切片重叠​

静默截断​

集合

有序列表

无序列表

数组

基本形式

特点

声明

默认值

初始化

相等性

数组遍历

二维数组

杨辉三角

切片

`append`

切片比较

初始化

访问元素

截取元素

遍历元素

添加元素

省略号操作

删除元素

拷贝元素

值与引用

存储原理

`slice`结构体

切片

引用传递

长度与容量

切片扩容

扩容策略

1.17版本

1.18版本

截取原理

删除原理

nil slice

内存泄露

切片重叠

静默截断