小马别过河

V1

2022/10/08阅读:20主题:默认主题

Go 概念[译]:slices 用法与实现

介绍

Go 语言的 Slice 类型提供了一种方便且高效处理类型序列的方法。Slice 和其他语言的数组有点类似,但有着区别于数组的特性。本文着重于介绍 Slice 的定义和用法。

Arrays(数组)

Slice 类型是基于 Array 类型的更高级的抽象,所以想要了解 Slice 之前,需要先理解 Arrays。

Array 类型定义需要指定长度和元素类型。比如,数组[4]int表示包含4个整形元素。数组的长度是固定的,而且它的长度是它类型的一部分([4]int[5]int是不同、互不相容的类型)。Arrays 可以按普通方式索引,s[n]表示 s 的第 n 个元素,从0算起。

var a [4]int
a[0] = 1
i := a[0]
// i == 1

Arrays 不需要初始化,它的默认值是一个直接使用的数组,数组内的元素就是该类型的默认值。

// a[2] == 0, the zero value of the int type

[4]int在内存的表现只是4个按顺序排列的整数。

Go 的 Array 是值类型。一个数组变量代表整个数组,而不是数组第1个元素的指针(C语言)。这意味着你分配和传递一个 Array 时,会复制 Array 的内容。(为了避免这种情况,可以传递 Array 的指针,但这只是 Array 的指针,而不是 Array 本身)。我们可以把 Array 当成一种特殊的 struct,只不过它的字段名是索引,而不是字段名。

Array 可以这样指定:

b := [2]string{"Penn""Teller"}

或者让编译器自己计算长度

b := [...]string{"Penn""Teller"}

上面两个案例,b 的类型都是 [2]string

Slices(切片)

数组有它应用场景,但是它有点死板,所以在 Go 代码中,不会特别常用。Slices 则随处可见。Slice 基于数组,但是更加强大且便利。

切片的类型规范是[]T,T 代表切片元素的类型。不像数组,切片不用指定长度。

切片字面量的声明和数组差不多,只不过不用指明元素的个数。

letters := []string{"a""b""c""d"}

切片也可以使用内置函数make创建。

func make([]T, len, cap) []T

T 代表的是切片元素的类型。make函数的参数是类型([]T)、长度(len)、容量(cap), 。make被调用时,会先创建一个数组,然后返回一个引用该数组的切片。

var s []byte
s = make([]byte55)
// s == []byte{0, 0, 0, 0, 0}

参数cap被忽略时,默认使用cap = len。上面的代码可以简化为:

s := make([]byte5)

可以使用内置函数lencap,来获取切片的长度和容量。

len(s) == 5
cap(s) == 5

后文会介绍 len 和 cap 的区别。

切片的缺省值是 nil。nil 切片的 len 和 cap 都为 0。

还能通过对数组和切片进行"截取"(slicing)操作,得到新的切片。比如,表达式b[1:4]创建一个新的切片,切片的元素包括变量 b的索引1到索引3的元素。

b := []byte{'g''o''l''a''n''g'}
// b[1:4] 为 []byte{'o', 'l', 'a'}, 跟 b 底层使用共同的数据

进行像b[n:m]的截取操作时,n 和 m 都是可选的,他们的默认值分别是 0 和 len(b):

// b[:2] == []byte{'g', 'o'}
// b[2:] == []byte{'l', 'a', 'n', 'g'}
// b[:] == b

同理,也可以对数组进行类似的操作:

x := [3]string{"Лайка""Белка""Стрелка"}
s := x[:] // a slice referencing the storage of x

Slice 内部实现

切片是数组片段的描述,它包括一个指向底层数组的指针ptr,数组片段的长度len,以及片段的容量cap(容量是片段的最大长度)。 demo1

我们通过s := make([]type, 5)创建变量s,它的结构如下: demo2

长度len是切片引用的数组片段的长度,容量cap 是底层数组的元素个数(从切片指针引用的第一个元素到数组的结尾)。通过下面的例子,长度和容量的区别更加明显。

我们截取切片(slicing,翻译成"截取"可能并不贴切)s,会观察到其结构、及其底层数组有了以下变化:

s = s[2:4]
demo3
demo3

截取操作并不会复制切片,而是创建一个新的指向原始底层数组的切片。这使得操作切片和操作数组索引一样高效。因此,操作一个切片的元素,会影响到引用相同底层数组的其他切片。

