在 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内置函数以来container/vector，在 Go 1 中删除的包的大部分功能都可以使用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]

注意如果元素的类型是一个指针或指针字段，其需要被垃圾收集一个结构，上述实施方式Cut和Delete有潜在的存储器泄露的问题：其值的一些元素仍然由切片引用a并因此不能集。下面的代码可以解决这个问题：

切

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]

}

洗牌

费雪-耶茨算法：

for i := len(a) - 1; i > 0; i-- {

    j := rand.Intn(i + 1)

    a[i], a[j] = a[j], a[i]

}