Smarticen Notes

slice

5 min read

slice是切片，又称动态数组，依托数组实现，可以方便地进行扩容、传递等。

底层数组对用户屏蔽，在底层数组容量不足时可以实现自动重分配并生成新的slice。

数据结构

在源码包的src/runtime/slice.go:slice定义了Slice的数据结构：

type slice struct {
	array unsafe.Pointer
	len int
	cap int
}
  • array指向底层数组
  • len表示切片长度
  • cap表示底层数组容量 结构简单清晰

make创建slice

使用make创建slice，可以指定长度和容量，创建的时候底层会分配一个数组，数组的长度即容量。

例如slice := make([]int, 5,10)就创建了一个长度为5，容量为10的slice，只要后续添加的元素时没有达到容量10，那么就不用重新分配内存，直接使用预留内存即可。

使用数组创建slice

数组创建的slice，将与原数组共用一部分内存。 例如slice := array[5:7] 切片的长度是从数组中截取的部分，切片的容量则是从截取的位置开始到底层数组的结束。

使用数组创建切片还有一种特别的写法，即同时指定容量：

sliceA := make([]int, 5, 10)
sliceB := sliceA[0:5]   // len=5,cap=10
sliceC := sliceA[0:5:5] // len=5,cap=5

slice扩容

使用append向切片添加内容的时候，如果slice空间不足，就会触发slice扩容，重新申请一块更大的内存，然后将原来的slice的数据拷贝进新slice，扩容后再将数据追加进去。

扩容遵循以下原则：

  • 如果原slice容量小于1024，则新slice容量将扩大为原来的2倍。
  • 如果原slice容量大于等于1024，则新slice容量将扩大为原来的1.25倍。

使用append()向slice添加一个元素的流程如下：

  1. 如果slice容量够用，则将新元素添加进去，slice.len++，返回原slice
  2. 原slice容量不够，则将slice先扩容，扩容后得到新的slice
  3. 将新元素加入新slice，slice.len++，返回新的slice。

拷贝slice

使用内置的copy函数拷贝两个切片的时候，会将源切片的数据逐个拷贝到目的切片指向的数组中，拷贝数量取两个切片长度的最小值。

例如，长度为10的切片拷贝到长度为5的切片时，只会拷贝5个元素。也就是说，copy过程不会发生扩容。

总结

  • 每个切片都指向一个底层数组
  • 每个切片都保存了当前切片的长度、底层数组的可用容量。所以len()和cap()的时间复杂度都是O(1)。
  • 通过函数传递切片，只会拷贝切片这个结构体本身，不会拷贝底层数组。
  • 使用append()向切片添加元素有可能触发扩容，扩容后将会生成新的切片。

使用建议

  • 创建切片时尽量预留比较合适的空间，避免添加元素的过程中发生扩容的数据拷贝，有利于性能提升。
  • 切片拷贝时需要判断实际拷贝的元素格式
  • 谨慎使用多个切片拷贝同一个数组，以防止读写冲突。

Graph View