数组、切片(以及字符串): append内置函数的运作机制

介绍

数组是编程语言中最常用到的功能之一. 数组看起来是比较简单,但在一个语言要实现一个数组的时候,有些问题必须要解决,如::

• 固定大小或可变大小?
• 是类型的一部分?
• 多为数组的模型?
• 空数组的意义?

这些问题的解决影响着数组仅是语言的一个功能还是其设计的核心部分.

你要爪子
翻译于 1年前

0人顶

在早期的Go语言发展中,在设计数组前大约用了1年的时间来决定这些问题. 关键的一步就是引入片, 可以在一个固定大小的数组上有一个灵活可扩展的数据结构. 是该类型的大小的一部分,新的Go程序员通常对片的工作原理十分困惑。也许其他编程语言对他们思想影响太深.

在这篇中将理清这些混乱. 我们将通过构建块来解释附加内置函数是如何工作的,以及为什么它的工作原理是这样的。

你要爪子
翻译于 1年前

0人顶

数组

数组是 Go语言的一个重要模块, 就像基础模块一样他们往往隐藏在一些可见组件中. 在我们转到更有趣,功能更强大更突出的片之前,我们必须先简单说一说这些组件。

数组不知经常出现在 Go语言程序中,因为数组的是他类型的一部分大小,这限制了数组的功能.

声明

var buffer [256]byte

声明了256个字节的变量缓冲区。这个类型的缓冲区包含它的大小,[256]字节。用512字节数组是不同的类型[512]字节。

与数组有关的数据仅仅是一个数组的元素。如下所示,类似数组缓冲池在内存中的样子,

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

你要爪子
翻译于 1年前

0人顶

也就是说这个变量拥有256个字节的数据,再不拥有其他任何东西了。我们可以使用熟悉的索引语法buffer[0],buffer[1]等等,直到buffer[255]来访问其中的元素。(索引的范围从0到255,包含有256个元素。)试图对超过这个范围的buffer索引获取值将会引起程序崩溃。

有一个名字为len的内置函数,它返回的是数组或者片段中元素的数目,还可以是几个其他数据类型的元素的个数。对数组来说,len返回的是什么很明确。在我们所举的例子里,len(buffer)返回的是固定值256。

数组有自己的用途-比如数组是表示转换矩阵的好方法-不过,Go语言中最常用的目的是替分片占据存储。

几点人
翻译于 1年前

0人顶

分片:分片头

分片这种动作应用在哪儿呢?一个人只有准确地理解了分片是什么和分片能做什么的情况下才能很好的使用分片。
分片是一种数据结构,它描述的是与分片变量本身相隔离的,存储在数组里的连续部分。分片不是数组,分片描述的是一段数组。
前一节里我们给出了数组变量buffer,我们创建一个分片,它通过对buffer数组分片指定了元素100到元素150的分片(准确地说,是 100-149,包含两端)

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

几点人
翻译于 1年前

0人顶

在这个代码片段中,我们使用了完整的变量声明。变量slice是被声明为byte[]类型,它被初始化为一个buffer数组类型,包括100到150个slice元素。更通用的语法是丢掉类型,它通过初始化表达式进行设置。

var slice = buffer[100:150]

在一个函数我们可以使用简短的声明形式,

slice := buffer[100:150]

到底slice变量是什么呢?它虽然不是非常的完整,但是我们现在觉得slice作为一个小的数据结构拥有2个元素:一个长度和一个指针数组。你可以把它想象成是下面的样子:

type sliceHeader struct {
 Length int
 ZerothElement *byte
}
slice := sliceHeader{
 Length: 50,
 ZerothElement: &buffer[100],
}

NCThinker
翻译于 1年前

1人顶

当然,上面的只是一个说明。不管怎样这片代码结构对编程者是不可见的,元素指针的类型取决于元素的类型,但是给出了技术性的一个一般思想。

到目前为止,我们在数组上对slice进行操作,但是我们也可以切片一个slice:

slice2 := slice[5:10]

正如前面的一样,这种操作创建了一个新的slice,在这种情况下,原始slice拥有5到9(包括9)个元素,这就意味着原始数组有105到109个元素。slice2变量的形式和下面的sliceHeader结构体一样:

slice2 := sliceHeader{
 Length: 5,
 ZerothElement: &buffer[105],
}

注意,这个头仍然指向底层相同的数组,存储buffer数组变量。

NCThinker
翻译于 1年前

1人顶

