Golang

7.数组和切片

1. 数组 array

数组是定长的，长度一旦定义，不能更改。

1.1. 如何声明?

声明数组，注意要指定长度。如果未指定长度可使用省略号，将会按长度初始化值的个数进行计算。

1
2
3

var a [3]int
v := [...]int{1,2,3}
q := [3]int{1, 2, 3, 4} // 编译错误: cannot assign [4]int to [3]int

多维数组初始化

1

var grid [4][5]int{{1,2},{4,5}}

指定索引初始化

1

v1 := [...]string{1:"1",5:"5",9:"9"}

1.2. 零值

数组是值类型

声明数组后不赋值，则每个元素都被初始化零值，比如 int 类型会初始化为 0。

1.3. 特性

Go 语言中数组在初始化之后大小就无法改变，存储元素类型相同、但是大小不同的数组类型在 Go 语言看来也是完全不同的，只有两个条件都相同才是同一个类型。

1
2
3

var a1 [3]int
var a2 [5]int
fmt.Printf("%T != %T", a1, a2)

两种不同的优化 cmd/compile/internal/gc.anylit

  1. 当元素数量小于或者等于 4 个时，会直接将数组中的元素放置在栈上；
  2. 当元素数量大于 4 个时，会将数组中的元素放置到静态区并在运行时取出；

1.4. 元素比较

需要满足两个条件

  1. 如果数组的元素类型可比较，则数组也可以比较
  2. 维数相同，含有元素个数相同

1.5. 遍历数组

1
2
3

for i,v := range arr {
  fmt.Println(i,v)
}

1.6. 作为函数参数

调用 func instance(arr [5]int ) 会拷贝数组

函数参数变量接收的是一个复制的副本，并不是原始调用的变量。因为函数参数传递的机制导致传递大的数组类型将是低效的，并且对数组参数的任何的修改都是发生在复制的数组上，并不能直接修改调用时原始的数组变量。

1.7. 编译初始化

编译器会在负责初始化字面量的 cmd/compile/internal/gc.anylit 函数中做两种不同的优化：

  1. 当元素数量小于或者等于 4 个时，会直接将数组中的元素放置在栈上；
  2. 当元素数量大于 4 个时，会将数组中的元素放置到静态区并在运行时取出拷贝到栈上；

2. 切片 slice

切片 slice 本身是没有数据的，是对底层 array 的一个 view

2.1. 如何声明?

声明为 nil 的空切片，底层数组指针 = nil，作为函数的实参也是 nil, 可以求长度,结果为 0

注意空切片可以 append 增加元素，可以动态扩展内存。同样为 nil 的map 不行，对空 map 增加键值对会 panic。

1

var arr []int

1
2

s2 := []int{}    // 空切片,创建了长度和容量都是0的底层数组
s3 := arr[0:2:cap(arr)]   // len=2; cap=cap(arr)

声明 len=10, cap=32 的 slice，会初始化 10 个零值

1

s1 := make([]int, 10 , 32)  // 类型,len, cap

2.2. 取内容

多个slice之间可以共享底层的数据，并且引用的数组部分区间可能重叠。

1
2
3
4
5

arr := []int{0,1,2,3,4,5,6,7,8,9}
s := arr[2:6] // s = [2,3,4,5]
s := arr[:6]  // s = [0,1,2,3,4,5]
s := arr[6:]  // s = [6,7,8,9]
s := arr[:]   // 0,1,2,3,4,5,6,7,8,9

切片操作超出cap(s)的上限将导致一个panic异常，但是超出len(s)则是意味着扩展了slice

1
2
3
4
5

func TestSlice(t *testing.T) {
	arr := make([]int, 5, 9)
	fmt.Println(arr[5])   // error
	fmt.Println(arr[4:7]) // 扩展
}

x[m:n]切片操作对于字符串则生成一个新字符串，如果x是[]byte的话则生成一个新的[]byte。

2.3. 拼接 slice

… 可变参数列表, 在函数中可以 value ...int 用来解析列表, 在传递参数中使用 arr… 可以将数组解析成参数列表

1

s1 = append(s1[:3], s2[4:]...)

2.4. 如何删除元素?

删除中间的元素

1
2
3
4

	arr := []int{1, 2, 3, 4}
	i := 1
	fmt.Println(append(arr[0:i], arr[i+1:]...))
	fmt.Println(arr[:i+copy(arr[i:], arr[i+1:])])

2.5. 作为函数参数

