zhenpy 2018-08-20
编译自: https://dave.cheney.net/2018/07/12/slices-from-the-ground-up
作者: Dave Cheney
译者: Name1e5s
这篇文章受到了我与同事讨论使用 切片(slice)作为 栈(stack)的一次聊天的启发。后来话题聊到了 Go 语言中的切片是如何工作的。我认为这些信息对别人也有用,所以就把它记录了下来。
任何关于 Go 语言切片的讨论都要从另一个数据结构也就是 数组(array)开始。Go 的数组有两个特性:
package main
import "fmt"
func main() {
var a [5]int
b := a
b[2] = 7
fmt.Println(a, b) // prints [0 0 0 0 0] [0 0 7 0 0]
}
Go 语言的切片和数组的主要有如下两个区别:
基于第二个特性,两个切片可以享有共同的底层数组。看下面的示例:
package main
import "fmt"
func main() {
var a = []int{1,2,3,4,5}
b := a[2:]
b[0] = 0
fmt.Println(a, b) // prints [1 2 0 4 5] [0 4 5]
}
package main
import "fmt"
func negate(s []int) {
for i := range s {
s[i] = -s[i]
}
}
func main() {
var a = []int{1, 2, 3, 4, 5}
negate(a)
fmt.Println(a) // prints [-1 -2 -3 -4 -5]
}
大多数程序员都能直观地了解 Go 语言切片的底层数组是如何工作的,因为它与其它语言中类似数组的工作方式类似。比如下面就是使用 Python 重写的这一小节的第一个示例:
Python 2.7.10 (default, Feb 7 2017, 00:08:15)
[GCC 4.2.1 Compatible Apple LLVM 8.0.0 (clang-800.0.34)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> a = [1,2,3,4,5]
>>> b = a
>>> b[2] = 0
>>> a
[1, 2, 0, 4, 5]
以及使用 Ruby 重写的版本:
irb(main):001:0> a = [1,2,3,4,5]
=> [1, 2, 3, 4, 5]
irb(main):002:0> b = a
=> [1, 2, 3, 4, 5]
irb(main):003:0> b[2] = 0
=> 0
irb(main):004:0> a
=> [1, 2, 0, 4, 5]
在大多数将数组视为对象或者是引用类型的语言也是如此。 4
切片同时拥有值和指针特性的神奇之处在于理解切片实际上是一个 结构体(struct)类型。通常在 反射(reflect)包内相应部分之后 的这个结构体被称作 切片头(slice header)。切片头的定义大致如下:
package runtime
type slice struct {
ptr unsafe.Pointer
len int
cap int
}
这很重要,因为和 map 以及 chan 这两个类型不同 ,切片是值类型,当被赋值或者被作为参数传入函数时候会被复制过去。
程序员们都能理解 square 的形参 v 和 main 中声明的 v 的是相互独立的。请看下面的例子:
package main
import "fmt"
func square(v int) {
v = v * v
}
func main() {
v := 3
square(v)
fmt.Println(v) // prints 3, not 9
}
因此 square 对自己的形参 v 的操作没有影响到 main 中的 v。下面这个示例中的 s 也是 main 中声明的切片 s 的独立副本, 而不是 指向 main 的 s 的指针。
package main
import "fmt"
func double(s []int) {
s = append(s, s...)
}
func main() {
s := []int{1, 2, 3}
double(s)
fmt.Println(s, len(s)) // prints [1 2 3] 3
}
Go 的切片是作为值传递而不是指针这一点不太寻常。当你在 Go 内定义一个结构体时,90% 的时间里传递的都是这个结构体的指针 5 。切片的传递方式真的很不寻常,我能想到的唯一与之相同的例子只有 time.Time。
切片作为值传递而不是作为指针传递这一特殊行为会让很多想要理解切片的工作原理的 Go 程序员感到困惑。你只需要记住,当你对切片进行赋值、取切片、传参或者作为返回值等操作时,你是在复制切片头结构的三个字段:指向底层数组的指针、长度,以及容量。
我们来用引出这一话题的切片作为栈的例子来总结下本文的内容:
package main
import "fmt"
func f(s []string, level int) {
if level > 5 {
return
}
s = append(s, fmt.Sprint(level))
f(s, level+1)
fmt.Println("level:", level, "slice:", s)
}
func main() {
f(nil, 0)
}
在 main 函数的最开始我们把一个 nil 切片传给了函数 f 作为 level 0 。在函数 f 里我们把当前的 level 添加到切片的后面,之后增加 level 的值并进行递归。一旦 level 大于 5,函数返回,打印出当前的 level 以及它们复制到的 s 的内容。
level: 5 slice: [0 1 2 3 4 5]
level: 4 slice: [0 1 2 3 4]
level: 3 slice: [0 1 2 3]
level: 2 slice: [0 1 2]
level: 1 slice: [0 1]
level: 0 slice: [0]
你可以注意到在每一个 level 内 s 的值没有被别的 f 的调用影响,尽管当计算更高的 level 时作为 append 的副产品,调用栈内的四个 f 函数创建了四个底层数组 6 ,但是没有影响到当前各自的切片。
如果你想要了解更多 Go 语言内切片运行的原理,我建议看看 Go 博客里的这些文章:
via: https://dave.cheney.net/2018/07/12/slices-from-the-ground-up
作者: Dave Cheney 译者: name1e5s 校对: pityonline
本文由 LCTT 原创编译, Linux中国 荣誉推出
什么是数组数组是一种线性表数据结构,它用一组连续的内存空间来存储一组具有相同类型的数据。典型的线性表有数组、链表、队列和栈。直接将第 k 位的数据搬移到数组元素最后,然后把新的元素直接放在第 k 位。