数组,切片:‘append’的机制

编程语言最常见的特征之一是数组的概念。 数组看起来像简单的东西,但是在将它添加到语言中时,必须回答许多问题,例如:

  • 固定的size,还是可变的size?
  • size是类型的一部分吗?
  • 多维数组看起来是什么样子的?
  • 空数组代表了什么含义?

以上问题的如何解答,影响着数组在语言中的定位,仅仅是语言的特性还是其设计的核心部分。

在Go的早期发展中,在设计感觉正确之前,花了大约一年时间来决定这些问题的答案。 关键的一步是引入了 切片 ,其建立在固定大小的数组之上,并提供灵活的,可扩展的数据结构。 不过,到目前为止,Go的新手经常会在 切片 的工作方式上遇到问题, 也许是因为来自其他语言的经验使他们戴着有色眼镜来看待 切片

在这篇文章中,将尝试清除混淆。 将通过构建代码来解释 append 内置函数的工作原理以及为什么它如此的工作。

<!– more –>

1 数组

数组是Go中的重要组成部分,但像建筑的基础一样,它们通常隐藏在更可见的组件之下。 这里先简要介绍一下它们,然后再继续讨论 切片 更有趣,强大和突出的特性。

数组在Go程序中不常见,因为数组的大小是其类型的一部分,这限制了其表达力。

var buffer [256]byte

该声明声明了变量 buffer ,其中包含256个字节。 缓冲区的类型包括其大小 1byte 。 512字节的数组将是 2byte , 是不同的类型。

与数组关联的数据就是这样的:一个元素数组。 显然, buffer 在内存中看起来像这样,

buffer: byte byte byte ... 256 times ... byte byte byte

也就是说,变量除了保存256字节的数据之外,没有其他的。 可以使用熟悉的索引语法, buffer3,buffer4等一直到buffer5来访问它的元素。 (索引范围0到255涵盖256个元素) 尝试使用超出该范围的值对buffer进行索引时,会导致程序崩溃。

内置的函数 len ,它返回数组和 切片 以及其他一些数据类型的元素个数。 对于数组,len返回是很清楚明确的。 在上面的例子中, len(buffer) 返回固定值256。

Go的数组是值类型。 数组变量表示整个数组; 它不是指向第一个数组元素的指针(如C中的情况)。 这意味着,当分配或传递数组值时,将产生出其内容的副本。 (为了避免复制,可以传递一个指向数组的指针,但是这是一个指向数组的指针,而不是一个数组)。 思考数组的一种方法是将其作为一种结构体,但是使用索引而不是命名字段:fixed-size的复合值。

数组有特定的使用场景 – 矩阵变换就是很好的例子 - 但是在Go中最常通常的用途就是用作一个 切片 的存储空间。

2 切片: slice header

切片是很容易使用,但是要很好地使用它们,必须明确了解它是什么以及它能做什么。

切片是描述与切片变量本身分开存储的数组连续部分的数据结构。 切片不是数组。 切片描述一个数组的一个片段。

给定上一节的 buffer 数组变量,可以通过对数组进行切片来创建描述元素100到150 (确切地说,包括100到149)的切片:

var slice []byte = buffer[100:150]

变量 slice 具有类型 []byte ,读作 slice of bytes , 并被初始化为数组从元素100(包括)到150(排他)的切片。 更惯用的语法,删除类型,由初始化表达式来设置类型:

var slice = buffer[100:150]

在函数中可使用更短的声明形式:

slice := buffer[100:150]

这个 slice 变量究竟是什么? 这不完全是一个完整的故事, 但是现在可把切片看作一个有两个元素的小数据结构:一个长度和一个指向数组元素的指针。 你可想到,其实幕后就是如此构造:

1
2
3
4
5
6
7
8
9
type sliceHeader struct {
Length int
ZerothElement *byte
}

slice := sliceHeader{
Length: 50,
ZerothElement: &buffer[100],
}

当然这只是一个示例。 尽管这段代码片段已表明 sliceHeader 结构对程序员是不可见的, 元素指针的类型取决于元素的类型,但这给出了机制的共同之处。

当目前为止只做了数组的切片操作,但是切片上也可作切片操作:

slice2 := slice[5:10]

像以前一样,这个操作创建一个新的切片,在这种情况下,原始切片的元素5到9(包括),意味着原始阵列的元素105到109。 slice2变量的底层sliceHeader结构如下所示:

1
2
3
4
slice2 := sliceHeader{
Length: 5,
ZerothElement: &buffer[105],
}

注:此 header 仍然指向相同的底层数组,存储在 buffer 变量中。