我们也重新切片,意思就是说我们截取一个slice,然后把截取后的结果返回到最初的结构中。

slice = slice[5:10]

slice变量的Headerstructure结构体看起来和slice2的一样。你将会看到会经常重复使用它们,例如截取一个slice。下面的截取是去掉了第一个和最后一个元素:

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

[练习,写出上面这种形式的结构体,作为之后的作业]

NCThinker
翻译于 1年前

1人顶

你会经常听到Go语言的程序员讲 "slice header"因为他确实是储存在切片变量里. 例如, 当你调用一个函数,它接受一个切片作为参数,如 bytes.IndexRune,在调用的时候,header是传递给行数的,

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

切片参数被传递到IndexRune这个函数 , 实际上传递的是 "slice header".

在切片头有更多数据,下面将会谈到, 但先让我们看看当你的程序用到了切片,切片头有什么意义.

你要爪子
翻译于 1年前

0人顶

给函数传递分片

理解这一点是很重要的:虽然片段包含指针,但是它本身却是只是一个值。解开这个秘密:它是一个含有指针和长度的结构的值。它不是一个指向结构的指针。

这一点非常重要。

当我们在前面的例子里调用IndexRune的时候,传递给它的是分片头的一个拷贝。这种行为可以得到重要的结果。

看看下面这个简单的函数:

func AddOneToEachElement(slice []byte) {
 for i := range slice {
 slice[i]++
 }
}

它做得仅仅是函数名字所叙述那样,(使用for range 循环)对一个片段的索引迭代,增大每个元素。

几点人
翻译于 1年前

0人顶

试试这个例子:

func main() {
 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) }

(如果你想探个究竟,那么你可以编辑,然后重新执行这个可以执行的程序片段。)
虽然分片头是值传递的,但是这个头包含指向数组元素的指针,因此原来的分片头和传递给函数的这个头的拷贝都指向同一个数组。 因此,当这个函数返回的时候,已经修改的元素可以通过原来的分片变量看到修改过的元素值。

函数的参数实际上是一个拷贝,如下面的例子所示:

func SubtractOneFromLength(slice []byte) []byte {
 slice = slice[0 : len(slice)-1]
 return slice
}
func main() {
 fmt.Println("Before: len(slice) =", len(slice))
 newSlice := SubtractOneFromLength(slice)
 fmt.Println("After: len(slice) =", len(slice))
 fmt.Println("After: len(newSlice) =", len(newSlice))
}

这时我们可以看到由函数修改的分片参数的内容,不过分片头没有更改。存储在分片变量里的长度也不能通过调用函数而修改,这是因为传递给函数的是分片头的一个拷贝,不是原来的分片头。因此,如果我们想编写一个修改分片头的函数,那么我们必须把它当作结果参数返回,这儿我们就是这样做的。分片变量是无法做更改的,不过返回值具有新的长度,然后把这个返回值存储在新的分片中。

几点人
翻译于 1年前

0人顶

分片指针:方法中的接收者

让函数修改分片头的另一个方法是给这个函数传送指针。下面是前面例子的一次修改,实现了给函数传递指针:

func PtrSubtractOneFromLength(slicePtr *[]byte) {
 slice := *slicePtr
 *slicePtr = slice[0 : len(slice)-1]
}
func main() {
 fmt.Println("Before: len(slice) =", len(slice))
 PtrSubtractOneFromLength(&slice)
 fmt.Println("After: len(slice) =", len(slice))
}

在这个例子里,这么做似乎很笨拙,尤其是在对额外增加的中间层的处理上(临时变量实现),不过,在这儿,你可以看到指向分片的指针却是很常见的。对要修改分片的函数来说,使用指针实现参数接收是常见的做法。

让我们说说我们需要一个在最后一个斜杠处截短分片的方法。我们如下编写:

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

如果你运行这个例子,你会看到程序得到正确的运行,对调用者的分片完成了更改。

几点人
翻译于 1年前

0人顶

[练习:改变接收者的类型为一个数值而不是一个指针,然后继续运行。解释一下发生了什么]

另一方面,如果我们想要写一个方法来处理路径并把ASCII字母变为大写(忽视非英文名称),这个方法可能是一个数值,因为数值接收者将仍然指向同一个数组。

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]中多次写值。

[练习:将ToUpper方法改变为用指针接收值,看看结果是否变化了]

[高级练习:口说梦话ToUpper方法改变为处理Unicode字符,而不只是ASCII]

yale8848
翻译于 1年前

0人顶

容量

