slice in Go

本文详细介绍 Go 语言中 slice 的用法。

对于可以随机访问的顺序存储数据结构来说，Go 提供了 array 和 slice。
array 作为固定长度的数组，在 Go 语言中使用场景极少，而 slice 作为动态数组切片则相反，由于其灵活的特性，在 Go 程序中大量而广泛的使用。
因此，要想更熟练的使用 Go 语言进行编程，掌握 slice 的用法非常重要。

slice 本质是对底层数组的引用，在申明一个 slice 时，Go 实际上会在底层先分配一个数组，然后通过引用的方式来访问这个底层数组。

##### 如何遍历 slice? --- 使用 range 关键字进行遍历。遍历时，既可以返回单值，也可以返回双值。返回单值时就是 index，返回双值时会是 index 和 value。 e.g.

myslice := make([]string, 0, 5)
for i := range myslice {
  ...
}

for i, v := range myslice{
  ...
}

##### Go 可否同时遍历多个 length 相同的 slice ？** --- 答案是不可以！

Golang 不支持类似如下 python 的语法：

1 2	for x, y in range([1, 2, 3], [4, 5, 6]): print x, y

要想实现同时遍历两个或多个 slice，可以通过共享 index 的方式。也就是如果两个 slice 长度相同，那么遍历其中一个 slice 的同时，使用其 index 来访问另一个 slice 的元素，如下：

1
2
3

for i := range x {
    fmt.Println(x[i], y[i])
}

##### 如何 Copy Slice ? （深拷贝） ---
###### 两种方式： **1. 使用 Go 语言内置函数 copy**

1 2	b = make([]T, len(a)) copy(b, a)

2. 使用 append 函数
把要 copy 的 slice append 到一个 empty slice 中去。

1	b = append([]T(nil), a...)

##### 如何对一个 Slice 进行排序？ --- Go provides a `sort` package to do all things about sort, binary search, etc.

使用前需要 import "sort"，sort 包提供了对 float64, int, string 这 3 个基本数据类型的排序操作（不支持 int64，int32等其他类型的排序，需要用户自己转换）
同时，还提供了 IsSorted, Search 等函数用于支持对 slice 的相关操作。

函数原型
e.g.

1 2	func Ints(a []int) func Search(n int, f func(int) bool) int

##### 如何只对 slice 的某一部分进行排序？ ---

1	sort.Ints(slice[5:11])

##### 如何排序一个自定义的数据类型？ --- Sort a user-defined data structure Sorting user-defined data in Go requires you to implement the sort.Interface. This interface requires three simple methods: Len, Less, and Swap.

函数原型:

1
2
3

Len() int
Less(i, j int) bool
Swap(i, j int)

In simple, as long as the user-defined slice of data implement these three methods, we can call sort.Sort(data) to sort it.

e.g.

type intervals []Interval

func (slice intervals) Len() int {
    return len(slice)
}

##### 如何删除 slice 中的元素？ ---

没有提供 build-in 的函数来实现 remove 功能。需要我们手动操作。
主要的方法就是拼接

(1) 删除尾部元素

1	sol = (sol)[0 : len(*sol)-1]

(2) 删除中间元素

1	a = append(a[:i], a[i+1:]...)

总结：
从 slice 这种数据结构本质来看，其并不适合做删除操作。实际上，无论什么语言，数组（连续空间，随机访问）这种数据结构，做删除操作的话，都是需要移动元素的，而移动元素会导致大量的 copy，效率很低。

如果实在需要使用 slice 又不可避免需要删除元素，那么可以使用下述方法提高效率。
前提是不关心删除之后元素的原有顺序，那么可以用最后一个元素替换要删除的元素，然后去掉最后一个元素，
e.g

1 2	a[i] = a[len(a)-1] a = a[:len(a)-1]

当然，如果需要频繁删除中间或开头的元素，更好的是选择链表这样的数据结构。
Go中可以使用 map 或 container/list 包。

##### 如何清空一个 slice --- 清空 slice，也即把这个 slice 置 nil

1	slice = nil

要弄清楚一个 slice 置为 nil 具体是怎么回事，我们可以借助下述这个 slice 结构体定义来理解：

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

从上述结构中我们可以看到，一个置为 nil 的 slice 是指它的 length 和 capacity 成员都是 0，并且它的底层数组指向 nil。从功能表现上来看，nil slice 可以被 append，并且自动分配内存。

