golang slice array append

Golang中的slice, array和append

Posted by Manasseh Zhou on Wednesday, September 19, 2018

TOC

引言

在编程语言的设计过程中, array是一个重要的数据结构, 实现array的功能常常需要考虑很多因素, 如:

  • length是否可变?
  • length是不是也是类型的一部分?
  • 多维数组如何表示?
  • 空数组的意义?

在Golang中为了解决这个问题, 除了定长的数组(array)外, 还引入了切片(slice)这一数据结构, 从而实现可变长度数组的功能.

Array

虽然Golang有slice这么强大的数据结构, 可是我们还是要从简单的array说起.

创建(声明)一个array

var array [5]int

如你所见, Golang中的array有两个重要的参数, 大小, 以及其中存储的数据类型. 这里注意, 与C++不同, 在传递参数时, C++不关注数组中保存的元素的个数, 而在Golang中, [10]int 和 [5]int 则会被视为两种不同的类型.

package main

import (
	"fmt"
)

func testArray5(array [5]int) {
	fmt.Println(array)
}

func main() {
	var array5 [5]int
	// var array10 [10]int
	
	testArray5(array5)
	// testArray5(array10) Error: cannot use array10 (type [10]int) as type [5]int in argument to testArray5
}

我们刚刚声明的array内保存了5个int类型的数据, 在内存中, 长这个样子:

int int int int int

我们可以通过array[index]的方式来访问数组中的各个元素, 需要注意的是: 越界访问会直接报错, 如果需要获取array的长度信息, 可以使用Golang内置的len()函数.

先在这里挖个坑:

func main() {
	var a [5]int
	b := a
	
	b[3] = 7
	
	fmt.Println(a, b) // [0 0 0 0 0] [0 0 0 7 0]
}

在上面的这段代码中, 我们先声明了一个数组a, 之后又将a赋值给了b, 并修改了b中的值, 把a, b中的值都输出了出来. 看起来没什么问题对吧? 好, 那就让我们一起看看slice又是什么样的吧!

Slice

在slice的定义中, 没有了固定的长度, 而是把长度作为slice自身的属性, 同样我们也能通过len()来获取一个slice的长度.

slice本身是一个数据结构, 它描述了一段与它自身分开存储的数组的相关信息. slice 不是 array, 而是描述了array的一部分! 接下来, 让我们创建一个slice.

var sli []int := array5[1:3]
var sli2 := array5[1:3]
sli3 := array[1:3]

这样, 我们就得到了array5这个array的三个slice, 其中保存的内容从array5中array5[1]开始, 到array5[3]为止(不包含array5[3]).

先看看我们挖的坑

为了对比slice 和 array 的不同, 你可以运行一下下面的程序, 猜想一下程序的输出和实际的输出进行一下对比, 看看你的想法是不是和实际情况一样.

P.S. append()函数为向slice中添加新的值

package main

import (
    "fmt"
)

func a() {
    x := []int{}
    x = append(x, 0)
    x = append(x, 1)
    y := append(x, 2)
    z := append(x, 3)
    fmt.Println(y, z)
}

func b() {
    x := []int{}
    x = append(x, 0)
    x = append(x, 1)
    x = append(x, 2)
    y := append(x, 3)
    z := append(x, 4)
    fmt.Println(y, z)
}

func main() {
    a()
    b()
}

是

[0, 1, 2] [0, 1, 3]
[0, 1, 2, 3] [0, 1, 2, 4]

还是

[0, 1, 2] [0, 1, 3]
[0, 1, 2, 4] [0, 1, 2, 4]

一样么? 如果一样, 大概你已经知道Golang的slice的具体原理了(那么, 欢迎来帮我的文章debug!), 如果不一样, 我们一点一点的看到底发生了啥~

那么 slice 到底是什么呢?

通过上面的描述, 我们现在可以假设一下:

type SliceHeader struct {
    var Length int
    var ZerothElement *int
}

上面的声明则是创建了这样的一个数据结构

sli := SliceHeader{
    Length: 2,
    ZerothElement: &array5[1],
}

当然, 在实际过程中SliceHeader这一结构对程序员透明, 而且元素类型也由具体的数据决定.

同样的slice的slice也可以以同样的方式进行理解.

slice是怎么实现的动态大小呢

在上面的假设中, 我们的SliceHeader只保存了它的大小(已存储的数据的长度)和指向的内存空间, 那么如果我们插入了大于该内存空间所能保存的数据时, 会发生什么事情呢? 那当然是越界错误啦!