下面的函数通过传入一个元素扩展它的slice参数:

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

(为什么它需要返回一个已经修改过的slice呢?)现在运行它:

func main() {
 var iBuffer [10]int
 slice := iBuffer[0:0]
 for i := 0; i < 20; i++ { slice = Extend(slice, i) fmt.Println(slice) } }

查看slice的值是怎么变化的。

是时候谈论切片头的第三个组件了:它的容量。除了数组指针和长度,切片头还存储它的容量:

type sliceHeader struct {
 Length int
 Capacity int
 ZerothElement *byte
}

Capacity字段记录数组实际使用了多少的空间。这是Length能达到的最大值。试着增加slice的长度并超过它的容量,慢慢超过数组长度的限制,将会触发可怕的后果。

NCThinker
翻译于 1年前

1人顶

在我们的例子中slice是通过下面的方式创建的:

slice := iBuffer[0:0]

它的头部像下面的样子:

slice := sliceHeader{
 Length: 0,
 Capacity: 10,
 ZerothElement: &iBuffer[0],
}

Capacity字段和底层数组的长度减去slice的第一个元素的数组索引值是相等的(0在这种情况下存在)。如果你想探究一个slice的容量,使用cap函数:

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

NCThinker
翻译于 1年前

1人顶

Make方法

如果我们想增大分片,却超出分片本身的容量,怎么办呢?你不能这么做。根据分片的定义,容量限制了分片的增长。不过,你可以通过新创建一个数组,把分片数据拷贝到数组,然后修改分片使其指向新的数组而得到相同的结果。

让我们开始创建数组 。我们可以使用内置函数new来创建一个更大一点的数组,然后对所得的数组进行分片。不过实现这个更简单的方法是使用内置的make函数替代new函数。这个函数创建了一个新数组,然后创建了一个指向数组的分片头,所有这些一次完成。make函数使用了三个参数:分片类型,分片初始长度和make创建的用来保存分片数据的数组的长度,即分片容量。下面的调用创建了一个长度为10,且多余5个空间(10-15)的分片,运行它,你就会看到结果:

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

下面的程序片段对int分片的容量实现了倍增,而其长度却保持不变:

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

几点人
翻译于 1年前

0人顶

运行这段代码后,slice在需要重新分配之前拥有更多的增长空间。

当创建slices的时候,slice的长度和它的容量是相同的。通用情况下在make内置一个数组。参数的长度默认就是它的容量,所有你可以把它们设置为相同的值。

gophers := make([]Gopher, 10)

gophers sclice的长度和容量都同时被设置为了10。

NCThinker
翻译于 1年前

1人顶

复制

当我们把上一节中的slice的容量扩大两倍的时候,我们写了一个循环把以前的数据复制到新的slice中。Go有一个内置的copy函数,使这个实现更加简单。它的参数有2个sclice,它把右边参数的数据复制到左边参数中来。下面是使用copy函数写的一个例子:

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

copy函数很好用。它只复制它能够复制的,请注意两个参数的长度。换句话说,它复制的元素数量是两个slice中长度最小的那个。这可以节省一点效率。另外,copy函数会返回一个整数值,代表复制元素的数量。尽管它并不值得时时去检测。

NCThinker
翻译于 1年前

1人顶

在源分片和目的分片出现交叉时,copy函数仍然可以进行正确地拷贝,这意味着可以用copy函数实现耽搁分片中元素的移动。下面展示了如何使用copy函数向分片中间插入一个值。

// Insert向分片的指定位置插入值,
// 位置必须在有效范围内.
// 分片必须有空间增加新元素.
func Insert(slice []int, index, value int) []int {
 // 给分片增加一个元素的空间.
 slice = slice[0 : len(slice)+1]
 //使用copy函数移动分片的前面部分,打开一个缺口.
 copy(slice[index+1:], slice[index:])
 // 存储新值.
 slice[index] = value
 // 返回结果
 return slice
}

上面的函数中有两点要注意。第一点当然是这个函数必须返回已经更新的分片,因为分片的长度已经更改。第二点是这个函数使用了很方便的简写。表达式

slice[i:]

准确地讲等同于:

slice[i:len(slice)]

另外,尽管我们仍然没有使用过这个小技巧,不过我们仍然可以保持分片表达式的第一个元素为空;这个元素的默认值为零。因此表达式:

slice[:]

就意味着整个分片,这在对整个数组进行分片时很有用。这个表达式是说明"指向整个数组元素的分片":