也可以二次切片,也就是说切片并将结果存储回原来的切片结构。

slice = slice[5:10]

经过上面的二次切片,slice变量的sliceHeader结构与slice2变量的一样。 可能会经常看到二次切片,例如截断切片。 此语句删除了我们的切片的第一个和最后一个元素:

slice = slice[1:len(slice)-1]

经过上面的而且切片后, sliceHeader 如下所示:

1
2
3
4
slice := sliceHeader{
Length: 3,
ZerothElement: &buffer[104],
}

你会经常听到有经验的Go程序员谈论 slice header ,因为它真的是存储在切片变量中。 例如,当你调用将切片作为参数的函数(如bytes.IndexRune)时,该 header 就是传递给该函数的参数。 在下面调用中, slice 是入参,但事实上却是 slice header

slashPos := bytes.IndexRune(slice, '/')

slice header 中还有一个数据项,会在下面讨论,但首先看看当你使用 slice 编程时, slice header 的存在意味着什么。

3 切片作为函数的入参

很重要的一点,一个slice包含一个指针,但它本身就是一个值。 是一个保存指针和长度的结构体的值, 不是指向结构体的指针。

当在前面的例子中调用 IndexRune 时,传递了一个 slice header 的副本。 这样的方式有重要的副作用。

思考下面这个简单的函数:

1
2
3
4
5
func AddOneToEachElement(slice []byte) {
for i := range slice {
slice[i]++
}
}

迭代一个切片的索引(使用范围循环),增加其元素。 调用如下:

1
2
3
4
5
6
7
8
9
10
func main() {
var buffer [256]byte
slice := buffer[10:20]
for i := 0; i < len(slice); i++ {
slice[i] = byte(i)
}
fmt.Println("before", slice)
AddOneToEachElement(slice)
fmt.Println("after", slice)
}

即使 slice header 通过值传递, header 包含指向数组元素的指针,因此原始 header 和传递给该函数的标题的副本都描述相同的数组。 因此,当函数返回时,可以通过原始 slice 变量看到被修改的元素。

slice header 真的只是传递了副本,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
func SubtractOneFromLength(slice []byte) []byte {
slice = slice[0 : len(slice)-1]
return slice
}

func main() {
var buffer [256]byte
slice := buffer[10:20]
fmt.Println("Before: len(slice) =", len(slice))
newSlice := SubtractOneFromLength(slice)
fmt.Println("After: len(slice) =", len(slice))
fmt.Println("After: len(newSlice) =", len(newSlice))
}

这里看到一个slice参数的内容可以被一个函数修改,但是它的 header 不能。 存储在 slice 变量中的长度不会通过对函数的调用进行修改,因为函数传递了 slice header 的副本,而不是原始的变量。 因此,如果要编写一个修改 header 的函数,那么必须将其作为结果参数返回,就像上面所做的那样。 slice 变量不变,但返回的值具有新的长度,然后将其存储在 newSlice 中。

4 切片指针:Method receivers

另外一个通过函数调用修改 slice header 的方式时传递 header 的指针。下面上买示例的一个变种:

1
2
3
4
5
6
7
8
9
10
11
12
func PtrSubtractOneFromLength(slicePtr *[]byte) {
slice := *slicePtr
*slicePtr = slice[0 : len(slice)-1]
}

func main() {
var buffer [256]byte
slice := buffer[10:20]
fmt.Println("Before: len(slice) =", len(slice))
PtrSubtractOneFromLength(&slice)
fmt.Println("After: len(slice) =", len(slice))
}

这个例子看起来很笨拙,特别是处理了需要一个额外的间接引用,但这是对于指向slice的指针而言,常见的处理方式。 对于修改 slice 使用指针 receiver 是惯用的。

假设现在希望在一个切片上有一个方法,以最后的斜杠截断它。 可以这样写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type path []byte

func (p *path) TruncateAtFinalSlash() {
i := bytes.LastIndex(*p, []byte("/"))
if i >= 0 {
*p = (*p)[0:i]
}
}

func main() {
pathName := path("/usr/bin/tso") // Conversion from string to path.
pathName.TruncateAtFinalSlash()
fmt.Printf("%s\n", pathName)
}

如果运行此示例,将看到它正常工作,更新调用者中的切片。

另一方面,如果想写一个路径的方法,在路径中的ASCII字母(忽略非英文名称)转变为大写,该方法调用者可以是一个值, 因为值 receiver 仍将指向相同的底层阵列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type path []byte

