在 GO lang 中删除和添加元素到数组

Question

我有 2 个数组声明为： var input []string 和 var output []string 。

输入数组最初填充了一些ID。输出数组为 NULL。

每次迭代后，我想从输入数组中删除一个随机元素并将其添加到输出数组。

最后，输出数组中的所有元素都将与输入数组相同（但顺序（索引）不同）。

for index := 0; index < len(input); index++ {
    if !visited[index] {
        //do something
    }
}
output[#iteration index] = input[current index]

当我尝试这样做时，我得到 array out of bounds error。

Answer 1

对于 output 数组，您需要使用 append 或为其分配初始容量以匹配 input 的大小。

// before the loop
output := make([]string, len(input))

将是我的建议，因为 append 会导致一堆不必要的重新分配，并且您已经知道您需要什么容量，因为它基于 input.

另一件事是：

output = append(output, input[index])

但是就像我说的，从我观察到的 append 以指数方式增长初始容量。如果您没有指定任何内容，这将以 2 为基数，这意味着您将在达到所需容量之前进行一些不需要的重新分配。

Answer 2

您可以在 golang/SliceTricks 找到一些有用的技巧。

自从引入 append 内置后，Go 1 中删除的 container/vector 包的大部分功能都可以使用 append 和 copy.

以下是矢量方法及其切片操作类似物：

追加向量

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]

NOTE 如果元素的类型是 pointer 或带有指针字段的结构，需要进行垃圾回收，则Cut 和 Delete 的上述实现有一个潜在的 内存泄漏 问题：一些具有值的元素仍然被 slice 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]

Delete

copy(a[i:], a[i+1:])
a[len(a)-1] = nil // or the zero value of 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]

扩张

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:]...)...)

NOTE 第二个 append 创建一个新的切片，它有自己的底层存储，并将 a[i:] 中的元素复制到该切片，然后这些元素复制回切片 a（由第一个 append）。使用替代方法可以避免创建新切片（以及内存垃圾）和第二个副本：

Insert

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

在 GO lang 中删除和添加元素到数组

Remove and adding elements to array in GO lang

arrays

append

go

slice

其他技巧

过滤而不分配

反转

洗牌