array[:]

的最简写方式。

现在,所有的问题已经说明白了,让我们运行一下Insert函数。

slice := make([]int, 10, 20) //注意:容量要大于长度,这样才有空间增加新元素.
for i := range slice {
slice[i] = i
}
fmt.Println(slice)
slice = Insert(slice, 5, 99)
fmt.Println(slice)

几点人
翻译于 1年前

0人顶

Append:一个例子

在前面几节中,我们通过一个元素,写了一个扩展函数来扩展slice。尽管它有点问题,因为如果slice的容量太小的时候,这个函数就会崩溃。(我们内置的例子也有这个问题)。现在我们有方法来修复它,让我们为整数slices写一个健壮的实现。

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
}

这种情况下,返回slice特别的重要,因为当重新分配结果slice的时候,描述了一个完全不同的数组。下面的一小片代码展示在slice填满的时候发生了什么。

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

NCThinker
翻译于 1年前

1人顶

要注意到当初始化一个大小为5的一个数组时空间已经重新分配了。当新的数组被分配后,其容量和首元素地址都会改变。

在健壮的Extend函数的指导下我们可以写出一个更好的可以让我们按照多元素的方式扩展切片。为了能实现这个目标,我们用Go的特性将函数参数列表转换为一个切片。这就是我们运用了Go函数多变的技巧。

让我调用Append函数吧。在第一个版本中,我们可以只重复调用Extend来清除variadic函数机制。Append的签名方式如下:

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

yale8848
翻译于 1年前

0人顶

有人说Append有一个参数,而一个切片拥有0个或者更多的整形参数。那些参数是一个整形切片并实现了Append所关注的,如下面的形式:

// 给切片追加元素
// 第一个版本:循环调用Extend
func Append(slice []int, items ...int) []int {
 for _, item := range items {
 slice = Extend(slice, item)
 }
 return slice
}

注意在参数列表元素中循环迭代的范围,它是隐式[]int类型。也要注意用了一个空白的标识_抛弃循环的索引,这个例子中我们不需要这个标识。

yale8848
翻译于 1年前

0人顶

试试下面这段代码:

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

在这个例子里出现了另一个技术:通过复合文本常量初始化分片,复合文本常量是由分片类型,紧跟着包括在大括号内的 分片各项的值组成:

由于下面的原因,其中的Append函数也让我们很感兴趣。我们不仅仅可以用它来添加分片中的元素,而且还可以通过在调用处使用...符号给分片"激增"参数方法给分片增加第二个分片:

slice1 := []int{0, 1, 2, 3, 4}
slice2 := []int{55, 66, 77}
fmt.Println(slice1)
slice1 = Append(slice1, slice2...) //"..."很重要!
fmt.Println(slice1)

当然,我们还可以让Append更高效,在函数内部进行扩展,对其一次性分配足够的空间:

