Go学习

go slice切片

Posted by Liao on 2022-06-16

一、定义

slice元素存储在连续的内存中，实质是数组

1
2
3
4
5
6
7
// Slice is the runtime representation of a slice.
// It cannot be used safely or portably and its representation may change in a later release.
type Slice struct {
   Data unsafe.Pointer //元素存储的地方
   Len  int //存储元素的数量
   Cap  int //容量，可以存储多少个元素
}

二、创建切片

2.1 声明一个slice

只分配切片的结构，如下图，还没分配底层数组（存储空间），因此data=nil，存储个数为0，容量为0。这时不能对其进行读写操作，否则会越界。

1
var ints []int

data是数组的起始地址

2.2 通过make创建slice

如果通过make创建slice，不仅会分配这3个slice结构，还会为ints开辟一段容纳5个整形元素的内存，并初始化为整形的默认值0。

1
2
3
var ints []int = make([]int, 2, 5) // 长度是2 容量是5
ints = append(ints, 1) // 再追加一个元素，前面已经存储2个，因此放在第三位
fmt.Println(ints[2]) //输出1

已经存储的元素可以安全读写的（ints[0]、ints[1]、ints[2]），但是超出范围的话就是越界访问，会发生panic。

1
2
ints[0] = 1 //正常读写
ints[3] = 1 //panic

3.3 通过new创建slice

1
2
3
ps := new([]string)
*ps = append(*ps, "hello") 
fmt.Println(ps)

1、new一个slice变量，同样会分配 data、len、cap，但是不负责底层数组的分配，因此data=nil，len=0，cap=0，并且不能进行读写。

2、new的返回是slice结构的起始地址，因此ps是个地址

3、由于目前还没分配底层数组，因此可以由append来分配底层数组。

3.4 二维数组初始化

1
var ans [][]int
1
2
3
grid := [][]int{
		{9, 9, 8, 1}, {5, 6, 2, 6}, {8, 2, 6, 4}, {6, 2, 2, 2},
}
1
2
3
4
ans := make([][]int, n) // n行
for i := range ans {
	ans[i] = make([]int, n) // n列
}

三、切片与底层数组

1
2
3
4
5
6
7
8
9
arr := [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} //定义数组，数组长度确定了之后不能改变
var s1 []int = arr[1:5]
var s2 []int = arr[7:]
for i := range s1 { //1 2 3 4
	fmt.Println(s1[i]) 
}
for i := range s2 { // 7 8 9
	fmt.Println(s2[i])
}

1、可以将不同的slice关联到同一个数组，它们会共用底层数组。len是加入到slice的元素个，而cap会从data开始到底层数组结束的个数

2、slice访问和修改的都是底层数组的元素，要注意越界问题。

1
2
3
arr := [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
var s1 []int = arr[1:5]
fmt.Println(s1[4]) //越界 panic

可以通过append增加一个元素，或者修改范围arr[1:6]

1
2
3
4
arr := [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
var s1 []int = arr[1:5]
s1 = append(s1, 19)
fmt.Println(s1[4]) //19

3、添加元素后，容量不够，需要重新开辟数组

1
2
3
arr := [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
var s1 []int = arr[7:]
s1 = append(s1, 10)

arr[7:]的底层数组是 len是3，cap是3，再添加一个元素则需要扩容，原来的底层数组不能使用了，需要开辟新的数组：原来的元素拷贝过来，再添加新元素。

四、切片的扩容规则

golang1.18 之前：

1
2
ints := []int{1, 2}
ints = append(ints, 3, 4, 5)
4.1 预估容量
1
2
3
4
5
6
7
8
9
10
if oldCap * 2 < cap {
  	newCap = cap
} 
else {
  if oldLen < 1024 
  	newCap = oldCap * 2 //容量直接翻倍
  else {
    newCap = oldCap * 1.25 	
  }
}

所以例子中 newCap = 5

4.2 newCap个元素需要多大内存

在编程语言中，申请分配内存并不是直接与操作系统交涉，而是和语言自身实现的内存管理模块有关。内存管理模块会提前向OS申请 一批内存，分成常用的规格管理起来（8、16、32、48、64、96、112字节…）。

当我们申请内存时，会匹配到足够大 且最接近的规格。

4.3 匹配到适合的内存规格

在64位操作系统下，一个字节占用8位，因此需要申请 5 * 8 =40 (int 是8，string是16字节) 字节的内存，来存放到扩容后的底层数组，而实际申请时会匹配到48字节，因此48字节的内存能装6个元素。

所以扩容后的容量时6。

golang 1.18以后扩容规则改变了

1
2
ints := []int{1, 2}
ints = append(ints, 3, 4, 5)
4.1 预估容量
1
2
3
4
5
6
7
8
9
10
if oldCap * 2 < cap {
  	newCap = cap
} 
else {
  if oldLen < 256 
  	newCap = oldCap * 2 //容量直接翻倍
  else {
    newCap = oldCap * 1.25 	
  }
}

所以例子中 newCap = 5

五、实际应用（语法糖）

1、二维数组排序

2、unpack slice，…运算符 

1
var c = [...]int{1, 2, 3, 4, 5} // 不确定长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func main() {
  ans := mergeSimilarItems([][]int{{1, 3}, {2, 2}}, [][]int{{7, 1}, {2, 2}, {1, 4}})
	fmt.Println(ans)
}
func mergeSimilarItems(items1 [][]int, items2 [][]int) [][]int {
	sort.Slice(items1, func(i, j int) bool { // 二维数组排序
		return items1[i][0] < items1[j][0]
	})

	sort.Slice(items2, func(i, j int) bool {
		return items2[i][0] < items2[j][0]
	})

	var ans [][]int
	i, j := 0, 0
	for {
		if i == len(items1) {
			return append(ans, items2[j:]...) // unpack slice，把items2其余的数加入到ans
		} else if j == len(items2) {
			return append(ans, items1[i:]...)
		} else if items1[i][0] < items2[j][0] {
			ans = append(ans, items1[i])
			i++
		} else if items1[i][0] > items2[j][0] {
			ans = append(ans, items2[j])
			j++
		} else {
			items1[i][1] += items2[j][1]
			ans = append(ans, items1[i])
			i++
			j++
		}
	}
}

slice是一个结构体，作为形式参数传递时将结构体内容复制，实质上是值传递。

3、slice引用作为参数传递，实参不变

1
2
3
4
5
6
7
8
9
10
11
12
func main() {
	sli := make([]int, 0)
	sli = append(sli, 1, 2, 3, 4, 5)
	fmt.Printf("%p\n", &sli) // 0x14000114018
	modyfiy(sli)
  fmt.Println(sli) // [1 2 3 4 5]
}

func modyfiy(sli []int) {
	sli = append(sli, 6)
	fmt.Printf("%p\n", sli) // 0x14000118060
}

4、slice指针作为参数传递，可以同步到实参

因为实参和形参指向同一个内存地址0x14000194018，因此 *sli = append(*sli, 6) 改变了slice的地址，其值会改变

1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
	sli := make([]int, 0)
	sli = append(sli, 1, 2, 3, 4, 5)
	fmt.Println(sli) // [1 2 3 4 5]
	modyfiy(&sli)
  fmt.Printf("%p\n", &sli) //0x14000194018
	fmt.Println(sli) // [1 2 3 4 5 6]
}

func modyfiy(sli *[]int) {
	*sli = append(*sli, 6) 
  fmt.Printf("%p\n", sli) // 0x14000194018
}
FEATURED TAGS
Go学习
FRIENDS