func (p path) ToUpper() {
for i, b := range p {
if 'a' <= b && b <= 'z' {
p[i] = b + 'A' - 'a'
}
}
}

func main() {
pathName := path("/usr/bin/tso")
pathName.ToUpper()
fmt.Printf("%s\n", pathName)
}

这里, ToUpper 方法在for范围构造中使用两个变量来捕获索引和切片元素。 这种形式的循环避免了在身体中多次使用 p[i]

5 容量

下面函数扩展整数切片:

1
2
3
4
5
6
func Extend(slice []int, element int) []int {
n := len(slice)
slice = slice[0 : n+1]
slice[n] = element
return slice
}

调用如下:

1
2
3
4
5
6
7
8
func main() {
var iBuffer [10]int
slice := iBuffer[0:0]
for i := 0; i < 20; i++ {
slice = Extend(slice, i)
fmt.Println(slice)
}
}

观察切片怎么增长直到…

现在是时候谈谈 slice header 的第三个字段:它的容量。 除了数组指针和长度之外,slice头还存储其容量:

1
2
3
4
5
type sliceHeader struct {
Length int
Capacity int
ZerothElement *byte
}

容量字段记录底层数组实际有多少空间; 它是长度可以达到的最大值。 试图将切片超越其容量,将超出数组的极限,并将触发 panic

上面示例中 slice 初始语句如下:

slice := iBuffer[0:0]

它的 header 如下所示:

1
2
3
4
5
slice := sliceHeader{
Length: 0,
Capacity: 10,
ZerothElement: &iBuffer[0],
}

容量字段等于底层数组的长度减去切片的第一个元素在数组中的索引值。如果需要查询切片的容量,请使用内置函数 cap

1
2
3
if cap(slice) == len(slice) {
fmt.Println("slice is full!")
}

6 Make

如果想要超越其容量,那怎么办? 不能这么做! 根据定义,容量是增长的极限。 但是可以通过分配一个新数组,复制数据和修改切片来指向新数组来实现相同的结果。

可以使用内置函数来重新分配一个更大的数组,然后分割它,但是更简单的是使用 make 内置函数。 它分配一个新数组,并创建一个 slice header 来描述它。 make 函数有三个参数:slice的类型,它的初始长度和它的容量,容量是分配保存slice数据的数组的长度。 这个调用创建一个长度为10的片段,还有5个(15-10)的空间,你可以通过运行它看到:

1
2
slice := make([]int, 10, 15)
fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice))

下面代码将 int slice 的容量加倍,但是它的长度保持不变:

1
2
3
4
5
6
7
8
slice := make([]int, 10, 15)
fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice))
newSlice := make([]int, len(slice), 2*cap(slice))
for i := range slice {
newSlice[i] = slice[i]
}
slice = newSlice
fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice))

运行此代码之后,在另一个重新分配之前,切片有了更多的空间。

当创建切片时,长度和容量通常是一样的。 该内置函数有一个这种常见情况的缩写。 length参数默认为容量,此您可以将其设置为相同的值。

gophers := make([]Gopher, 10)

gophers slice 有相同的长度和容量,都为10。

7 复制

上面的示例中,当切片的容量加倍时,需要写了一个循环来将旧数据复制到新的切片。 Go有一个内置的函数 copy ,使这更容易。 它的参数是两个切片,它将数据从右边的参数复制到左边的参数。 示例重写为使用 copy

1
2
newSlice := make([]int, len(slice), 2*cap(slice))
copy(newSlice, slice)

copy 函数很智能。 它只复制它可以复制,会关注两个 slice 参数的长度。 换句话说,它复制的元素的数量是两个切片中长度的最小值。 此外,copy返回一个整数值,复制的元素数量,虽然并不总是需要检查。

当源和目的地有重叠时,/copy/ 函数也可以正确的,这意味着它可以用于在单个切片中移动项目。 以下是使用 copy 将值插入片段中间的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
// Insert inserts the value into the slice at the specified index,
// which must be in range.
// The slice must have room for the new element.
func Insert(slice []int, index, value int) []int {
// Grow the slice by one element.
slice = slice[0 : len(slice)+1]
// Use copy to move the upper part of the slice out of the way and open a hole.
copy(slice[index+1:], slice[index:]) // slice[index:] 等价于 slice[index:len(slice)]
// Store the new value.
slice[index] = value
// Return the result.
return slice
}

上面函数有几件事要注意。 首先,当然,它必须返回更新的切片,因为它的长度已经改变。 其次,它使用方便的速记。表达式:

slice[i:]

等价于:

slice[i:len(slice)]

