在 Go 中使用 append 进行前置的机制是什么？

Question

假设我有一个slice类型的切片int。在声明时，我将第三个参数设置为size，我相信size通过设置cap切片的参数为至少整数保留内存。

slice:=make([]int,0,size)

现在，假设我有一个整数变量value。要将其添加到最后的切片中，我使用

slice=append(slice,value)

如果当前切片中的元素数小于size，则无需将整个底层数组复制到新位置以添加新元素。

另外，如果我想在前面加上value到slice，作为建议在这里和这里，我用

slice=append([]int{value},slice...)

我的问题是，在这种情况下会发生什么？如果元素数量仍然小于size，元素如何存储在内存中？假设make()在调用函数时进行了连续分配，是否所有现有元素都右移以释放第一个空间以获取值？还是重新分配内存并复制所有元素？

问的原因是我希望我的程序尽可能快，并且想知道这是否是减慢它的可能原因。如果是这样，是否有任何替代方法可以更节省时间？

Answer 1

通过重新切片和复制

内置函数append()总是将元素附加到切片。您不能（单独）使用它来添加元素。

话虽如此，如果您的切片容量大于长度（其元素后有“空闲”空间）并希望在其中添加元素，您可以重新切片原始切片，将所有元素复制到一个更高的索引以腾出空间对于新元素，然后将该元素设置为第 0^个索引。这将不需要新的分配。这是它的样子：

func prepend(dest []int, value int) []int {
    if cap(dest) > len(dest) {
        dest = dest[:len(dest)+1]
        copy(dest[1:], dest)
        dest[0] = value
        return dest
    }

    // No room, new slice need to be allocated:
    // Use some extra space for future:
    res := make([]int, len(dest)+1, len(dest)+5)
    res[0] = value
    copy(res[1:], dest)
    return res
}

测试它：

s := make([]int, 0, 5)
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)

输出（在Go Playground上试试）：

[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]

注意：如果没有新元素的空间，因为性能现在很重要，我们不只是做：

res := append([]int{value}, dest...)

因为它进行了比需要更多的分配和复制：为文字 ( []int{value})分配一个切片，然后append()在附加dest到它时分配一个新的切片。

相反，我们的解决方案只分配一个新数组（通过make()，甚至为将来的增长保留一些空间），然后将其设置value为第一个元素并复制dest（之前的元素）。

带链表

如果您需要多次添加，普通切片可能不是正确的选择。一种更快的替代方法是使用链表，在该链表中添加元素不需要分配切片/数组和复制，您只需创建一个新的节点元素，然后通过将其指向旧的根来将其指定为根（第一个元素）。

标准库在container/list包中提供了通用实现。

手动管理更大的后备阵列

坚持使用普通切片和数组，还有另一种解决方案。

如果您愿意自己管理更大的后备数组（或切片），则可以通过在使用的切片之前留出可用空间来实现。预置时，您可以从支持的较大数组或切片中创建一个新的切片值，该值从一个索引开始，为 1 个要预置的元素留出空间。

不完整，仅作演示：

var backing = make([]int, 15) // 15 elements
var start int

func prepend(dest []int, value int) []int {
    if start == 0 {
        // No more room for new value, must allocate bigger backing array:
        newbacking := make([]int, len(backing)+5)
        start = 5
        copy(newbacking[5:], backing)
        backing = newbacking
    }

    start--
    dest = backing[start : start+len(dest)+1]
    dest[0] = value
    return dest
}

测试/使用它：

start = 5
s := backing[start:start] // empty slice, starting at idx=5
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)

// Prepend more to test reallocation:
for i := 10; i < 15; i++ {
    s = prepend(s, i)
}
fmt.Println(s)

输出（在Go Playground上试试）：

[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]
[14 13 12 11 10 8 9 1 2 3 4]

分析：当backing切片中有空间来添加值时，此解决方案不会进行分配和复制！所发生的一切是它从backing覆盖目标 +1 空间的切片创建一个新切片，以用于要预先添加的值，设置它并返回此切片值。你真的不能比这更好了。

如果没有空间，那么它分配一个更大的backing切片，复制旧的内容，然后进行“正常”前置。

使用棘手的切片

想法：想象一下，你总是以倒序将元素存储在切片中。

在切片中以向后的顺序存储元素意味着 prepand 变为 append！

所以要“预加”一个元素，你可以简单地使用append(s, value). 就这样。

是的，这有其有限的用途（例如，附加到以相反顺序存储的切片具有与“正常”切片和前置操作相同的问题和复杂性），并且您失去了许多便利（for range仅使用命名一个元素来列出元素的能力） ，但在性能方面没有什么比仅使用append().

注意：迭代以向后顺序存储元素的元素必须使用向下循环，例如：

for i := len(s) - 1; i >= 0; i-- {
    // do something with s[i]
}

最后说明：所有这些解决方案都可以轻松扩展为预先添加一个切片而不仅仅是一个值。通常，重新切片时的额外空间不是+1但是+len(values)，也不是简单的设置dst[0] = value而是调用copy(dst, values).