因为slice值包含指向第一个slice元素的指针 ( 后面介绍 slice 的源码)，因此向函数传递slice将允许在函数内部修改底层数组的元素。

复制一个slice只是对底层的数组创建了一个新的 slice 别名

1
2
3
4
5
6
7
8
9

func change(arr []int){
  arr[0] = 100
}

func main(){
  arr := [5]int{1,2,3,4,5}
  change(arr[:])
  // arr = 100,2,3,4,5
}

Go 语言只有值传递

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func TestSlice2(t *testing.T) {
	s1 := make([]int, 0, 10)

	// Go 语言只有值传递
	appendFunc := func(s []int) {
		s = append(s, 10, 20, 30)
		fmt.Println(s)
	}

	fmt.Println(s1)
	appendFunc(s1)
	fmt.Println(s1)
	fmt.Println(s1[:10])
}

// 结果
// []
// [10 20 30]
// []
// [10 20 30 0 0 0 0 0 0 0]

在上面的例子中，切片值传递过去，使用 append 修改，改变了函数入参 s 的 len 和 cap，但没有改变 s1 的 len 和 cap。

3. 两者区别

  • 数组需要指定长度
  • 数组的长度是固定的, 切片是可变的
  • 作为函数参数，数组是值拷贝，切片…..

4. 看看 slice 的结构

译期间的切片是 cmd/compile/internal/types.Slice 类型的，但是在运行时切片可以由如下的 reflect.SliceHeader 结构体表示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// go@1.16.5     runtime/slice.go
type slice struct {
	array unsafe.Pointer  // 底层数组
	len   int					
	cap   int
}

// reflect/value.go    SliceHeader 是slice 在运行时的表示
type SliceHeader struct {
	Data uintptr  // 连续空间
	Len  int      // 切片长度
	Cap  int      // 容量
}

一个 slice 由三个部分构成：指针、长度和容量。

指针指向第一个slice元素对应的底层数组元素的地址，要注意的是slice的第一个元素并不一定就是数组的第一个元素。

长度对应slice中元素的数目；长度不能超过容量，容量一般是从slice的开始位置到底层数据的结尾位置。

内置的len和cap函数分别返回slice的长度和容量。

slice 不能直接使用 == != 比较

底层数组是可以被多个 slice 同时指向的，因此对一个 slice 的元素进行操作是有可能影响到其他 slice 的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

package main

import "fmt"

func main() {
	slice := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	s1 := slice[2:5]  // 2,3,4
  s2 := s1[2:6:7]   // 4,5,6,7
  // 注意这个7表示是2->7 也就是容量开始和结束位置

	s2 = append(s2, 100) // 4,5,6,7,100
	s2 = append(s2, 200) // 4,5,6,7,100,200

	s1[2] = 20           // 2,3,20

	fmt.Println(s1)      // 2,3,20
	fmt.Println(s2)      // 4,5,6,7,100,200
	fmt.Println(slice)   // 0,1,2,3,20,5,6,7,100,9
}

5. 实例

循环

一种将slice元素循环向左旋转n个元素的方法是三次调用reverse反转函数，第一次是反转开头的n个元素，然后是反转剩下的元素，最后是反转整个slice的元素。（如果是向右循环旋转，则将第三个函数调用移到第一个调用位置就可以了。）

1
2
3
4
5
6

s := []int{0, 1, 2, 3, 4, 5}
// Rotate s left by two positions.
reverse(s[:2])
reverse(s[2:])
reverse(s)
fmt.Println(s) // "[2 3 4 5 0 1]"

扩展用法

s1 对 arr 取值, s2 对 s1 取值"下标越界", 但 slice 是 view 视图, 实际取值是对原数组操作, 还是会得到正确的值, s2 中的 3:5 中 3 的位置是相对于 s1

即 slice 可以向后扩展, 不能越界, 不能向前扩展

1
2
3

s1 = arr[2:6]
s2 = s1[3:5]
// 即  s1[2] = s2[0] ,

对切片使用append

函数原型

1
2

// go@1.16.5  buitltin/builtin.go
func append(slice []Type, elems ...Type) []Type

虽然在扩容的时候 Go 语言一定会生成新的底层数组，但是它也同时生成了新的切片。它是把新的切片作为了新底层数组的窗口，而没有对原切片及其底层数组做任何改动。

请记住，在无需扩容时，append函数返回的是指向原底层数组的新切片，而在需要扩容时，append函数返回的是指向新底层数组的新切片。所以，严格来讲，“扩容”这个词用在这里虽然形象但并不合适。