比如，下述例子把一个 slice 中的所有元素拷贝到一个 nil slice 中去，从而实现复制功能。

1	slice1 := append([]int(nil), slice...)

可见，通过简单的 slice = nil 是最好的清空 slice 的方式，通过这样的方式，其底层的数组原占的内存也会被 gc 自动回收。
注意：不要通过 slice = slice[:0] 这样的方式去清空一个 slice，因为这会导致潜在的内存泄露。也就是说，内存已经不再使用了，但是却有可能通过 re-slice的方式访问到。

#### 如何插入一个元素到 slice 中？ --- use copy to shift items around in a single slice

给一个 slice 插入元素的时候需要注意 len 和 cap 属性，如果当前 slice 的 len 小于 cap，那么无需重新分配内存。
否则，插入一个元素必然需要重新分配内存。

func Insert(slice []int, index, value int) []int {
    slice = slice[0 : len(slice)+1]       // Grow the slice by one element, make sure cap >= len(slice) + 1
    copy(slice[index+1:], slice[index:])  // Use copy to move the upper part of the slice out of the way and open a hole.
    slice[index] = value
    return slice
}

##### slice 作为函数参数 ---
###### 1. 如果只是改变原有 slice 中的值，那么不需要传指针：虽然本质上，slice 做函数参数时，本身是做为值传递的，但是由于 slice 这个数据结构包含了一个指向底层数组的指针，在修改 slice 原有内容的时候的，是修改了底层数组的内容，因此修改效果可以体现。

1
2
3

func modifySlice(a []int) {
    a[0] = 1000
}

###### 2. 如果有 append 操作，必须取该 slice 变量的指针再传递：这是由于 append 会导致 slice 底层结构体中的引用的数组地址改变，length 成员变量的值也会改变, append 之后，slice 引用的还是原来的数组地址，因此修改无效！必须传递该 slice 的指针，以便获得修改后的效果。

func testSlice(a *[]int) {
    ...
}

func testAppend(slice0 []int) {
    fmt.Printf(" %p \n", &slice0)
    slice0 = append(slice0, 4)
    fmt.Printf(" %p \n", &slice0)
    slice0 = append(slice0, 5)
    fmt.Printf(" %p \n", &slice0)
}

func main() {
    slice0 := []int{1, 2, 3}
    fmt.Printf(" %p \n", &slice0)
    testAppend(slice0)
    fmt.Printf(" %p \n", &slice0)
}

运行结果：

0xc0820403c0
0xc082040420 // 可见，做参数传递时， slice 复制了一份，因此地址变了。
0xc082040420
0xc082040420
0xc0820403c0

如果不想通过参数中传指针的方式，那么利用返回值的方式来获得改变后的 slice。具体做法是在函数拷贝一个原 slice（使用copy(src, dest)），然后在函数末尾返回一个 slice，如：

func testSlice(a []int) []int {
    dest := make([]int, len(a))
    copy(dest, a)
    ...
    return dest
}

##### 二维 slice 的 append 操作 --- 当使用二维 slice 时，需要把一个一维的 slice append 到这个二维 slice中，如果这个一维 slice 会频繁变动，比如作为临时 slice 使用（在算法题 SubSet， Combination Sum 等中经常见到），一定要记得拷贝一份再 append 给那个二维 slice。

使用这个：

1	all = append(all, append([]int(nil), *sol...))

e.g.

func test2d(all *[][]int) {
    r1 := []int{1, 2, 3}
    r2 := []int{9, 8, 7}
    *all = append(*all, r1)
    *all = append(*all, r2)
}

func test1d(d1 *[]int) {
    *d1 = append(*d1, 88)
    *d1 = append(*d1, 99)
}

func main() {
    all := [][]int{}
    test2d(&all)
    fmt.Println(all)

    d1 := []int{}
    test1d(&d1)
    fmt.Println(d1)
}

###### 总结： --- 在什么情况下需要用到指针形式的 slice 呢？

(1). 做函数参数，需要对 slice 结构做 append 操作修改原数据。
(2). 为 slice 提供 pointer receiver 形式的成员函数修改本 slice。
比如，https://blog.golang.org/slices 提供的一个例子：

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

注意： 这里的 receiver 必须是 pointer 类型的，否则修改无效。

参考

https://blog.golang.org/go-slices-usage-and-internals
http://lib.csdn.net/article/go/37533
https://www.dotnetperls.com/slice-go
https://blog.golang.org/slices
http://blog.csdn.net/erlib/article/details/50957218