d := []byte{'r''o''a''d'}
e := d[2:]
// e == []byte{'a', 'd'}
e[1] = 'm'
// e == []byte{'a', 'm'}
// d == []byte{'r', 'o', 'a', 'm'}

刚才我们截取了变量 s,使它的长度小于容量(图 demo3 所示)。我们可以对 s 重新分片,来扩展切片。

s = s[:cap(s)]
demo4
demo4

扩容切片(copyappend 方法)

如果要对切片扩容,就必须创建一个更大容量的新切片,同时复制旧切片的内容到新切片。这类似其他语言的「动态数组」的实现。下面的例子是把切片s的扩容两倍,操作流程是先创建一个新切片 t, 容量是原切片s的两倍,接着把原切片s的元素赋值给t的元素,最后把t赋值给s

t := make([]bytelen(s), (cap(s)+1)*2// +1 in case cap(s) == 0
for i := range s {
        t[i] = s[i]
}
s = t

for 循环可以使用内建函数copy简化。copy会从源切片复制数据到目标切片。它的返回值是复制元素的个数。

func copy(dst, src []T) int

copy函数支持复制不同长度的切片。如果dstsrc底层是同一个数组,copy也能正确处理。

因此,上面的代码可以简化成

t := make([]bytelen(s), (cap(s)+1)*2)
copy(t, s)
s = t

一个常用操作是追加一个元素到切片尾部。下面的函数追加 byte 元素到一个切片,如果容量不够会扩容,最后返回被追加后的切片。

func AppendByte(slice []byte, data ...byte) []byte {
    m := len(slice)
    n := m + len(data)
    if n > cap(slice) { // 如有需要,重新扩容
        // 扩展2倍容量,便于后续操作
        newSlice := make([]byte, (n+1)*2)
        copy(newSlice, slice)
        slice = newSlice
    }
    slice = slice[0:n]
    copy(slice[m:n], data)
    return slice
}

AppendByte 可以这么使用:

p := []byte{235}
p = AppendByte(p, 71113)
// p == []byte{2, 3, 5, 7, 11, 13}

AppendByte函数非常有用,因为它们提供了完整的自动扩容控制。取决于程序的特性,来决定扩容的大小或者重新分配的上限。

但是大部分程序是不需要完全控制扩容策略,所以 Go 提供了适用于大部分场景的append函数:

func append(s []T, x ...T) []T

append函数追加元素 x 到切片 s,如果容量用完会自动扩容。

a := make([]int1)
// a == []int{0}
a = append(a, 123)
// a == []int{0, 1, 2, 3}

如果追加一个切片到另一个切片,可以使用 ... 来展开成第二个参数。

a := []string{"John""Paul"}
b := []string{"George""Ringo""Pete"}
a = append(a, b...) // 等同于 "append(a, b[0], b[1], b[2])"
// a == []string{"John", "Paul", "George", "Ringo", "Pete"}

既然 slice 的零值(nil) 表现和长度为 0 的切片表现一样,你可以直接把 nil 切片作为append的第一个参数。

// Filter 过滤掉不符合 fn() 的元素
func Filter(s []int, fn func(int) bool) []int {
    var p []int // == nil
    for _, v := range s {
        if fn(v) {
            p = append(p, v)
        }
    }
    return p
}

一个可能会遇到的"陷阱"

正如前文所说,对一个切片进行重新切片操作以后,两个切片还是共用同一个底层数组。这个底层数组会一直保留在内存中,直到没被引用才被回收。这偶尔会造成一些问题:实际用到的切片长度很小,但是底层的数组非常大。

var digitRegexp = regexp.MustCompile("[0-9]+")

func FindDigits(filename string) []byte {
    b, _ := ioutil.ReadFile(filename)
    return digitRegexp.Find(b)
}

这段代码返回的[]byte指向的底层数组,包含着整个文件。只要切片引用着这个数组,垃圾回收器就不会释放这部分内容。相当于为了少数有用的 byte,我们在内存一直存着整个文件内容。

想要解决这个问题,可以在返回前,把目标数据复制到一个新的切片:

func CopyDigits(filename string) []byte {
    b, _ := ioutil.ReadFile(filename)
    b = digitRegexp.Find(b)
    c := make([]bytelen(b))
    copy(c, b)
    return c
}

更简洁的版本是使用 append。这个留给读者自己练习。

引用

[1]. Go Slices: usage and internals (https://go.dev/blog/slices-intro)

分类:

后端

标签:

Golang

作者介绍

小马别过河
V1