Go 语言, 一文彻底搞懂 slice 实现原理
slice 切片,因为其可以方便的进行扩容、传递等,在实际应用中比数组更加灵活。切片的一些基础使用可以看下之前的文章,传送门。
这里我们再更加深层次的了解下 slice 。先看几段代码,测试下诸位对 slice 的理解程度。
答题环节
以下程序输出什么?
答
案
是:
slice 根据数组 array 创建,与数组共享存储空间,slice 起始位置是 array[5],长度为 1,容量为 5,slice[0]和 array[5]地址相同。
以下程序输出什么?
答
案
是:
order
[low:high:max]
意思是对 order 进行切片,新切片范围是[low, high)
,新切片容量是 max;order 长度为 2 倍的 orderLen;
pollorder 切片是 order 的前半部分切片;
lockorder 是 order 的后半部分切片,即原 order 分成了两段;
所以,pollorder 和 lockerorder 的长度和容量都是 orderLen,即 5。
slice 实现原理
源码包 src/runtime/slice.go 定义的 slice 数据结构为:
array 指针指向底层数组
len 表示切片长度
cap 表示切片容量
make 创建 slice
make 创建 slice 可以同时指定其长度和容量,底层会分配一个数组,数组的长度即容量。
slice = make([]int,5,10): 表示改 slice 长度为 5,容量为 10。
数组创建 slice
使用数组来创建 slice 时,slice 与原数组共用一部分内存。
slice := array[5:7] 所创建的 slice ,结构如下图:
切片从数组 array[5] 开始,到数组 array[7] 结束(不包含 array[7]),切片长度为 2,数组后面的内容作为切片的预留内存,即容量为 5。
slice 扩容
在使用 append 向 slice 追加元素时,若 slice 空间不足则会发生扩容,扩容会重新分配一块更大的内存,将原 slice 拷贝到新 slice,然后返回新 slice。扩容后再将数据追加进去。
扩容操作只只对容量,扩容后的 slice 长度不变,容量变化规则如下:
若 slice 容量够用,则将新元素追加进去,slice.len++,返回原 slice
若 slice 容量不够用,将 slice 先扩容,扩容得到新 slice,将新元素追加进新 slice,slice.len++,返回新 slice。
slice copy
使用 copy() 内置函数拷贝两个切片时,会将源切片的数据逐个拷贝到目的的切片指向的数组中,拷贝数量取两个切片长度的最小值。
例如将长度为 10 的切片拷贝到长度为 5 的切片时,将会拷贝 5 个元素。也就是说 copy 不会发生扩容。
根据数组或切片来生成新的切片一般使用 slice := array[start:end] 方式,这种新生成的切片没有指定容量,新切片的容量是从 start 开始到 array 的结束(注意并不是到 end)。
另一种写法,生成新切片同时指定其容量:slice[start:end:cap] ,其中的 cap 为新切片的容量,容量不能超过原切片实际值。
总结
创建切片时可根据实际需要预分配容量,尽量避免追加过程中扩容操作,有利于提升性能
切片拷贝时需要判断实际拷贝的元素个数
谨慎使用多个切片操作同一个数组,以防读写冲突
每个切片都指向一个底层数组
每个切片都保存了当前切片的长度、底层数组可用容量
使用 len()、cap()计算切片长度、容量时,时间复杂度均为 O(1),不需要遍历切片
通过函数传递切片时,不会拷贝整个切片,因为切片本身只是个结构体而矣
使用 append() 向切片追加元素时有可能触发扩容,扩容后将会生成新的切片
版权声明: 本文为 InfoQ 作者【微客鸟窝】的原创文章。
原文链接:【http://xie.infoq.cn/article/e6bee89d08655c45a6d70ddd1】。文章转载请联系作者。
评论