// Append给分片增加元素.
// 高效版本.
func Append(slice []int, elements ...int) []int {
 n := len(slice)
 total := len(slice) + len(elements)
 if total> cap(slice) {
 //重新分配空间,扩展为新给定大小的1.5倍,这样我们让然可以再对它进行扩展.
 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两次,第一次是把分片数据拷贝到新分配的内存,然后再拷贝要继续添加的各项到前面数据的后边。

试试下面这段代码;它的执行结果与前面提到的那段代码相同:

slice1 := []int{0, 1, 2, 3, 4}
slice2 := []int{55, 66, 77}
fmt.Println(slice1)
slice1 = Append(slice1, slice2...) // "..."很重要!
fmt.Println(slice1)

几点人
翻译于 1年前

0人顶

Append:内置函数

至此,我们已经明白设计append内置函数的动机。这个内置函数所要做的确实如上面的Append例子那样,而且同样高效,不过它可对任何分片类型操作。

Go语言的一个弱点是任何泛类型的操作只有在运行时才能确定。终有一天这会得到更改,不过,迄今为止 ,为了更容易地对分片进行操作,Go语言必须给出内置的泛型append函数。它就像我们上面的int型分片那样运行,不过它针对的是任何分片类型。

记住:由于在调用append的时候总是更改了分片的头,因此你必须在调用之后保存返回的分片。事实上,如果没有保存返回结果的话,编译器是不会让你调用append的。

下面的几段混合有print语句。试试这几段代码,编辑,然后看看运行结果:

// 创建两个最初的分片.
slice := []int{1, 2, 3}
slice2 := []int{55, 66, 77}
fmt.Println("Start slice: ", slice)
fmt.Println("Start slice2:", slice2)
// 给一个分片添加元素.
slice = append(slice, 4)
fmt.Println("Add one item:", slice)
// 继续添加另一个分片.
slice = append(slice, slice2...)
fmt.Println("Add one slice:", slice)
// 拷贝(int型)分片.
slice3 := append([]int(nil), slice...)
fmt.Println("Copy a slice:", slice3)
// 把分片拷贝到自己的尾部.
fmt.Println("Before append to self:", slice)
slice = append(slice, slice...)
fmt.Println("After append to self:", slice)

花点时间考虑上面这几段代码中的最后一段细节是值得的,这样就能够理解如何设计分片才可能使简单的调用得到正确的结果。

在由社团构建的"分片使用技巧"维客页面里, 还有许多append、copy和其他使用分片方法的例子。

几点人
翻译于 1年前

0人顶

Nil

另外,发现这样一个知识点:我们要明白nil分片是如何表示的。很自然,它的分片头为零:

sliceHeader{
 Length: 0,
 Capacity: 0,
 ZerothElement: nil,
}

或者仅如下面表示:

sliceHeader{}

关键的地方是元素指针也指向了nil。由

array[0:0]

创建的分片具有零长度(也许还具有零容量),不过它的指针指的不是nil,因此它不是nil分片。

应当很清晰了,空分片可以增大(假设它又非零的容量),而nil分片没有存放元素值得数组,而且从不会为了存放元素而增长。

也就是说,nil分片功能上等同于零长度的分片,不同的是它不指向任何东西。它具有零长度,但可以给其分配空间,添加元素。就像上面例子里那样,你可以看看通过给nil分片添加而实现分片拷贝的那一段。

几点人
翻译于 1年前

0人顶

字符串

现在我们在介绍分片的这段中插入一段对Go语言字符串的简短介绍。

字符串实际上很简单:它只是Go语言在句法上有一点额外支持的只读的字节分片。

由于字符串是只读的,因此它没有容量(你就不能对它进行扩展),然而,在大多数情况下,你只要把它当作只读的字节片段看待。

对初学者来说,我们可以通过索引来访问某一个字节:

slash := "/usr/ken"[0] //生成字节值为'/'.

我们也可以对字符串分片,用来获取子字符串:

usr := "/usr/ken"[0:4] //生成字符串"/usr"

现在,当我们对字符串分片的时候,其背后是如何运行的应该是很明了的。

我们还可以多通常的字节分片进行操作,可以使用简单的转换由字节分片创建字符串:

str := string(slice)

而且还可以进行相反方向的转换:

slice := []byte(usr)

我们还可以看到隐藏在字符串下面的数组;除了使用字符串访问数组内容外,没有其他办法可以访问了。这就意味着当我们做 上面的任何一种转换的时候,这个数组一定得到了拷贝。很显然,Go非常关心这一点,因此,你不需要做任何事情。运行上面 两种转换的任一一种都会修改字节分片底层的数组,这不会影响到对应的字符串。

几点人
翻译于 1年前

0人顶

切片的一个重要结果就和给字串设计了求子字串函数一样的效果。所有要做的只是创建一个含有2个词的字串头。应为字串是只读的,原始字串和经过切片处理的字串可以共同安全的分享同一个数组。

经验之谈:最先实现的是字串的分配,但是当给语言添加切片时,它提供了一种有效处理字串的模式。从一些基准测试中可以看出它的速度是很快的。

关于字串还有很多,当然,这些只能放到另一篇文章里讲了。

yale8848
翻译于 1年前

0人顶

结论

了解切片是如何工作的, 有助于了解他们是怎么实现的. 有一点数据结构,切片头,是与切片关联的项目,在开头也说了数组的独立分配.当我们传递切片值, 切片头会被复制一份,但它指向的数组是共享的.

一旦你明白它们是如何工作的,切片会非常简单易用, 但是功能强大,尤其是对于需要复制和附加的内置函数

你要爪子
翻译于 1年前

0人顶

更多阅读

有很多在网上找到关于Go语言分片的文章,正如前面提到的 "Slice Tricks" 有很多例子.关于 Go Slices的博客描述了内存布局图清晰的细节. Russ Cox's Go 数 据 结构 文章包括讨论分片以及一些其他的Go语言的的内部数据结构。.

还有更多的资料,但是最好的学习方式是使用它。

作者 Rob Pike

你要爪子
翻译于 1年前

0人顶