顺便说一下，只要新长度不会超过切片的原容量，那么使用append函数对其追加元素的时候就不会引起扩容。这只会使紧邻切片窗口右边的（底层数组中的）元素被新的元素替换掉

1
2
3
4
5
6

// s1 = [2,3,4,5]
s1 = s1.append(s1,100)
// s1 = [2,3,4,5,100]
// arr = [0,1,2,3,4,5,100,7,8,9]
// 当 添加后的 cap < 原数组 cap 时, 在原数组上进行替换
// 添加后的 cap > 源数组 cap 时, go 将新分配一个数组

扩容规则

Go 1.18 对规则做了优化，以下规则仅适用于 <= 1.17 的版本，详细请见最新的笔记。

  1. 预估扩容后的容量
    1. oldCap * 2 < cap 则 newCap = cap
    2. 否则
      1. oldLen < 1024 翻倍扩容，即 newCap = oldCap*2
      2. oldLen >= 1024，扩容 1/4，即 newCap = oldCap*1.25
    3. 最后，进行内存对齐

需要多大内存?

内存管理模块会提前申请内存，分成不同规格管理起来。

1
2
3
4
5
6
7

// go@1.16.5 runtime/sizeclasses.go

// 这个值取的是  8* (2,x) ，x 为递增变量
var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}


var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32}

例如通过 append 的得到 []int{1,2,3,4,5} 一共是 5*8=40 字节，查表可知最近接 40 的值是 48，即占用内存 48 字节，cap=6。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

// go@1.16.5  runtine/slice.go
// growslice 处理追加期间的切片增长
func growslice(et *_type, old slice, cap int) slice {
	// ......
  
  // 如果扩容的数据，超过现有 cap 的两倍，则使用扩容数据的长度
	newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		newcap = cap
	} else {
    // 小于 1024 时，2 倍递增
		if old.cap < 1024 {
			newcap = doublecap
		} else {
			// 防止溢出 和 无限循环
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			if newcap <= 0 {
				newcap = cap
			}
		}
	}
  
  
	var overflow bool
	var lenmem, newlenmem, capmem uintptr

	switch {
	case et.size == 1:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		capmem = roundupsize(uintptr(newcap))
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
	case et.size == sys.PtrSize:
		lenmem = uintptr(old.len) * sys.PtrSize
		newlenmem = uintptr(cap) * sys.PtrSize
		capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
		newcap = int(capmem / sys.PtrSize)
	case isPowerOfTwo(et.size):
		var shift uintptr
		if sys.PtrSize == 8 {
			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
		} else {
			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
		}
		lenmem = uintptr(old.len) << shift
		newlenmem = uintptr(cap) << shift
		capmem = roundupsize(uintptr(newcap) << shift)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / et.size)
	}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// go@1.16.5	runtime/msize.go
// 内存对齐函数
func roundupsize(size uintptr) uintptr {
	if size < _MaxSmallSize {
		if size <= smallSizeMax-8 {
			return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
		} else {
			return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
		}
	}
	if size+_PageSize < size {
		return size
	}
	return alignUp(size, _PageSize)
}

// go@1.16.5	runtime/stubs.go
func divRoundUp(n, a uintptr) uintptr {
	// a is generally a power of two. This will get inlined and
	// the compiler will optimize the division.
	return (n + a - 1) / a
}

依然用上面的例子，class_to_size[size_to_class8[ n+a-1 ]] ，得出 48

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 例题
func main() {
    s := []int{5}
    s = append(s, 7)   
    s = append(s, 9)
  
  	// s  5,7,9
    x := append(s, 11)
    // x  5,7,9,11
    y := append(s, 12)
  	// x  5,7,9,12
    fmt.Println(s, x, y)
}

数组反转

1
2
3
4
5

func reverse(s []int) {
    for i, j := 0, len(s)-1; i < j; i++,j-- {
        s[i], s[j] = s[j], s[i]
    }
}

bytes.Equal 切片比较, bytes 提供了 []byte 类型的比较 , 若是其它类型, 自己封装函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func equal(x, y []string) bool {
    if len(x) != len(y) {
        return false
    }
    for i := range x {
        if x[i] != y[i] {
            return false
        }
    }
    return true
}
Go
Licensed under CC BY-NC-SA 4.0
© 2018 - 2024 ixugo
本文阅读量 次， 总访问量 次 ，总访客数 人
Built with Hugo .   Theme Stack designed by Jimmy