7、线性数据结构-切片

切片slice

• 容器容量可变，所以长度不能定死
• 长度可变，元素个数可变
• 底层必须依赖数组，可以理解它依赖于顺序表，表现也像个可变容量和长度顺序表
• 引用类型，和值类型有区别

定义切片

var s1 []int //长度、容量为0的切片，零值
var s2 = []int{}	//长度、容量为0的切片，字面量定义
var s3 = []int{1,3,5}	//字面量定义，长度、容量都是3
var s4 = make([]int,0)	//长度、容量都为0的切片，make([]T,length)
var s5 = make([]int,3,5) //长度为3，容量为5，底层数组长度为5，元素长度为3，所以显示[0,0,0]

使用切片要关注容量cap和长度len两个属性

内存模型

切片本质是对底层数组一个连续片段的引用。此片段可以是整个底层数组，也可以是由起始和终止索引标识的一些项的子集。

因为下面是底层数组，所以数组的容量是不可以改变的。元素内容能变的。

理解：切片保存的就是标头值，该值包括，指向的实际存储的地址，实际长度和容量的长度

由上图可知，pointer的实际地址和底层数组的地址是不同的

// https://github.com/golang/go/blob/master/src/runtime/slice.go
// slice header 或 descriptor
type slice struct {array unsafe.Pointer    指向底层数组的指针len int				切片访问的元素的个数（即长度）cap int				切片允许增长到的元素个数（即容量）
}
注意上面三个结构体的属性都是小写，所以包外不可见。len函数取就是len属性，cap函数取cap属性。

func main() {var s1 = make([]int, 3, 5)fmt.Printf("s1 %p %p %d", &s1, &s1[0], s1)}
s1 0xc000008078 0xc00000e450 [0 0 0]分析结果：&s1指的是标头值的地址  表示切片的地址，header这个结构体的地址&s1[0] 指的是实际存储的起始元素的地址， 第一个元素的地址，由于第一个元素存在底层数组中，数组的第一个元素地址就是数组的地址指针可以通过取底层数组的第一个元素的地址，即切片第一个元素的地址

追加

append：在切片的尾部追加元素，长度加1。
增加元素后，有可能超过当前容量，导致切片扩容。

切片扩容就是底层数组会出现起始一段地址

长度和容量

func main() {s1 := []int{100}fmt.Printf("s1 %p %p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s1 = make([]int, 2, 5)fmt.Printf("s1 %p %p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)
}s1 0xc000008078 0xc00001a098,1,1,[100]
s1 0xc000008078 0xc0000103f0,2,5,[0 0]结论：s1被重新复制了，但是S1的地址没有变化，底层数组的地址发生了变化

追加
func main() {s1 := make([]int, 2, 5)   //定义了一个长度为2，容量为5的切片，fmt.Printf("s1 %p %p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s1 = append(s1, 200)	// append返回新的header信息，覆盖fmt.Printf("s1 %p %p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)
}s1 0xc000008078 0xc0000103f0,2,5,[0 0]
s1 0xc000008078 0xc0000103f0,3,5,[0 0 200]
结论： s1的地址和底层数组的地址都没有发生变化，这是因为没有超过容量，底层共用同一个数组，但是，对底层数组使用的片段不一样。

