【1-2 Golang】Go语言快速入门—数组与切片

&emsp;&emsp;数组和切片是Go语言提供的两种基本数据结构，数组的概念大家应该都很熟悉，相同类型元素的集合，且元素在内存中连续存储，可以非常方便的通过下标访问数组元素；那么什么是切片呢？切片可以理解为动态数组，也就是说数组长度（最大可以存储的元素数目）可以动态调整。切片是我们日常开发最常用的数据结构之一，应该重点学习。 ## 数组 &emsp;&emsp;数组的定义与使用非常简单，如下面实例所示： ``` package main import "fmt" func main() { var arr [3]int //数组访问 arr[0] = 100 arr[1] = 200 arr[2] = 300 //arr最大可以存储三个整数，下标从0开始，最大为2 //Invalid array index 3 (out of bounds for 3-element array)；访问越界，无法编译通过 //arr[3] = 400 fmt.Println(len(arr), arr) //len返回数组长度 var arr1 [5]int //数组的类型包括：元素类型 + 数组长度，任意一项不等，说明数组类型不同，无法相互赋值 //Cannot use 'arr' (type [3]int) as type [5]int //arr1 = arr fmt.Println(arr1) } ``` &emsp;&emsp;在使用数组过程中，需要重点注意下标最大值为len - 1，不要出现访问越界情况。Go语言数组和C语言数组使用非常类似，但是在数组作为函数参数使用时候，还是有些许不同的。 &emsp;&emsp;首先要明确一点的是，Go语言函数传参都是传值的（输入参数会拷贝一份），而不是传递引用（输入参数的地址），因此虽然你在函数内部修改了输入参数，但是调用方变量并没有改变，如下面事例： ``` package main import "fmt" func main() { arr := [6]int{1,2,3,4,5,6} testArray(arr) fmt.Println(arr) //原数组未发生修改：[1 2 3 4 5 6] } func testArray(arr [6]int) { arr[0] = 0 arr[5] = 500 fmt.Println(arr) //修改数组元素：[0 2 3 4 5 500] } ``` &emsp;&emsp;学习过C语言数组的伙伴可能会比较纳闷，C语言在这种情况下，调用方数组元素是会同步发生改变的。Go语言是怎么做到的呢？上面说过，Go语言函数传参都是传值的，所以Go语言会把数组所有元素全部拷贝一份，这样函数内部修改的数组就和原数组没有任何关系了。 &emsp;&emsp;我们可以简单看看Go语言汇编代码，Go语言本身提供有编译工具： ``` //-N 禁止优化 -l 禁止内联 -S 输出汇编 go tool compile -S -N -l test.go "".main STEXT size=125 //MOVQ 拷贝8字节数据 0x0026 00038 (test.go:6) MOVQ $1, "".arr+48(SP) 0x002f 00047 (test.go:6) MOVQ $2, "".arr+56(SP) 0x0038 00056 (test.go:6) MOVQ $3, "".arr+64(SP) 0x0041 00065 (test.go:6) MOVQ $4, "".arr+72(SP) 0x004a 00074 (test.go:6) MOVQ $5, "".arr+80(SP) 0x0053 00083 (test.go:6) MOVQ $6, "".arr+88(SP) //MOVUPS 拷贝16字节数组，数组6个元素拷贝三次 0x005c 00092 (test.go:7) MOVUPS "".arr+48(SP), X0 0x0061 00097 (test.go:7) MOVUPS X0, (SP) 0x0065 00101 (test.go:7) MOVUPS "".arr+64(SP), X0 0x006a 00106 (test.go:7) MOVUPS X0, 16(SP) 0x006f 00111 (test.go:7) MOVUPS "".arr+80(SP), X0 0x0074 00116 (test.go:7) MOVUPS X0, 32(SP) 0x0079 00121 (test.go:7) CALL "".testArray(SB) …… "".testArray STEXT nosplit 0x000f 00015 (test.go:11) SUBQ $136, SP 0x0026 00038 (test.go:12) MOVQ $0, "".arr+144(SP) 0x0032 00050 (test.go:13) MOVQ $500, "".arr+184(SP) ``` &emsp;&emsp;不要被汇编两个字吓到，只要了解虚拟内存结构（重点函数栈桢结构），了解寄存器概念，了解一些常见指令含义，上面逻辑就非常清楚了。"CALL testArray"就是函数调用，其上面几条指令就是参数准备，可以很明显看到参数是对原数组的一个拷贝。上述事例栈桢结构如下图所示：  ## 切片 &emsp;&emsp;切片可以理解为动态数组，基本使用和数组比较类似，都是连续存储，可以按下标访问；动态的含义是，切片的容量是可以调整的，往切片追加元素时，Go语言底层判断数组容量是否足够，如果不够则触发扩容操作。 ### 基本操作 &emsp;&emsp;我们先看一个小事例，以此了解切片的初始化、访问、追加元素等基本操作，以及切片的长度以及容量： ``` package main import "fmt" func main() { //声明并初始化切片 slice := []int{1,2,3} slice[0] = 100 //len：切片长度，即切片存储了几个元素；cap：切片容量，即切片底层数组最多能存储元素数目 fmt.Println(len(slice), cap(slice), slice) //上述声明方式，切片长度/容量都等于3： 3 3 [100 2 3] //往切片追加元素，注意切片slice容量是3，此时追加元素会触发扩容操作 slice = append(slice, 4) fmt.Println(len(slice), cap(slice), slice) //切片已经扩容，此时容量是6（一般按双倍容量扩容）： 4 6 [100 2 3 4] //切片的容量虽然是6，但长度是4，访问下标5越界 //slice[5] = 5 //panic: runtime error: index out of range [5] with length 4 //也可以基于make函数声明切片；第二个参数为切片长度，第三个参数为切片容量（可以省略，默认容量等于长度） slice1 := make([]int, 4, 8) slice1[1] = 1 slice1[2] = 2 fmt.Println(len(slice1), cap(slice1), slice1) //4 8 [0 1 2 0] //切片遍历访问 for idx, v := range slice { printSliceValue(idx, v) //printSliceValue自己随便定义就行 } } ``` &emsp;&emsp;函数len用于获取切片长度，cap用于获取切片容量；切片长度指切片元素数目，访问下标最大为len - 1，切片容量指切片底层数组最多能存储的元素数目；append函数用于往切片追加元素，该函数会判断切片容量，如果容量不够则触发扩容操作，一般按照容量两倍扩容。make是Go语言提供的变量初始化函数，可用于初始化一些内置类型变量，如切片，map，管道chan等。 &emsp;&emsp;我们可以通过for range方式遍历切片，range可以获取当前遍历元素的索引以及元素值，那么问题来了，遍历过程中修改元素值，切片的元素会修改吗？如下面的事例： ``` package main import "fmt" func main() { slice := make([]int, 10, 10) for i := 0; i < 10; i ++ { slice[i] = i } for idx, v := range slice { v += 100 printSliceValue(idx, v) } fmt.Println(slice) //输出 [0 1 2 3 4 5 6 7 8 9] } func printSliceValue(idx, val int) { fmt.Println(idx, val) } ``` &emsp;&emsp;显而易见，这么修改元素v的值，切片slice的元素不会改变。为什么呢？因为这里索引值v只是切片元素的一个拷贝，修改副本值，原值肯定是不会改变的。那么想在遍历中修改切片的值怎么办？可以通过slice[idx]形式修改，这样访问到的才是切片原值。 &emsp;&emsp;切片还有一个常见操作：截取，即截取该切片的一部分生成一个新的切片，语法格式为"slice[start:end]"，start与end均表示下标，左开又闭（新切片包括下标start元素，不包含下标end元素），新切片长度为end - start。 ``` package main import "fmt" func main() { slice := []int{1,2,3,4,5,6,7,8,9,10} //切片截取 slice1 := slice[2:5] //修改新切片slice1元素，slice元素会改变吗？ slice1[0] = 100 fmt.Println(len(slice), cap(slice), slice) fmt.Println(len(slice1), cap(slice1), slice1) //slice1追加多个元素，超过其cap触发扩容 slice1 = append(slice1, 11,12,13,14,15,16,17,18,19,20,21,22) //再次修改slice1元素，slice元素会改变吗？ slice1[0] = 200 fmt.Println(len(slice), cap(slice), slice) fmt.Println(len(slice1), cap(slice1), slice1) } /** 输出： 10 10 [1 2 100 4 5 6 7 8 9 10] 3 8 [100 4 5] 10 10 [1 2 100 4 5 6 7 8 9 10] 15 16 [200 4 5 11 12 13 14 15 16 17 18 19 20 21 22] **/ ``` &emsp;&emsp;分析输出结构，通过截取生成新切片slice1之后，修改slice1元素，slice元素竟然也被改变了！这是为什么呢？因为切片底层也是基于数组实现，截取后两个切片共用同一个底层数组，所以修改元素才会互相影响。那为什么append触发扩容之后，又不影响了呢？因为扩容会申请新的数组，也就是说slice1底层数组变了，与slice底层数组剥离了，此时修改元素肯定不会互相影响了。 &emsp;&emsp;另外注意，slice1 := slice[2:5]截取切片后，slice长度是3，但是容量是8；因为slice1与slice共用底层数组，而底层数组最大容量是10，但是slice1却是从底层数组索引2开始，所以slice1的容量就是10 - 2 = 8 了。 &emsp;&emsp;最后我们再思考一个问题，前面我们介绍数组在传递的时候是按值传递，函数内部修改数组元素，调用方数组并没有改变？那么切片呢？我们需要牢记一点，Go语言传参都是按值传递的？那就是了，切片和数组一样，也不会改变。是这样吗？我们用一个小事例验证下： ``` package main import "fmt" func main() { slice := make([]int, 2, 10) slice[0] = 1 slice[1] = 2 fmt.Println(len(slice), cap(slice), slice) //初始切片长度2，容量10：2 10 [1 2] testSlice(slice) fmt.Println(len(slice), cap(slice), slice) //切片长度容量都没有改变，但是切片元素改变了：2 10 [100 200] } func testSlice(slice []int) { slice[0] = 100 slice[1] = 200 slice = append(slice, 300) fmt.Println(len(slice), cap(slice), slice) //修改切片元素，并追加一个元素，切片长度3，容量10：3 10 [100 200 300] } ``` &emsp;&emsp;貌似和猜想的不一样啊，testSlice函数中修改了切片元素，main函数中slice切片元素也同步改变了；而testSlice函数追加元素，改变了切片长度，但是main函数中slice切片长度却没有改变。why？Go语言传参到底是传值还是传引用呢？Go语言确实是按值传参的。长度和容量都是切片的值，所以即使testSlice函数修改了main函数中也不会改变，但是底层数组却是共用的，testSlice函数修改了main函数中会同步修改。 &emsp;&emsp;看到这里可能你还是有些迷惑，不用担心，学习下一小节切片实现原理之后，相信你会恍然大悟。 ### 实现原理 &emsp;&emsp;我们一直说切片就是动态数组，这是怎么做到动态的呢？都知道数组是连续内存存储的，所以想追加元素非常麻烦，需要申请更大的连续内存空间，拷贝所有数组元素，性能非常大。切片也是基于数组实现的，只不过采取预分配策略，一般切片的容量都比切片长度大，这样再往切片追加元素时，就可以避免内存分配以及数据拷贝。这样一来，切片也需要记录更多的信息：如数组首地址，用于存储元素；容量，记录底层数组最多可以存储的元素数目；长度，记录已经存储的元素数目。容量减长度，就是数组剩余长度了，即该切片在触发扩容之前，还能追加的元素数目。 &emsp;&emsp;切片的定义在runtime/slice.go文件，如下： ``` type slice struct { array unsafe.Pointer len int cap int } ``` &emsp;&emsp;和我们猜测的一样，切片包含三个字段，其实array是一个指针，指向底层数组收地址。该文件还定义了一些常用的切片操作函数： ``` //make创建切片底层实现 func makeslice(et *_type, len, cap int) unsafe.Pointer //切片追加元素时，容量不足扩容实现方法 func growslice(et *_type, old slice, cap int) slice //切片数据拷贝 func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int ``` &emsp;&emsp;当我们使用make函数创建切片类型时，底层就是调用makeslice函数分配数组，其中第一个参数type表示切片存储的元素类型，因此数组所需内存大小应该是元素大小乘数组容量。makeslice函数实现非常简单，如下： ``` func makeslice(et *_type, len, cap int) unsafe.Pointer { //math.MulUintptr返回a * b，同时判断是否发生溢出 mem, overflow := math.MulUintptr(et.size, uintptr(cap)) //省略了一些参数校验逻辑 return mallocgc(mem, et, true) //mallocgc函数用于分配内存，第三个参数表示是否初始化内存为全零 } ``` &emsp;&emsp;函数makeslice好像只是申请了切片底层数组内存，那么结构体slice中的其他字段呢？怎么维护呢？函数参数传递切片时，传递的到底是什么呢？这就需要我们分析汇编代码了。Go程序如下： ``` package main import "fmt" func main() { slice := make([]int, 4, 10) slice[0] = 100 printInt(len(slice)) printInt(cap(slice)) testSlice(slice) } func printInt(a int) { fmt.Println(a) } func testSlice(slice []int) { fmt.Println(slice) } ``` &emsp;&emsp;编译后的汇编代码如下： ``` "".main STEXT size=153 //makeslice第一个参数是类型指针，这里就是type.int 0x0018 00024 (test.go:6) LEAQ type.int(SB), AX //准备第二个参数 0x001f 00031 (test.go:6) MOVL $4, BX //准备第三个参数 0x0024 00036 (test.go:6) MOVL $10, CX //函数调用；函数返回值即数组首地址，在AX寄存器 0x0029 00041 (test.go:6) CALL runtime.makeslice(SB) //下面三行汇编是构造slice结构：数组首地址 + len + cap 0x002e 00046 (test.go:6) MOVQ AX, "".slice+32(SP) 0x0033 00051 (test.go:6) MOVQ $4, "".slice+40(SP) 0x003c 00060 (test.go:6) MOVQ $10, "".slice+48(SP) //AX寄存器存储数组首地址，即赋值slice[0] = 100 0x0047 00071 (test.go:7) MOVQ $100, (AX) //+40(SP)即切片的len，拷贝到AX寄存器作为参数传递 0x004e 00078 (test.go:8) MOVQ "".slice+40(SP), AX 0x0053 00083 (test.go:8) MOVQ AX, ""..autotmp_1+24(SP) 0x0058 00088 (test.go:8) CALL "".printInt(SB) //+48(SP)即切片的cap，拷贝到AX寄存器作为参数传递 0x005d 00093 (test.go:9) MOVQ "".slice+48(SP), AX 0x0062 00098 (test.go:9) MOVQ AX, ""..autotmp_1+24(SP) 0x0067 00103 (test.go:9) CALL "".printInt(SB) //拷贝slice结构：数组首地址 + len + cap，构造函数testSlice输入参数 0x006c 00108 (test.go:11) MOVQ "".slice+32(SP), AX 0x0071 00113 (test.go:11) MOVQ "".slice+40(SP), BX 0x0076 00118 (test.go:11) MOVQ "".slice+48(SP), CX 0x0080 00128 (test.go:11) CALL "".testSlice(SB) ``` &emsp;&emsp;函数输入参数可以在栈上，也可以使用寄存器传递输入参数，比如上述代码，AX是第一个输入参数，BX、CX依次是第二个、第三个输入参数；函数返回值也是既可以在栈上，也可以使用寄存器，上面代码使用AX寄存器作为第一个返回值。 &emsp;&emsp;毕竟slice结构非常简单明了，三个8字节，数组首地址 + len + cap，所以可以很方便的通过汇编代码构造。而len(slice)获取切片长度，cap(slice)获取切片容量更是简单，slice地址偏移8字节、16字节就是了。 &emsp;&emsp;另外注意testSlice函数调用，拷贝了slice结构作为函数参数，底层数组呢？肯定还是共用的，所以在函数testSlice内部修改了切片元素，调用方也会同步修改；而在函数testSlice内部append触发的扩容，却不回影响调用方切片的len以及cap。这也解决了我们上一小节留下的一些疑惑。 &emsp;&emsp;上述事例示意图如下所示：  ### 扩容 &emsp;&emsp;append用于往切片追加元素，其底层实现会判断切片容量，如果容量不足，则触发扩容。append通常有两种写法：1）追加一个切片到另一个切片；2）追加元素到一个切片。如下面事例所示： ``` package main import "fmt" func main() { slice := make([]int, 0, 100) slice = append(slice, 10, 20, 30) slice1 := []int{1, 2, 3} slice = append(slice, slice1...) fmt.Println(slice,slice1) //[10 20 30 1 2 3] [1 2 3] } ``` &emsp;&emsp;append函数实现在哪呢？如果你查看runtime/slice.go文件，会发现好像没有appendslice函数，倒是有growslice切片扩容的实现。append函数其实是编译阶段生成的，并没有源码，这里直接给出两种写法下的核心逻辑： ``` //参考1：cmd/compile/internal/walk/assign.go:appendSlice //参考2：cmd/compile/internal/walk/builtin.go:walkAppend // expand append(l1, l2...) to // init { // s := l1 // n := len(s) + len(l2) // // Compare as uint so growslice can panic on overflow. // if uint(n) > uint(cap(s)) { // s = growslice(s, n) // } // s = s[:n] // memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T)) // } // Rewrite append(src, x, y, z) // init { // s := src // const argc = len(args) - 1 // if cap(s) - len(s) < argc { // s = growslice(s, len(s)+argc) // } // n := len(s) // s = s[:n+argc] // s[n] = a // s[n+1] = b // ... // } ``` &emsp;&emsp;可以看到，在容量不足时，都是通过growslice来扩容的。函数growslice在切片容量较小时，按照两倍扩容；切片容量较大时，扩容25%。确定切片容量后，就是申请内存，同时拷贝切片数据到新数组。有兴趣的读者可以研究下growslice函数的源码。 ### 拷贝 &emsp;&emsp;最后我们再探索一个问题：不管是切片的截取，传参等，底层数组初始都是共用的，修改一个切片的元素必然影响另一个切片，有没有办法实现切片的完全拷贝呢？拷贝后两个切片数组也是隔离的，互不影响。这种完全拷贝可以基于Go语言内置函数copy实现： ``` package main import "fmt" func main() { slice := []int{1,2,3,4,5} slice1 := make([]int, len(slice), 10) copy(slice1, slice) slice1[0] = 100 fmt.Println(slice, slice1) } /** [1 2 3 4 5] [100 2 3 4 5] **/ ``` &emsp;&emsp;可以看到，修改切片slice1元素之后，slice切片元素没有发生改变。这里又有疑问了，copy函数的实现逻辑是怎样的呢？是runtime/slice.go文件中的slicecopy函数吗？只能说不完全是，Go语言在编译阶段判断，如果切片元素类型包括指针，则copy对应typedslicecopy函数；如果需要一些运行时变量，则copy对应slicecopy函数；否则编译阶段直接生成汇编代码，这里直接给出该汇编代码的核心逻辑： ``` //参考：cmd/compile/internal/walk/builtin.go:walkCopy // Lower copy(a, b) to a memmove call or a runtime call. // // init { // n := len(a) // if n > len(b) { n = len(b) } // if a.ptr != b.ptr { memmove(a.ptr, b.ptr, n*sizeof(elem(a))) } // } ``` ## 总结 &emsp;&emsp;到这里数组和切片的基本上算是讲解完毕了，是不是没想到竟然有这么多细节点需要注意。数组的按值传参一定要记得，切片的slice结构定义一定要清楚，结合该结构定义，思考切片的截取，传参，扩容等现象，应该就比较好理解了。