你可以在
golang/SliceTricks中找到一些有用的技巧。
自从引入了
append
内置函数后,大部分
container/vector
包的功能已被移除,现在可以使用
append
和
copy
来实现它们。
以下是vector方法及其切片操作的类比:
a = append(a, b...)
b = make([]T, len(a))
copy(b, a)
// or
b = append([]T(nil), a...)
a = append(a[:i], a[j:]...)
a = append(a[:i], a[i+1:]...)
// or
a = a[:i+copy(a[i:], a[i+1:])]
a[i] = a[len(a)-1]
a = a[:len(a)-1]
注意 如果元素的类型是指针或具有需要进行垃圾回收的指针字段的结构体,则上述的Cut
和Delete
实现存在潜在的内存泄漏问题:一些具有值的元素仍然被切片a
引用,因此无法进行回收。以下代码可以解决这个问题:
Cut
copy(a[i:], a[j:])
for k, n := len(a)-j+i, len(a); k < n; k++ {
a[k] = nil // or the zero value of T
}
a = a[:len(a)-j+i]
删除
copy(a[i:], a[i+1:])
a[len(a)-1] = nil // or the zero value of T
a = a[:len(a)-1]
不保留顺序的删除
a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]
a = append(a[:i], append(make([]T, j), a[i:]...)...)
a = append(a, make([]T, j)...)
a = append(a[:i], append([]T{x}, a[i:]...)...)
注意 第二个append
会创建一个新的切片并拥有自己的底层存储,将a[i:]
中的元素复制到该切片中,然后这些元素将被复制回到切片a
(由第一个append
完成)。通过使用另一种方式可以避免创建新的切片(因此避免内存垃圾)和第二次复制:
插入
s = append(s, 0)
copy(s[i+1:], s[i:])
s[i] = x
a = append(a[:i], append(b, a[i:]...)...)
x, a = a[0], a[1:]
x, a = a[len(a)-1], a[:len(a)-1]
a = append(a, x)
a = append([]T{ x }, a...)
x, a := a[0], a[1:]
a = append([]T{x}, a...)
额外技巧
无需分配内存的过滤方法
这个技巧利用了切片与原始数组共享同一后备数组和容量的特性,因此可以重复使用已有的存储空间来创建过滤后的切片。当然,原始内容会被修改。
b := a[:0]
for _, x := range a {
if f(x) {
b = append(b, x)
}
}
反转
要将切片中的内容替换为相同元素但顺序相反的元素:
for i := len(a)/2-1; i >= 0; i-- {
opp := len(a)-1-i
a[i], a[opp] = a[opp], a[i]
}
相同的事情,只是有两个索引:
for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {
a[left], a[right] = a[right], a[left]
}
洗牌
Fisher-Yates算法:
for i := len(a) - 1; i > 0; i
j := rand.Intn(i + 1)
a[i], a[j] = a[j], a[i]
}