此外,虽然还没有使用技巧,但也可以省略一个切片表达式的第一个元素; 它默认为零。因此

slice[:]

仅仅代表 slice 自身, 这在切片化数组时很有用。下面表达式切片整个数组:

array[:]

调用 Insert 函数如下:

1
2
3
4
5
6
7
8
9
func main() {
slice := make([]int, 10, 20) // Note capacity > length: room to add element.
for i := range slice {
slice[i] = i
}
fmt.Println(slice)
slice = Insert(slice, 5, 99)
fmt.Println(slice)
}

8 Append: 示例

往前回顾下,写的一个 Extend 函数,它将一个切片扩展。 然而,它是错误的,因为如果切片的容量太小,该函数将崩溃。 ( Insert 示例有相同的问题。) 现在已经准备好了修复这些的知识,所以现在重新编写一个强大的 Extend 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
func Extend(slice []int, element int) []int {
n := len(slice)
if n == cap(slice) {
// Slice is full; must grow.
// We double its size and add 1, so if the size is zero we still grow.
newSlice := make([]int, len(slice), 2*len(slice)+1)
copy(newSlice, slice)
slice = newSlice
}
slice = slice[0 : n+1]
slice[n] = element
return slice
}

在上面情况下,函数返回切片尤为重要,因为当它重新分配生成的切片时,会指向一个完全不同的数组。 下面这段代码,用于说明切片填满时会发生什么:

1
2
3
4
5
6
7
8
func main() {
slice := make([]int, 0, 5)
for i := 0; i < 10; i++ {
slice = Extend(slice, i)
fmt.Printf("len=%d cap=%d slice=%v\n", len(slice), cap(slice), slice)
fmt.Println("address of 0th element:", &slice[0])
}
}

注意当初始数组5被填满时的重新分配。 当分配新数组时,第零个元素的地址和容量都会发生变化。

以强大的Extend功能为指导,可以编写一个更好的功能,能支持多个元素来扩展切片。 为此,当调用函数时,使用Go的原生特性将函数的参数列表转换为切片。 也就是说,使用Go的可变参数列表。

函数命名为 Append 。 对于第一个版本,重复调用Extend,以使可变函数参数的机制清晰明了。 Append的签名:

func Append(slice []int, items ...int) []int

Append 需要一个参数,一个 slice ,后跟零个或多个 int 参数。 就 Append 的实现而言,这些参数正好是int的切片,可以看到:

1
2
3
4
5
6
7
8
// Append appends the items to the slice.
// First version: just loop calling Extend.
func Append(slice []int, items ...int) []int {
for _, item := range items {
slice = Extend(slice, item)
}
return slice
}

注意范围循环遍历items参数的元素,暗含了类型[]int。 还要注意使用空白标识符来舍弃循环中的索引,在这种情况下不需要这个索引。

Append 使用如下:

1
2
3
4
5
6
func main() {
slice := []int{0, 1, 2, 3, 4}
fmt.Println(slice)
slice = Append(slice, 5, 6, 7, 8)
fmt.Println(slice)
}

不仅可以 append 元素,还可以 append 另外一个切片,如下所示:

1
2
3
4
5
slice1 := []int{0, 1, 2, 3, 4}
slice2 := []int{55, 66, 77}
fmt.Println(slice1)
slice1 = Append(slice1, slice2...) // The '...' is essential!
fmt.Println(slice1)

当然, Append 函数优化实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Append appends the elements to the slice.
// Efficient version.
func Append(slice []int, elements ...int) []int {
n := len(slice)
total := len(slice) + len(elements)
if total > cap(slice) {
// Reallocate. Grow to 1.5 times the new size, so we can still grow.
newSize := total*3/2 + 1
newSlice := make([]int, total, newSize)
copy(newSlice, slice)
slice = newSlice
}
slice = slice[:total]
copy(slice[n:], elements)
return slice
}

注意使用 copy 两次,一次将切片数据移动到新分配的内存,然后将附加的切片数据复制到旧数据的末尾。

行为和上面快速实现一样:

1
2
3
4
5
slice1 := []int{0, 1, 2, 3, 4}
slice2 := []int{55, 66, 77}
fmt.Println(slice1)
slice1 = Append(slice1, slice2...) // The '...' is essential!
fmt.Println(slice1)

9 Append:内建函数

目前我们 get 到了 append 内置函数设计的动机了。 它完全和上面定义的/Append/ 示例的函数有同样的功能,同等效率,但它适用于任何切片类型。

Go的一个弱点是任何通用类型的操作都必须由运行时提供。 有一天可能会改变,但是现在,为了使切片更容易使用,Go提供了一个内置的通用 append 函数。 它与上面的int切片版本相同,但适用于任何切片类型。