func main() {s1 := make([]int, 2, 5)fmt.Printf("s1 %p %p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s1 = append(s1, 200)fmt.Printf("s1 %p %p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s2 := append(s1, 1, 2)	// append返回新的header信息，使用新的变量存储fmt.Printf("s2 %p %p,%d,%d,%v\n", &s2, &s2[0], len(s2), cap(s2), s2)
}
s1 0xc000008078 0xc0000103f0,2,5,[0 0]
s1 0xc000008078 0xc0000103f0,3,5,[0 0 200]
s2 0xc0000080c0 0xc0000103f0,5,5,[0 0 200 1 2]
结论：我们发现有新的header值，因为切片的重新赋值，所以s2有新的地址，但是s2指向的底层数组还是一样的，因为容量还没有超出。

func main() {s1 := make([]int, 2, 5)fmt.Printf("s1 %p %p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s2 := append(s1, 1, 2)fmt.Printf("s2 %p %p,%d,%d,%v\n", &s2, &s2[0], len(s2), cap(s2), s2)s3 := append(s1, -1)fmt.Printf("s3 %p %p, %d,%d,%v\n", &s3, &s3[0], len(s3), cap(s3),s3)
}
s1 0xc000008078 0xc0000103f0,2,5,[0 0]
s2 0xc0000080a8 0xc0000103f0,4,5,[0 0 1 2]
s3 0xc0000080d8 0xc0000103f0, 3,5,[0 0 -1]结论：目前三个切片底层用同一个数组，只不过长度不一样

func main() {s1 := make([]int, 2, 5)fmt.Printf("s1 %p %p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s2 := append(s1, 1, 2)fmt.Printf("s2 %p %p,%d,%d,%v\n", &s2, &s2[0], len(s2), cap(s2), s2)s3 := append(s1, -1)fmt.Printf("s3 %p, %p, %d,%d,%v\n", &s3, &s3[0], len(s3), cap(s3), s3)s4 := append(s3, 3, 4, 5, 6)fmt.Printf("s4 %p, %p, %d,%d,%v\n", &s4, &s4[0], len(s4), cap(s4), s4)}
s1 0xc000008078 0xc0000103f0,2,5,[0 0]
s2 0xc0000080a8 0xc0000103f0,4,5,[0 0 1 2]
s3 0xc0000080d8, 0xc0000103f0, 3,5,[0 0 -1]
s4 0xc000008108, 0xc0000142d0, 7,10,[0 0 -1 3 4 5 6]结论：底层数组变了，容量也增加了 ，底层数组的起始地址也发生了变化，相当于重新在内存中开辟了一块地址，并且容量变成了之前的2倍

结论：

• append一定返回一个新的切片，但本质上来说返回的是新的Header
• append可以增加若干元素
  • 如果增加元素时，当前长度 + 新增个数 <= cap则不扩容
    • 原切片使用原来的底层数组，返回的新切片也使用这个底层数组
    • 返回的新切片有新的长度
    • 原切片长度不变
  • 如果增加元素时，当前长度 + 新增个数 > cap则需要扩容
    • 生成新的底层数组，新生成的切片使用该新数组，将旧元素复制到新数组，其后追加新元素
    • 原切片底层数组、长度、容量不变

扩容策略

​ （老版本）实际上，当扩容后的cap<1024时，扩容翻倍，容量变成之前的2倍；当cap>=1024时，变成
之前的1.25倍。
​ （新版本1.18+）阈值变成了256，当扩容后的cap<256时，扩容翻倍，容量变成之前的2倍；当
cap>=256时， newcap += (newcap + 3*threshold) / 4 计算后就是 newcap = newcap +newcap/4 + 192 ，即1.25倍后再加192。
​ 扩容是创建新的底层数组，把原内存数据拷贝到新内存空间，然后在新内存空间上执行元素追加操作。
​ 切片频繁扩容成本非常高，所以尽量早估算出使用的大小，一次性给够，建议使用make。常用make([]int, 0, 100) 。

子切片

选取当前切片的一段等到一个新的切片，共用底层数据（因为不扩容），但是header中的三个属性会变，切片可以通过指定索引区间获得一个子切片，格式为slice[start:end]，规则就是前包后不包。

package mainimport "fmt"func main() {s1 := []int{10, 30, 50, 70, 90}for i := 0; i < len(s1); i++ {fmt.Printf("%d : addr = %p\n", i, &s1[i])}
}
0 : addr = 0xc00013a060
1 : addr = 0xc00013a068
2 : addr = 0xc00013a070
3 : addr = 0xc00013a078
4 : addr = 0xc00013a080

func main() {s1 := []int{10, 30, 50, 70, 90}fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s2 := s1	//共用一个底层数组fmt.Printf("s2 %p,%p,%d,%d,%v\n", &s2, &s2[0], len(s2), cap(s2), s2)}
s1 0xc000008078,0xc0000103f0,5,5,[10 30 50 70 90]
s2 0xc0000080a8,0xc0000103f0,5,5,[10 30 50 70 90]结论：s2复制s1的标头值，但是s2也被重新赋值了

func main() {s1 := []int{10, 30, 50, 70, 90}fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s2 := s1fmt.Printf("s2 %p,%p,%d,%d,%v\n", &s2, &s2[0], len(s2), cap(s2), s2)s3 := s1[:]fmt.Printf("s3 %p,%p,%d,%d,%v\n", &s3, &s3[0], len(s3), cap(s3), s3)
}
s1 0xc000008078,0xc0000103f0,5,5,[10 30 50 70 90]
s2 0xc0000080a8,0xc0000103f0,5,5,[10 30 50 70 90]
s3 0xc0000080d8,0xc0000103f0,5,5,[10 30 50 70 90]
结论：s3 := s1[:] 这个代表的就是从头到尾的元素都要，和s1共用一个底层数组

func main() {s1 := []int{10, 30, 50, 70, 90}fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s4 := s1[1:]fmt.Printf("s4 %p,%p,%d,%d,%v\n", &s4, &s4[0], len(s4), cap(s4), s4)
}
s1 0xc000008078,0xc0000103f0,5,5,[10 30 50 70 90]
s4 0xc0000080a8,0xc0000103f8,4,4,[30 50 70 90]结论： s4 := s1[1:] 掐头，从1开始容量长度都发生变化 首地址偏移了一位，因此长度len=end-start=4 cap=原cap-start=4

func main() {s1 := []int{10, 30, 50, 70, 90}fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s5 := s1[1:4]fmt.Printf("s5 %p,%p,%d,%d,%v\n", &s5, &s5[0], len(s5), cap(s5), s5)
}
s1 0xc000092060,0xc0000be060,5,5,[10 30 50 70 90]
s5 0xc000092090,0xc0000be068,3,4,[30 50 70]
结论：s5 := s1[1:4]  掐头去尾，但是前包后不包 就是1的位置的元素包含在里，4的位置的元素不在
len=end-start=3  cap=start的这个位置到容器的最大位置=4

func main() {s1 := []int{10, 30, 50, 70, 90}fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s6 := s1[:4]fmt.Printf("s6 %p,%p,%d,%d,%v\n", &s6, &s6[0], len(s6), cap(s6), s6)
}
s1 0xc000008078,0xc0000103f0,5,5,[10 30 50 70 90]
s6 0xc0000080a8,0xc0000103f0,4,5,[10 30 50 70]
结论：s6 := s1[:4]  去尾，后不包 len=4-0=4 容量=第一个位置到最大的容量值=5 cap=原cap-start 首地址还不变

func main() {s1 := []int{10, 30, 50, 70, 90}fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s7 := s1[1:1]fmt.Printf("s7 %p,%d,%d,%v\n", &s7, len(s7), cap(s7), s7)
}
s1 0xc000008078,0xc0000103f0,5,5,[10 30 50 70 90]
s7 0xc0000080a8,0,4,[]结论：首地址偏移1个元素，长度为0，cap=原cap-start 容量为4，共用底层数组  由于长度为0，所以不能s7[0]报错

为s7增加一个元素，s1、s7分别是什么？

func main() {s1 := []int{10, 30, 50, 70, 90}fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s7 := s1[1:1]s7 = append(s7, 100)fmt.Printf("s7 %p,%p,%d,%d,%v\n", &s7, &s7[0], len(s7), cap(s7), s7)fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)}
s1 0xc000008078,0xc0000103f0,5,5,[10 30 50 70 90]
s7 0xc0000080a8,0xc0000103f8,1,4,[100]
s1 0xc000008078,0xc0000103f0,5,5,[10 100 50 70 90]
结论：s7操作的也是在底层数组中，所以s7在1新增了100 底层数组s1的1位置30修改为了100 

func main() {s1 := []int{10, 30, 50, 70, 90}fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s8 := s1[4:4]fmt.Printf("s8 %p,%d,%d,%v\n", &s8, len(s8), cap(s8), s8)}
s1 0xc000008078,0xc0000103f0,5,5,[10 30 50 70 90]
s8 0xc0000080a8,0,1,[]
// 首地址偏移4个元素，长度为0，容量为1，因为最后一个元素没在切片中，共用底层数组

func main() {s1 := []int{10, 30, 50, 70, 90}fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s9 := s1[5:5]fmt.Printf("s9 %p,%d,%d,%v\n", &s9, len(s9), cap(s9), s9)
}
s1 0xc000008078,0xc0000103f0,5,5,[10 30 50 70 90]
s9 0xc0000080a8,0,0,[]增加元素会怎么样？s1、s9分别是什么？func main() {s1 := []int{10, 30, 50, 70, 90}fmt.Printf("s1 %p,%p,%d,%d,%v\n", &s1, &s1[0], len(s1), cap(s1), s1)s9 := s1[5:5]fmt.Printf("s9 %p,%d,%d,%v\n", &s9, len(s9), cap(s9), s9)s9 = append(s9, 100)fmt.Printf("s9 %p,%p,%d,%d,%v\n", &s9, &s9[0], len(s9), cap(s9), s9)
}
s1 0xc000008078,0xc0000103f0,5,5,[10 30 50 70 90]
s9 0xc0000080a8,0,0,[]
s9 0xc0000080a8,0xc00001a0e8,1,1,[100]

切片总结：

• 使用slice[start:end]表示切片，切片长度为end-start，前包后不包
• start缺省，表示从索引0开始
• end缺省，表示取到末尾，包含最后一个元素，特别注意这个缺省值是len(slice)即切片长度，不是容量
  • a1[5:]相当于a1[5:len(a1)]
• start和end都缺省，表示从头到尾
• start和end同时给出，要求end >= start
  • start、end最大都不可以超过容量值
  • 假设当前容量是8，长度为5，有以下情况
    • a1[:]，可以，共用底层数组，相当于对标头值的拷贝，也就是指针、长度、容量都一样
    • a1[:8]，可以，end最多写成8(因为后不包)，a1[:9]不可以。该切片长度、容量都为8，
      这8个元素都是原序列的，一旦append就扩容
    • a1[8:]，不可以，end缺省为当前长度5，等价于a1[8:5]
    • a1[8:8]，可以，但这个切片容量和长度都为0了。注意和a1[:8]的区别
    • a1[7:7]，可以，但这个切片长度为0，容量为1
    • a1[0:0]，可以，但这个切片长度为0，容量为8
    • a1[1:5]，可以，这个切片长度为4，容量为7，相当于跳过了原序列第一个元素
• 切片刚产生时，和原序列（数组、切片）开始共用同一个底层数组，但是每一个切片都自己独立保存着指针、cap和len
• 一旦一个切片扩容，就和原来共用一个底层数组的序列分道扬镳，从此陌路

后不包)，a1[:9]不可以。该切片长度、容量都为8，
这8个元素都是原序列的，一旦append就扩容
- a1[8:]，不可以，end缺省为当前长度5，等价于a1[8:5]
- a1[8:8]，可以，但这个切片容量和长度都为0了。注意和a1[:8]的区别
- a1[7:7]，可以，但这个切片长度为0，容量为1
- a1[0:0]，可以，但这个切片长度为0，容量为8
- a1[1:5]，可以，这个切片长度为4，容量为7，相当于跳过了原序列第一个元素

• 切片刚产生时，和原序列（数组、切片）开始共用同一个底层数组，但是每一个切片都自己独立保存着指针、cap和len
• 一旦一个切片扩容，就和原来共用一个底层数组的序列分道扬镳，从此陌路