A. Question
Go 语言中有哪三种一等公民的容器类型?它们各自有什么特点?
切片和数组在内存布局和赋值语义上有何区别?
如何高效地遍历一个大数组或大切片?
如何在 Go 中实现集合(Set)类型?
对于切片 a 和 b,在什么情况下 append (a, b…) 会导致 a 和 b 共享底层数组?什么情况下不会共享?
切片高效操作的原则有哪些?
下面的代码有什么问题?
|
|
B. 容器类型和容器值概述
Go 语言中有三种主要的容器类型:数组、切片和映射。每种容器类型用来存储一组相同类型的元素,并可以通过一种键值机制来访问这些元素。在数组和切片中,键值是整数索引,而映射可以使用任何可比较类型作为键值。数组是固定长度的,而切片和映射是动态的。
例如:
|
|
C. 无名容器类型的字面表示形式
Go 中使用特定的语法表示容器类型:
- 数组:
[N]T
,N
为长度,T
为元素类型 - 切片:
[]T
,T
为元素类型 - 映射:
map[K]T
,K
为键类型,T
为值类型
例如:
|
|
D. 容器字面量的表示形式
容器字面量用于定义和初始化容器。可以使用组合字面量形式 T{...}
来创建容器。
例子:
|
|
E. 容器类型零值的字面量表示形式
数组类型的零值可以表示为 A{}
,而切片和映射类型的零值是 nil
。
例如:
|
|
F. 容器字面量是不可寻址的但可以被取地址
虽然容器字面量不可寻址,但是可以使用取地址操作符 &
来获取它们的地址。
例如:
|
|
G. 内嵌组合字面量可以被简化
在组合字面量中,内嵌组合字面量可以省略类型部分和取地址符号。
例如:
|
|
H. 容器值的比较
映射和切片不能直接比较,只能和 nil
比较。数组可以比较,只要元素类型可比较。
例如
|
|
I. 查看容器值的长度和容量
可以使用 len
和 cap
函数查看容器的长度和容量。数组的长度和容量相等,切片的容量不小于其长度。
例如:
|
|
切片值的容量和长度不一定相等
J. 读取和修改容器的元素
可以通过索引或键访问和修改容器的元素。
例如:
|
|
K. 重温一下切片的内部结构
切片是一个包含指针、长度和容量的结构。它指向一个底层数组的子集,能够动态调整大小。
例如:
|
|
为了更好的理解和解释切片类型和切片值,我们最好对切片的内部结构有一个基本的印象。在上一篇文章值部中,我们已经了解到官方标准编译器对切片类型的内部定义大致如下:
1 2 3 4 5
type _slice struct { elements unsafe. Pointer // 引用着底层存储在间接部分上的元素 len int // 长度 cap int // 容量 }
虽然其它编译器中切片类型的内部结构可能并不完全和官方标准编译器一致,但应该大体上是相似的。下面的解释均基于官方标准编译器对切片类型的内部定义。
上面展示的切片的内部定义为切片的直接部分的定义。直接部分的
len
字段表示一个切片当前存储了多少个元素;直接部分的cap
表示一个切片的容量。下面这张图描绘了一个切片值的内存布局。Responsive Image 尽管一个切片值的底层元素部分可能位于一个比较大的内存片段上,但是此切片值只能感知到此内存片段上的一个子片段。比如,上图中的切片值只能感知到灰色的子片段。
在上图中,从下标
len
(包含)到下标cap
(不包含)对应的元素并不属于图中所示的切片值。它们只是此切片之中的一些冗余元素槽位,但是它们可能是其它切片(或者数组)值中的有效元素。下一节将要介绍如何通过调用内置
append
函数来向一个基础切片添加元素而得到一个新的切片。这个新的结果切片可能和这个基础切片共享起始元素,也可能不共享,具体取决于基础切片的容量(以及长度)和添加的元素数量。当一个切片被用做一个
append
函数调用中的基础切片,
- 如果添加的元素数量大于此(基础)切片的冗余元素槽位的数量,则一个新的底层内存片段将被开辟出来并用来存放结果切片的元素。这时,基础切片和结果切片不共享任何底层元素。
- 否则,不会有底层内存片段被开辟出来。这时,基础切片中的所有元素也同时属于结果切片。两个切片的元素都存放于同一个内存片段上。
下下一节将展示一张包含了上述两种情况的图片。
一些其它切片操作也可能会造成两个切片共享底层内存片段的情况。这些操作将在后续章节逐一介绍。
注意,一般我们不能单独修改一个切片值的某个内部字段,除非使用反射或者非类型安全指针。换句话说,一般我们只能通过将其它切片赋值给一个切片来同时修改这个切片的三个字段。
L. 容器赋值
映射和切片赋值会共享底层数据,而数组赋值会复制元素。 前两个是引用类型,后一个是值类型的。
例如:
|
|
L.1. 添加和删除容器元素
映射可以直接添加和删除元素;切片可以使用 append
添加元素,删除时需要组合使用 append
和子切片。
例如:
|
|
在 Go 语言中,append
函数是用于向切片中添加元素的内置函数。Go 并没有提供直接删除切片元素的内置方法,因此我们通常需要结合 append
和子切片语法来实现删除操作。以下是对 append
函数的详细解释和示例。
L.1.1. append
函数的使用
append
函数是一个变长参数函数,允许我们向切片中添加一个或多个元素。它的基本用法如下:
|
|
在上面的例子中:
s0
是一个初始切片,包含元素[2, 3, 5]
。s1
是通过向s0
添加元素7
得到的新切片。s2
是通过向s1
添加元素11
和13
得到的新切片。
L.1.2. 变长参数和切片展开
append
函数的第二个参数是变长参数,可以通过两种方式传递:
- 直接传递多个元素:如
append(s1, 11, 13)
。 - 使用切片展开:如
append(s0, s0...)
,这相当于将s0
中的所有元素逐个传递给append
。
在例子中,第 14 行的 append(s0, s0...)
等价于 append(s0, s0[0], s0[1], s0[2])
。
L.1.3. 内存分配和共享
- 当
append
需要为结果切片分配新的内存时,结果切片的容量通常是基础切片容量的两倍,以便为将来的append
操作提供足够的空间。 - 如果基础切片有足够的冗余空间,
append
不会分配新的内存,而是直接在现有空间上操作。
在示例中:
s1
的创建需要新的内存,因为s0
没有足够的空间来容纳新元素。s2
的创建不需要新的内存,因为s1
有足够的冗余空间。
在 Go 语言中,append
函数用于向切片中添加元素。当我们使用 append
向切片添加元素时,Go 语言的运行时会根据需要自动调整切片的容量。具体来说,append
函数的行为如下:
为什么 s1 的容量变成了 6 而不是 4?
在例子中:
|
|
初始切片
s0
:s0
的长度和容量都是 3,因为它包含三个元素[2, 3, 5]
。使用
append
添加元素:当你使用append(s0, 7)
向s0
添加一个新元素时,Go 语言会检查s0
的容量是否足够容纳新元素。在这个例子中,s0
的容量是 3,而我们需要存储 4 个元素(原有的 3 个加上新添加的 1 个),因此容量不足。扩展容量:由于容量不足,Go 语言会为
s1
分配新的内存空间。Go 的标准实现通常会将容量扩展为当前容量的两倍,以便为将来的append
操作提供足够的空间。因此,s1
的容量变成了 6,而不是 4。
内存分配策略
容量扩展:当切片的容量不足以容纳新元素时,Go 语言会分配一个更大的底层数组。通常情况下,==新的容量是旧容量的两倍==。这种策略是为了减少频繁的内存分配操作,提高性能。
共享底层数组:如果
append
操作不需要扩展容量,新的切片将共享原始切片的底层数组。
L.1.4. 示例
|
|
|
|
这张图片展示了 Go 语言中切片操作 append
后,切片如何共享底层数组,以及内存分配的变化情况。
切片关系和内存状态
s0 和 s3:
s0
和s3
共享同一个底层数组,长度为 3,容量为 3。- 当
s0[0]
被修改为99
时,s3[0]
也同步为99
,因为它们共享相同的底层数组。
s1:
s1
是在s0
上append
一个元素7
后生成的。- 由于
s0
的容量不足以容纳新元素,Go 分配了一个新的底层数组,容量为 6。 s1
的长度变为 4,容量变为 6。
s2:
s2
是在s1
上append
两个元素11
和13
后生成的。s1
的剩余容量足够,因此s2
继续使用s1
的底层数组。s2
的长度变为 6,容量仍为 6。
s4:
s4
是通过append(s0, s0...)
操作生成的。- 这意味着
s0
的所有元素被复制到一个新的位置,并追加到s0
的末尾。 s4
的长度变为 6,容量为 6,使用了新的底层数组。
L.1.5. 实际编程中的用法
在实际编程中,我们通常将 append
的结果重新赋值给基础切片,以便更新切片的内容和容量。例如:
|
|
在这个例子中,切片 s
逐步添加了 "map"
和 "channel"
,并且容量在需要时自动扩展。
L.1.6. 注意事项
截至 Go 1.22,append
函数的第一个参数不能是类型不确定的 nil
。这意味着我们不能直接对一个未初始化的切片使用 append
,而是需要先将其初始化为一个空切片或使用 make
函数。
L.2. 从数组或者切片派生切片(取子切片)
可以从数组或切片派生出子切片,子切片和原数组或切片共享底层数组。
Go 中有两种取子切片的语法形式(假设 baseContainer
是一个切片或者数组):
|
|
上面所示的双下标形式等价于下面的三下标形式:
|
|
所以双下标形式是三下标形式的特例。在实践中,双下标形式使用得相对更为广泛。
(注意:三下标形式是从 Go 1.2 开始支持的。)
上面所示的取子切片表达式的语法形式中的下标必须满足下列关系,否则代码要么编译不通过,要么在运行时刻将造成恐慌。
|
|
- 如果下标
low
为零,则它可被省略。此条规则同时适用于双下标形式和三下标形式。 - 如果下标
high
等于len(baseContainer)
,则它可被省略。此条规则同时只适用于双下标形式。 - 三下标形式中的下标
max
在任何情况下都不可被省略。
比如,下面的子切片表达式都是相互等价的:
|
|
M. 使用内置 make 函数来创建切片和映射
假设 M
是一个映射类型并且 n
是一个整数,我们可以用下面的两种函数调用来各自生成一个类型为 M
的映射值。
|
|
第一个函数调用形式创建了一个可以容纳至少 n
个条目而无需再次开辟内存的空映射值。第二个函数调用形式创建了一个可以容纳一个小数目的条目而无需再次开辟内存的空映射值。此小数目的值取决于具体编译器实现。
注意:第二个参数 n
可以为负或者零,这时对应的调用将被视为上述第二种调用形式。
假设 S
是一个切片类型,length
和 capacity
是两个非负整数,并且 length
小于等于 capacity
,我们可以用下面的两种函数调用来各自生成一个类型为 S
的切片值。length
和 capacity
的类型必须均为整数类型(两者可以不一致)。
|
|
第一个函数调用创建了一个长度为 length
并且容量为 capacity
的切片。第二个函数调用创建了一个长度为 length
并且容量也为 length
的切片。
使用 make
函数创建的切片中的所有元素值均被初始化为(结果切片的元素类型的)零值。
下面是一个展示了如何使用 make
函数来创建映射和切片的例子:
|
|
N. 使用内置 new 函数来创建容器值
new
函数通常用于创建指针,创建的值是零值。
例如:
|
|
O. 容器元素的可寻址性
数组中的元素是可寻址的,切片中的元素也是可寻址的,映射的元素不可寻址。
例如:
|
|
O.1. 疑问(暂且存疑)
在上一篇文章值部中,我们了解到每个数组或者结构体值都是仅含有一个直接部分。所以
- 如果一个映射类型的元素类型为一个结构体类型,则我们无法修改此映射类型的值中的每个结构体元素的单个字段。我们必须整体地同时修改所有结构体字段。
- 如果一个映射类型的元素类型为一个数组类型,则我们无法修改此映射类型的值中的每个数组元素的单个元素。我们必须整体地同时修改所有数组元素。
一个例子:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
package main import "fmt" func main () { type T struct{age int} mt := map[string]T{} mt["John"] = T{age: 29} // 整体修改是允许的 ma := map[int][5]int{} ma[1] = [5]int{1: 789} // 整体修改是允许的 // 这两个赋值编译不通过,因为部分修改一个映射 // 元素是非法的。这看上去确实有些反直觉。 /* ma[1][1] = 123 // error mt["John"]. age = 30 // error */ // 读取映射元素的元素或者字段是没问题的。 fmt.Println (ma[1][1]) // 789 fmt.Println (mt["John"]. age) // 29 }
为了让上例中的两行编译不通过的两行赋值语句编译通过,欲修改的映射元素必须先存放在一个临时变量中,然后修改这个临时变量,最后再用这个临时变量整体覆盖欲修改的映射元素。比如:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
package main import "fmt" func main () { type T struct{age int} mt := map[string]T{} mt["John"] = T{age: 29} ma := map[int][5]int{} ma[1] = [5]int{1: 789} t := mt["John"] // 临时变量 t.age = 30 mt["John"] = t // 整体修改 a := ma[1] // 临时变量 a[1] = 123 ma[1] = a // 整体修改 fmt.Println (ma[1][1], mt["John"]. age) // 123 30 }
注意:刚提到的这个限制可能会在以后被移除。
P. 使用内置 copy
函数来复制切片元素
copy
函数用于将一个切片的元素复制到另一个切片。这两个切片的类型的底层类型必须相同。
例如:
|
|
Q. 遍历容器元素
使用 for-range
语法遍历容器元素。
例如:
|
|
- 被遍历的容器值是
aContainer
的一个副本。注意,只有aContainer
的直接部分被复制了。此副本是一个匿名的值,所以它是不可被修改的。
- 如果
aContainer
是一个数组,那么在遍历过程中对此数组元素的修改不会体现到循环变量中。原因是此数组的副本(被真正遍历的容器)和此数组不共享任何元素。- 如果
aContainer
是一个切片(或者映射),那么在遍历过程中对此切片(或者映射)元素的修改将体现到循环变量中。原因是此切片(或者映射)的副本和此切片(或者映射)共享元素(或条目)。- 在遍历中的每个循环步,
aContainer
副本中的一个键值元素对将被赋值(复制)给循环变量。所以对循环变量的直接部分的修改将不会体现在aContainer
中的对应元素中。 (因为这个原因,并且for-range
循环是遍历映射条目的唯一途径,所以最好不要使用大尺寸的映射键值和元素类型,以避免较大的复制负担。)
R. 更多切片操作
Go 没有提供内置的切片克隆、插入和删除操作,需要通过组合已有功能实现。
例如,克隆切片:
|
|
S. 用映射来模拟集合(set)
可以使用 map[K]struct{}
模拟集合,因为 struct{}
不占用内存。
例如:
|
|
T. 上述各种容器操作内部都未同步
容器操作内部未进行同步处理,多个协程并发读取容器是安全的,但并发修改时需要同步机制。
这就是 Go 语言中数组和切片的主要特性、相似性和差异。通过这些例子和解释,希望能帮助您更好地理解这些概念。如果有任何进一步的问题
U. 对比
当然,以下是对 Go 语言中数组、切片以及映射的用法和特点的详细解释,并将通过表格对比它们的相同和不同之处。
U.1. 数组
- 定义:数组是一个固定长度的元素序列,所有元素类型相同。
- 特点:
- 长度固定,声明时就决定,无法更改。
- 存储在连续的内存空间中。
- 值类型,赋值时会拷贝整个数组。
- 支持索引访问,使用零基索引。
- 可比较(前提是元素类型可比较)。
- 用法示例:
1 2
var arr [3]int = [3]int{1, 2, 3} fmt.Println(arr[0]) // 输出: 1
U.2. 切片
- 定义:切片是一个动态长度的序列,它是对底层数组的一个引用。
- 特点:
- 动态长度,可以增长和缩减。
- 引用类型,赋值时共享底层数组。
- 支持索引访问,使用零基索引。
- 不可比较。
- 包含指向底层数组的指针、长度和容量。
- 用法示例:
1 2 3
s := []int{1, 2, 3} s = append(s, 4) fmt.Println(s) // 输出: [1 2 3 4]
U.3. 映射
- 定义:映射是一种无序的键值对集合。
- 特点:
- 动态长度,键值对可随时增删。
- 键类型必须是可比较类型。
- 引用类型,赋值时共享底层数据。
- 不可比较。
- 用法示例:
1 2 3 4
m := map[string]int{"Go": 2009, "C": 1972} m["Python"] = 1991 delete(m, "C") fmt.Println(m) // 输出: map[Go:2009 Python:1991]
U.4. 表格对比数组、切片和映射
特性 | 数组 | 切片 | 映射 |
---|---|---|---|
长度 | 固定 | 动态 | 动态 |
类型 | 值类型 | 引用类型 | 引用类型 |
索引类型 | 整数 | 整数 | 任意可比较类型 |
内存 | 连续存储 | 指向底层数组的片段 | 散列存储,通常非连续 |
比较 | 支持(元素可比较时) | 不支持 | 不支持 |
增长 | 不支持 | 支持(使用 append ) | 支持(增加键值对) |
初始值 | 用零值初始化 | nil 或用零值初始化 | nil 或用零值初始化 |
遍历 | 支持 for 和 range | 支持 for 和 range | 支持 range |
U.5. 例子总结
数组:适用于固定大小的场景,需时刻知道其容量,定义后无法更改。
1 2
var nums [3]int = [3]int{10, 20, 30} fmt.Println(nums[1]) // 输出: 20
切片:更灵活,适用于需要动态添加或删除元素的场景。
1 2 3
fruits := []string{"Apple", "Banana"} fruits = append(fruits, "Cherry") fmt.Println(fruits) // 输出: [Apple Banana Cherry]
映射:用于存储键值对,适合需要快速查找的场景。
1 2 3
ages := map[string]int{"Alice": 25, "Bob": 30} ages["Charlie"] = 35 fmt.Println(ages) // 输出: map[Alice:25 Bob:30 Charlie:35]