乐趣区

关于go:12-GolangGo语言快速入门数组与切片

  数组和切片是 Go 语言提供的两种根本数据结构,数组的概念大家应该都很相熟,雷同类型元素的汇合,且元素在内存中间断存储,能够十分不便的通过下标拜访数组元素;那么什么是切片呢?切片能够了解为动静数组,也就是说数组长度(最大能够存储的元素数目)能够动静调整。切片是咱们日常开发最罕用的数据结构之一,应该重点学习。

数组

  数组的定义与应用非常简单,如上面实例所示:

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)
}

  在应用数组过程中,须要重点留神下标最大值为 len – 1,不要呈现拜访越界状况。Go 语言数组和 C 语言数组应用十分相似,然而在数组作为函数参数应用时候,还是有些许不同的。

  首先要明确一点的是,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]
}

  学习过 C 语言数组的搭档可能会比拟纳闷,C 语言在这种状况下,调用方数组元素是会同步产生扭转的。Go 语言是怎么做到的呢?下面说过,Go 语言函数传参都是传值的,所以 Go 语言会把数组所有元素全副拷贝一份,这样函数外部批改的数组就和原数组没有任何关系了。

  咱们能够简略看看 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)

  不要被汇编两个字吓到,只有理解虚拟内存构造(重点函数栈桢构造),理解寄存器概念,理解一些常见指令含意,下面逻辑就十分分明了。”CALL testArray” 就是函数调用,其下面几条指令就是参数筹备,能够很显著看到参数是对原数组的一个拷贝。上述事例栈桢构造如下图所示:

切片

  切片能够了解为动静数组,根本应用和数组比拟相似,都是间断存储,能够按下标拜访;动静的含意是,切片的容量是能够调整的,往切片追加元素时,Go 语言底层判断数组容量是否足够,如果不够则触发扩容操作。

基本操作

  咱们先看一个小事例,以此理解切片的初始化、拜访、追加元素等基本操作,以及切片的长度以及容量:

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 本人轻易定义就行
  }
}

  函数 len 用于获取切片长度,cap 用于获取切片容量;切片长度指切片元素数目,拜访下标最大为 len – 1,切片容量指切片底层数组最多能存储的元素数目;append 函数用于往切片追加元素,该函数会判断切片容量,如果容量不够则触发扩容操作,个别依照容量两倍扩容。make 是 Go 语言提供的变量初始化函数,可用于初始化一些内置类型变量,如切片,map,管道 chan 等。

  咱们能够通过 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)
}

  不言而喻,这么批改元素 v 的值,切片 slice 的元素不会扭转。为什么呢?因为这里索引值 v 只是切片元素的一个拷贝,批改正本值,原值必定是不会扭转的。那么想在遍历中批改切片的值怎么办?能够通过 slice[idx] 模式批改,这样拜访到的才是切片原值。

  切片还有一个常见操作:截取,即截取该切片的一部分生成一个新的切片,语法格局为 ”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]
**/

  剖析输入构造,通过截取生成新切片 slice1 之后,批改 slice1 元素,slice 元素居然也被扭转了!这是为什么呢?因为切片底层也是基于数组实现,截取后两个切片共用同一个底层数组,所以批改元素才会相互影响。那为什么 append 触发扩容之后,又不影响了呢?因为扩容会申请新的数组,也就是说 slice1 底层数组变了,与 slice 底层数组剥离了,此时批改元素必定不会相互影响了。

  另外留神,slice1 := slice[2:5] 截取切片后,slice 长度是 3,然而容量是 8;因为 slice1 与 slice 共用底层数组,而底层数组最大容量是 10,然而 slice1 却是从底层数组索引 2 开始,所以 slice1 的容量就是 10 – 2 = 8 了。

  最初咱们再思考一个问题,后面咱们介绍数组在传递的时候是按值传递,函数外部批改数组元素,调用方数组并没有扭转?那么切片呢?咱们须要牢记一点,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]
}

  貌似和猜测的不一样啊,testSlice 函数中批改了切片元素,main 函数中 slice 切片元素也同步扭转了;而 testSlice 函数追加元素,扭转了切片长度,然而 main 函数中 slice 切片长度却没有扭转。why?Go 语言传参到底是传值还是传援用呢?Go 语言的确是按值传参的。长度和容量都是切片的值,所以即便 testSlice 函数批改了 main 函数中也不会扭转,然而底层数组却是共用的,testSlice 函数批改了 main 函数中会同步批改。

  看到这里可能你还是有些蛊惑,不必放心,学习下一大节切片实现原理之后,置信你会豁然开朗。

实现原理

  咱们始终说切片就是动静数组,这是怎么做到动静的呢?都晓得数组是间断内存存储的,所以想追加元素十分麻烦,须要申请更大的间断内存空间,拷贝所有数组元素,性能十分大。切片也是基于数组实现的,只不过采取预调配策略,个别切片的容量都比切片长度大,这样再往切片追加元素时,就能够防止内存调配以及数据拷贝。这样一来,切片也须要记录更多的信息:如数组首地址,用于存储元素;容量,记录底层数组最多能够存储的元素数目;长度,记录曾经存储的元素数目。容量减长度,就是数组残余长度了,即该切片在触发扩容之前,还能追加的元素数目。

  切片的定义在 runtime/slice.go 文件,如下:

type slice struct {
  array unsafe.Pointer
  len   int
  cap   int
}

  和咱们猜想的一样,切片蕴含三个字段,其实 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

  当咱们应用 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 函数用于分配内存,第三个参数示意是否初始化内存为全零
}

  函数 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)
}

  编译后的汇编代码如下:

"".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)

  函数输出参数能够在栈上,也能够应用寄存器传递输出参数,比方上述代码,AX 是第一个输出参数,BX、CX 顺次是第二个、第三个输出参数;函数返回值也是既能够在栈上,也能够应用寄存器,下面代码应用 AX 寄存器作为第一个返回值。

  毕竟 slice 构造十分简单明了,三个 8 字节,数组首地址 + len + cap,所以能够很不便的通过汇编代码结构。而 len(slice) 获取切片长度,cap(slice) 获取切片容量更是简略,slice 地址偏移 8 字节、16 字节就是了。

  另外留神 testSlice 函数调用,拷贝了 slice 构造作为函数参数,底层数组呢?必定还是共用的,所以在函数 testSlice 外部批改了切片元素,调用方也会同步批改;而在函数 testSlice 外部 append 触发的扩容,却不回影响调用方切片的 len 以及 cap。这也解决了咱们上一大节留下的一些纳闷。

  上述事例示意图如下所示:

扩容

  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]
}

  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
//     ...
//   }

  能够看到,在容量有余时,都是通过 growslice 来扩容的。函数 growslice 在切片容量较小时,依照两倍扩容;切片容量较大时,扩容 25%。确定切片容量后,就是申请内存,同时拷贝切片数据到新数组。有趣味的读者能够钻研下 growslice 函数的源码。

拷贝

  最初咱们再摸索一个问题:不论是切片的截取,传参等,底层数组初始都是共用的,批改一个切片的元素必然影响另一个切片,有没有方法实现切片的齐全拷贝呢?拷贝后两个切片数组也是隔离的,互不影响。这种齐全拷贝能够基于 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]
**/

  能够看到,批改切片 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))) }
// }

总结

  到这里数组和切片的基本上算是解说结束了,是不是没想到居然有这么多细节点须要留神。数组的按值传参肯定要记得,切片的 slice 构造定义肯定要分明,联合该构造定义,思考切片的截取,传参,扩容等景象,应该就比拟好了解了。

退出移动版