Go 数组和切片
Contents
TL;DR
数组不是引用类型，数组长度必须是常量表达式，数组的长度是数组类型的一部分。
切片并不直接拥有它指向的底层数组的元素，但切片的指针、长度和容量是和切片直接绑定的一部分，3 个中的任何一个发生变化都需要对切片变量进行重新赋值。
切片是“引用类型”，切片只能和 nil 比较，不能相互比较。
由于切片内部包含一个指向它能访问的底层数据的第一个元素的指针，当切片作为函数参数传递时，函数内部也可以通过访问切片副本的指针来修改底层数组的元素（引用传递）。拷贝一个切片实际上是为底层数组创建了一个别名。
切片字面量没有指定长度，它会自动创建合适大小的底层数组变量，并生成一个指向它的切片。
切片的容量通常是切片的第一个元素到底层数组的最后一个元素之间元素的个数。
切片的零值是 nil。nil 切片没有底层数组，长度和容量都为 0。非 nil 的切片的长度和容量也可以为 0，如 []int{}，make([]int, 3)[3:]。判断切片是否为空要用 len(s) == 0，而不是 s == nil。
数组、切片的索引可以是字符。
https://go.dev/play/p/sOhkuwVCTM3
数组
数组是包含固定个数（0 个或多个）的相同类型元素的序列。
len 方法返回数组元素的个数。
数组元素的初始值被设置成元素类型的零值。
可以用数组字面量（array literal）初始化数组。
字面量中的省略号表示数组长度由初始化变量的个数决定。
可以用同时指定下标和值的方式初始化数组，此时可以以任意顺序初始化，也可以不去初始化部分元素。
var a [3]int // array of 3 integers
var q [3]int = [3]int{1, 2, 3}
var r [3]int = [3]int{1, 2}
fmt.Println(r[2]) // 0
s := [...]int{1, 2, 3}
type Currency int
const (
USD Currency = iota
EUR
GBP
RMB
)
symbol := [...]string{RMB: "￥", USD: "$"}
数组的长度是数组类型的一部分，所以 [3]int 和 [4]int 是不同的类型。
数组的长度必须是一个常量表达式，即它的值在程序编译的时候要能够计算出来。
若数组元素的类型是可比较的，则该类型的数组也是可比较的，此时可以直接用 == 比较相同类型的两个数组。若比较结果相等，则表示里面的所有元素都相等。
函数调用时，实参的值的一份拷贝赋给形参，函数实际拿到值是一个副本。
Go 中数组作为参数传递就是按照值传递的方式传递副本。若作为参数传递的数组很大，这样的传递方式就很低效，函数内部对数组的修改也只能影响副本。这和很多其它把数组作为引用传递的语言不同。
可以选择数组指针作为参数传递，这样函数内部对数组元素的修改在函数的调用者处也可见。
// zeroes the contents of a [32]byte array
func zero(ptr *[32]byte) {
for i := range ptr {
ptr[i] = 0
}
}
func zero(ptr *[32]byte) {
*ptr = [32]byte{}
}
由于数组长度固定，不可增删元素，且长度也是数组类型的一部分，因此数组很少被用作函数的参数。
数组不是引用类型。
切片
切片是包含不定个数的相同类型元素的序列。写法是 []T。
切片和数组紧密关联。切片是一种可以访问到数组（这样的数组称为切片的底层数组）的部分或全部数据的轻量数据结构。
切片由 3 部分组成：指针，长度，容量。
- 指针指向切片可以访问到的底层数组的第一个元素（不一定是底层数组本身的第一个元素）。
- 切片的容量通常是切片的第一个元素到底层数组的最后一个元素之间元素的个数；
cap返回切片容量。 - 长度是切片元素的个数，不能超过数组容量，
len返回切片长度。
切片本质上是结构体，结构体里直接存储了切片的长度和容量。
多个切片可以指向同一个底层数组，因此它们指向的底层数组元素会重叠到。
操作符 s[i:j]（0<=i<=j<=cap(s)）创建了一个可以访问到底层数组的第 i 个到第 j-1 个元素的切片（共享底层数组空间）。s 可以是一个数组变量，一个指向数组的指针，或者是另一个切片。i 省略的话默认是 0，j 省略的话默认是 len(s)，i 和 j 都省略的话表示切片可以访问到整个底层数组。此操作符的执行时间是常数（底层数组相同，只需要移动指针）。
若 s 是切片，s[i:j] 的 j 超过 s 的容量会 panic（i 和 j 可以等于容量）；j 超过 s 的长度但小于 s 的容量则会扩展切片的范围，得到的切片的长度会大于 s 的长度。
For arrays or strings, the indices are in range if
0 <= low <= high <= len(a), otherwise they are out of range. For slices, the upper index bound is the slice capacitycap(a)rather than the length.
对于 b := a[low, high] 可以读写 a[low] 到 a[high-1] 范围内的所有元素，append(b, x) 时可能会覆盖到 a[high] 以及后面的元素：
// https://go.dev/play/p/MXPRndGzl5v
a := [5]int{1, 2, 3, 4, 5}
b := a[1:4]
b = append(b, 0)
fmt.Println(a[4]) // 0（覆盖之前是 5）
a[low : high : max]（
Full slice expressions
，0 <= low <= high <= max <= cap(a)）在 a[low :high] 的基础上还将切片的容量设置成 max - low，可以避免意外覆盖的风险。其中只有 low 可以省略（默认是 0）。
这种写法只能用于数组和切片（常见于
底层代码
），不能用于字符串。
由于切片内部包含一个指向它能访问的底层数据的第一个元素的指针，当切片作为函数参数传递时，函数内部也可以通过访问切片副本的指针来修改底层数组的元素（引用传递）。拷贝一个切片实际上是为底层数组创建了一个别名。
切片字面量没有指定长度，它会自动创建合适大小的底层数组变量，并生成一个指向它的切片。
// https://go.dev/play/p/WSH-p8SnGz1
s := []int{0, 1, 2, 3, 4, 5}
fmt.Println(len(s), cap(s)) // 6, 6
和数组不同，切片之间不能相互比较，唯一合法的比较是和 nil 比较。
标准库提供了 bytes.Equal 来比较两个 []byte，其它类型的切片比较则需要手动实现。
// "deep" equality
func equal(x, y []string) bool {
if len(x) != len(y) {
return false
}
for i := range x {
if x[i] != y[i] {
return false
}
}
return true
}
The elements of a slice are indirect.
对于一个确定的切片而言，由于它的底层数组的元素可能被更改，切片在不同时刻包含的元素也可能不同。
对于引用类型而言，== 操作符比较的是引用的身份（reference identity），即两个引用类型是否指向同一个东西。
切片设计成不可比较的考量：
- 没有简单、高效、不晦涩的方法可以处理 切片包含自身 的情况。
- 若将比较逻辑设计成和引用类型一样的浅比较（“shallow” equality），但数组之间的比较却是深比较，这种让人感到困惑的不一致设计不好。
- 若将比较逻辑设计成深比较，切片就不能用作 map 的键，因为 Go 的 map 作为一种散列表，只对键进行了浅拷贝，它需要保证键的值在散列表的整个生命周期内都保持不变（设计成不可比较同样使切片不能作为 map 的键）。
切片的零值是 nil。nil 切片没有底层数组，长度和容量都为 0。
特定类型的 nil 可以用强制类型转换表达式表示：
var s []int // len(s) == 0, s == nil
s = nil // len(s) == 0, s == nil
s = []int(nil) // len(s) == 0, s == nil
s = []int{} // len(s) == 0, s != nil
非 nil 的切片的长度和容量也可以为 0，如 []int{}，make([]int, 3)[3:]。
判断切片是否为空要用 len(s) == 0，而不是 s == nil。
除了和 nil 比较的比较结果相等以外，nil 切片和长度为 0 的切片的所有行为都一致，比如可以 reverse(nil)。除非有明确的说明，Go 函数应该对长度为 0 的切片做同样的处理，无论它是 nil 还是非 nil。
make 用于创建指定类型、长度、容量的切片，容量省略时默认等于长度。
make 会创建一个不具名的数组并返回该数组的一个切片，该数组只能通过返回的切片才能访问。
make(()T, len) // capacity equals the length
make([]T, len, cap) // same as make([]T, cap)[:len]
实现原理
// https://github.com/golang/go/blob/go1.16.6/src/runtime/slice.go#L13
type slice struct {
array unsafe.Pointer
len int
cap int
}
扩容基本原则：
- slice 容量小于 1024，则将新容量扩大为原来的 2 倍；
- 容量大于等于 1024，则将新容量扩大为原来的 1.25 倍。
谨慎使用多个切片操作同一个数组，以防读写冲突。
append
append 用于往切片尾部追加元素。
var runes []rune
for _, r := range "hello, 世界" {
runes = append(runes, r)
}
fmt.Printf("%q\n", runes) // ['h' 'e' 'l' 'l' 'o' ',' ' ' '世' '界']
fmt.Printf("%q\n", []rune("hello, 世界")) // ['h' 'e' 'l' 'l' 'o' ',' ' ' '世' '界']
var x []int
x = append(x, 4, 5, 6)
x = append(x, x...) // append the slice x
appendInt 简易实现（实际 append 的扩容机制更复杂）：
func appendInt(x []int, y ...int) []int {
var z []int
// zlen 是 append 后的切片长度
zlen := len(x) + len(y)
if zlen <= cap(x) {
// 1. 原切片 x 的容量足够：扩展 x 的长度，x 仍指向原先的底层数组；
// 返回的切片 z 和原切片 x 指向同一个底层数组
z = x[:zlen]
} else {
// 2. 原切片 x 容量不够，则分配一个新的数组；
// 返回的切片 z 和原切片 x 指向不同的底层数组
zcap := zlen
if zcap < 2*len(x) {
// 每次扩容以上一次容量的两倍进行，避免频繁地去分配空间，保证 append 一个元素的平均耗时是一个常数
zcap = 2 * len(x)
}
z = make([]int, zlen, zcap)
// The copy built-in function copies elements from a source slice into a
// destination slice. (As a special case, it also will copy bytes from a
// string to a slice of bytes.) The source and destination may overlap. Copy
// returns the number of elements copied, which will be the minimum of
// len(src) and len(dst).
copy(z, x)
}
copy(z[len(x):], y)
return z
}
copy 会将源切片的数据逐个拷贝到目标切片指向的数组中，拷贝数量取决于两个切片长度的较小者，拷贝过程中不会发生扩容。
通常情况下，我们不知道调用 append 是否会重新分配一个底层数组，所以我们不能断言被 append 的切片和返回的切片到底是指向同一个还是不同的底层数组，同理我们也不能断言对老切片元素的操作是否会反映到新切片上来。所以惯常做法是把 append 的结果重新赋给作为参数传入的切片变量（runes = append(runes, r)）。
更新切片变量不仅仅在 append 时是必要的，任何可能改变切片长度、容量或指向的底层数组的操作，都应该更新切片变量。
Although the elements of the underlying array are indirect, the slice’s pointer, length, and capacity are not (indirect).
切片并不直接拥有它指向的底层数组的元素，但切片的指针、长度和容量是和切片直接绑定的一部分，3 个中的任何一个发生变化都需要对切片变量进行重新赋值。从这个角度来看，切片并不是纯粹的引用类型，更像是如下结构体：
type IntSlice struct {
ptr *int
len, cap int
}
切片的原位操作
反转，轮转：
// in-place reverse
func reverse(s []int) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
// rotate a slice left by 2 elements in place
s := []int{0, 1, 2, 3, 4, 5}
reverse(s[:2]) // "[1 0 2 3 4 5]"
reverse(s[2:]) // "[1 0 5 4 3 2]"
reverse(s) // "[2 3 4 5 0 1]"
去除空 []string 切片中的空字符串：
func nonempty(strings []string) []string {
i := 0
for _, s := range strings {
if s != "" {
strings[i] = s
i++
}
}
return strings[:i]
}
data := []string{"a", "", "b"}
fmt.Printf("%q\n", nonempty(data)) // ["a" "b"]
// 原 data 的部分元素被覆盖
fmt.Printf("%q\n", data) // ["a" "b" "b"]
func nonempty2(strings []string) []string {
out := strings[:0] // zero-length slice of original
for _, s := range strings {
if s != "" {
out = append(out, s)
}
}
return out
}
以上两种实现返回的切片和传入的切片指向同一个底层数组，避免了重新分配数组。可以共用底层数组的前提条件是算法中每输入一个值最多只会有一个输出值。
实现栈：
stack = append(stack, v) // push v
top := stack[len(stack)-1] // top of stack
stack = stack[:len(stack)-1] // pop
从切片中间移除一个元素：
// 保持其它元素的顺序不变
func remove1(slice []int, i int) []int {
copy(slice[i:], slice[i+1:])
return slice[:len(slice)-1]
}
// 不保持其它元素的顺序
func remove2(slice []int, i int) []int {
slice[i] = slice[len(slice)-1]
return slice[:len(slice)-1]
}
s1 := []int{5, 6, 7, 8, 9}
s2 := []int{5, 6, 7, 8, 9}
fmt.Println(remove1(s1, 2)) // "[5 6 8 9]"
fmt.Println(remove2(s2, 2)) // "[5 6 9 8]"
