原文链接

Go Wiki: SliceTricks

译文

Go编程语言中的SliceTricks指的是一系列操作和模式，它们用于操作切片的内容和结构。这些技巧包括滤除元素、反转、洗牌、批量处理以及现场去重等。Go 1中引入了内置函数append，可以帮助实现曾经由container/vector包提供的大部分功能。现在，container/vector包已在Go 1中移除。

随着Go语言泛型的引入，golang.org/x/exp/slices包提供了这些函数的泛型实现。

以下是几种vector方法及其切片操作对应：

AppendVector

a = append(a, b...)

Copy

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

// 以下两种方法通常比上面的方法慢一点，
// 但如果后续还要继续向b追加更多元素，这些做法会更有效率。
b = append([]T(nil), a...)
b = append(a[:0:0], a...)

// 逻辑上，这种一行实现等同于上面两行的make+copy实现。
// 但实际上（截至Go toolchain v1.16）它稍慢一些。
b = append(make([]T, 0, len(a)), a...)

Cut

a = append(a[:i], a[j:]...)

Delete

a = append(a[:i], a[i+1:]...)
// 或者
a = a[:i+copy(a[i:], a[i+1:])]

Delete without preserving order

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

注意：如果元素的类型是指针或者包含指针字段的结构体，需要垃圾回收，上面实现的Cut和Delete可能会出现内存泄漏问题：一些元素的值仍被切片a的底层数组引用，就不可见于切片中。由于"deleted"值在底层数组中被引用，这个值在GC时仍然是"reachable"的，即便你的代码已经无法引用它了。如果底层数组是长期存在的，这代表了内存泄漏。下面的代码可以解决这个问题：

// Cut
copy(a[i:], a[j:])
for k, n := len(a)-j+i, len(a); k < n; k++ {
    a[k] = nil // 或T的零值
}
a = a[:len(a)-j+i]
// Delete
copy(a[i:], a[i+1:])
a[len(a)-1] = nil // 或T的零值
a = a[:len(a)-1]
// Delete without preserving order
a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]

Expand

插入n个元素到位置i：

a = append(a[:i], append(make([]T, n), a[i:]...)...)

Extend

追加n个元素：

a = append(a, make([]T, n)...)

Extend Capacity

确保有空间追加n个元素而无需重新分配：

if cap(a)-len(a) < n {
    a = append(make([]T, 0, len(a)+n), a...)
}

Filter (in place)

n := 0
for _, x := range a {
    if keep(x) {
        a[n] = x
        n++
    }
}
a = a[:n]

Insert

a = append(a[:i], append([]T{x}, a[i:]...)...)

注意：第二个append创建了一个新的带有自己底层数组的切片，并将a[i:]中的元素复制到这个新切片中，然后这些元素通过第一个append再次被复制回a切片。创建新切片（以及内存垃圾）和第二次复制可以通过使用另一种方式避免：

Insert

a = append(a, 0 /* 使用元素类型的零值 */)
copy(a[i+1:], a[i:])
a[i] = x

InsertVector

a = append(a[:i], append(b, a[i:]...)...)

// 上面一行的方法会复制a[i:]两次，并至少分配一次。
// 下面这种冗长的方法只复制a[i:]中的元素一次，
// 并最多分配一次。然而，由于缺少优化来避免
// "make"调用时的元素清除，这种方式不一定总是更快。
//
// 未来的编译器优化可能实现两者的最高效方式。
//
// 假设元素类型是int。
func Insert(s []int, k int, vs ...int) []int {
    if n := len(s) + len(vs); n <= cap(s) {
        s2 := s[:n]
        copy(s2[k+len(vs):], s[k:])
        copy(s2[k:], vs)
        return s2
    }
    s2 := make([]int, len(s) + len(vs))
    copy(s2, s[:k])
    copy(s2[k:], vs)
    copy(s2[k+len(vs):], s[k:])
    return s2
}

a = Insert(a, i, b...)

Push

a = append(a, x)

Pop

x, a = a[len(a)-1], a[:len(a)-1]

Push Front/Unshift

a = append([]T{x}, a...)

Pop Front/Shift

x, a = a[0], a[1:]

其他技巧

不分配内存过滤(Filtering without allocating)，反转(Reversing)，洗牌(Shuffling)，批量处理(Batching with minimal allocation)，就地去重(In-place deduplicate (comparable))，向前移动(Move to front)，还有滑动窗口(Sliding Window)等是关于在特定情形下如何高效操作切片的一些额外技巧。它们包括了在共享相同底层数组的同时不产生新的内存分配，在原切片上交换元素的位置，以及使用随机函数打乱切片元素的顺序等。高效批量处理技巧涉及如何将一个大的切片分割成多个小批次进行处理，而就地去重技巧则展示了如何删除排序后切片中的重复元素。向前移动元素或者是把一个不存在的元素预置到切片的前面，都可以在原地完成。滑动窗口是另一个常见的模式，用于序列化处理具有固定大小窗口的连续片段。