为了避免这个问题, 我们在SliceHeader中又增加了一个叫做capacity的项, 用来表示所指向的内存空间所能存放的数据的最大容量, 在向其中添加项时, 先判断是否超过其capacity, 如果不超过, 则直接保存到其所指向的内存空间中, 否则, 重新申请一段更大的内存, 把旧数据拷贝过去后再向其中加入新的项.

type SliceHeader struct {
    var Length int
    var Capacity int
    var ZerothElement *int
}
sli := SliceHeader{
    Length: 2,
    Capacity: 5,
    ZerothElement: &mem[0],
}

SliceHeader

通过对capacity的判断(cap(slice)), 保证了slice不能超越其内存所能存储的数据量而无限扩展, 从而保证了内存的安全.

我该怎么创建一个空的slice呢

也许你就要问了, 我不能总是从array中创建一个slice出来吧? 这多麻烦啊!

使用new()先创建出一段内存空间, 作为array, 之后再使用slice是一个可行的办法, 但是这太麻烦了.

Golang还为我们提供了一个make()函数, 通过这个函数我们可以直接完成创建一段内存空间并用SliceHeader描述他的过程, 这个函数需要三个参数, (slice的类型, 初始大小, 初始容量(可省略)).

sice := make([]int, 4, 8)
fmt.Printf("slice: %v len: %d, cap: %d\n", slice, len(slice), cap(slice))

在不提供初始capacity(省略第三个参数)的情况下, Golang一般会让capacity = length, 所以对于未指定capacity的slice, 一般都会有 cap(slice) == len(slice)

先拷贝(copy)

在研究append之前, 我们先看看怎么把一个slice的内容转移到另一个slice中.

在append的时候, 很有可能发生cap(slice)==len(slice)的情况, 在这种情况下, 直接向slice中所指向的内存添加数据势必会导致错误, 我们需要先将旧数据拷贝到一个新的, 容量更大的slice中, 然后再进行append操作. 这里我们可以使用Golang中自带的copy()函数

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

注意, copy函数在工作时, 拷贝的元素数量为两个slice中的更小的那个长度. 返回值为实际拷贝的元素数量.

通过copy函数, 我们可以很方便的实现向slice中某一位置插入值的操作

// 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:])
    // Store the new value.
    slice[index] = value
    // Return the result.
    return slice
}

slice 在切片时在某些情况下可以使用缩写, 如slice[i:]代表了slice[i:len(slice)], slice[:] 代表了slice[0:len(slice)]

再增长(append)

刚刚, 我们提到了, 如果直接向已经满了的slice的内存空间中增加新的值会导致访问越界, 那么Golang又是怎么实现的呢?

在这里, 我们提供一个简单的实现方式用于理解, 实际的代码请见后文参考资料.

func Append(slice []int, element int) []int {
    n := len(slice)
    if n == cap(slice) {
        // Slice 满了! 增长!
        // 2*length(slice)+1 保证在size为0的时候还能增长
        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返回.

在Golang的实现中, 在len(slice)<1024时, 翻倍, 而在多于1024个元素时, 为节省内存空间考虑(考虑一下原来已经占用了8G的内存, 然后我又想要4G…这能忍?), 将capacity增加的量设置为原来的1.25倍.

我刚刚为啥掉到坑里了!

我们知道, Golang在参数传递时使用的是值传递, 那么在使用赋值方式初始化slice的值时, 会将其中保存的数据(SliceHeader中的len, cap, ptr)一个一个复制到新的slice中.

在func a()中, 在完成前两次append后, x的状态为len(x) = 2, cap(x) = 2此时, 再向其中append则必然会导致对slice的扩充, 从而导致向x, y中append新元素时使用的是不同的地址, 所以他们最终输出的结果不同.

而在func b()中, 在完成前三次append后, x的状态为len(x) = 3, cap(x) = 4此时, y, z在进行append()操作时, 均认为slice中只存放了三个元素, 可以直接向第四块内存空间写入数据, 而且, y, z指向了相同的内存空间, 这样就导致了z写入的数据覆盖了y写入的数据. 正确的做法: 先copy再写入.

Nil 和 空切片

nil切片和空切片类似, 都有len() = 0, cap() = 0 但空切片指向的内存地址不为nil, nil切片指向的内存地址为nil. 对这两种切片进行copy(), append(), len(), cap()的效果均相同

Reference

  1. append()
  2. growslice()
  3. Go Slices: usage and internals
  4. Slices
  5. Golang slices gotcha
  6. Slices from the ground up

推荐阅读

  1. 深入解析 Go 中 Slice 底层实现
comments powered by Disqus
FEATURED TAGS
CTF cybersecurity web write-up writeup