记住,由于 slice header 总是通过调用 append 来更新,所以需要在调用后保存返回的切片。 实际上,编译器不会让你调用 append 而不保存结果。

使用示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Create a couple of starter slices.
slice := []int{1, 2, 3}
slice2 := []int{55, 66, 77}
fmt.Println("Start slice: ", slice)
fmt.Println("Start slice2:", slice2)

// Add an item to a slice.
slice = append(slice, 4)
fmt.Println("Add one item:", slice)

// Add one slice to another.
slice = append(slice, slice2...)
fmt.Println("Add one slice:", slice)

// Make a copy of a slice (of int).
slice3 := append([]int(nil), slice...)
fmt.Println("Copy a slice:", slice3)

// Copy a slice to the end of itself.
fmt.Println("Before append to self:", slice)
slice = append(slice, slice...)
fmt.Println("After append to self:", slice)

请仔细考虑该例子的最后一行内容,以了解切片的设计如何使这个简单的调用成功。

10 Nil

另外,通过新学习到的知识,可以看到一个零切片的表示形式。 当然,它是 slice header 的零值:

1
2
3
4
5
sliceHeader{
Length: 0,
Capacity: 0,
ZerothElement: nil,
}

或者

sliceHeader{}

关键的细节之处就是元素指针为 nil 。 切片被创建

array[0:0]

长度为0,但是元素指针不为空,所以不是一个 nil 切片。

应该清楚的是,一个空切片可以增长(假设它具有非零容量),但是一个 nil 切片没有数组将数值填入,并且永远不会增长,甚至连一个元素都不能。

也就是说,/nil/ 切片在功能上等同于零长度切片,即使它没有指向。 它的长度为零,并可以附加到分配。 例如,上面示例中的一行,通过追加到一个 nil 切片来复制一个切片。

11 字符串

在切片的上下文中,这里简要介绍一下Go的字符串部分。

字符串实际上非常简单:它只是只读字节的切片,有一点源于语言的额外的语法支持。

因为它们是只读的,所以不需要容量(你也不能扩展它们),但是大多数情况下,可以像只读字节片一样对待它们。

对于初学者,可以对它们进行索引以访问单个字节

slash := "/usr/ken"[0] // yields the byte value '/'.

可以分割一个字符串来获取一个子字符串:

usr := "/usr/ken"[0:4] // yields the string "/usr"

现在应该清楚了,当裁剪一个字符串时,幕后发生了什么。

也可以用正常的字节切片,并通过简单的转换创建一个字符串:

str := string(slice)

反向转换也是可以的:

slice := []byte(usr)

字符串下面的数组从视图中隐藏; 除了通过字符串之外,没有办法访问其内容。 这意味着当我们进行这些转换之一时,必须复制数组。 在这些转换中的任何一个之后,对字节片下面的数组的修改不会影响相应的字符串。

字符串这种切片式设计的一个重要结果是创建子字符串非常高效。 所有需要发生的事情是创建一个两个字的字符串头。 由于字符串是只读的,原始字符串和由slice操作生成的字符串可以安全地共享相同的数组。

一个历史备注:字符串的最早实现始终被分配,但是当切片被添加到语言中时, 它们提供了一个有效的字符串处理模型。 一些基准测试结果都展示出巨大的加速。

当然,还有更多的字符串知识,一个 单独的博客文章 更深入地介绍了它们。

12 总结

要了解切片是如何工作的,它有助于了解它们是如何实现的。 有一些数据结构, slice header ,即与切片变量相关联的条目, 该 header 描述了单独分配的数组的一部分。 当我们传递切片值时, header 被复制,但它指向的数组始终是共享的。

一旦了解它们如何工作,切片就变得不仅易于使用,而且功能强大而富有表现力, 特别是在 copyappend 内置函数的帮助下。

13 延伸阅读

在Go里面有很多关于切片的使用场景。 如前所述 Slice Tricks" Wiki page页面有很多示例。 Go Slices博客文章使用清晰的图表描述了内存布局细节。 Russ Cox的Go Data Structures文章包括对片的讨论以及Go的其他内部数据结构。

有更多的材料可用,但是了解切片的最佳方式是使用它们。

Footnotes:

1

DEFINITION NOT FOUND.

2

DEFINITION NOT FOUND.

3

DEFINITION NOT FOUND.

4

DEFINITION NOT FOUND.

5

DEFINITION NOT FOUND.

Last Updated 2017-05-27 Sat 10:38.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)