如何在 Swift 内存中处理 var 数组的更新（对 CoW 感到困惑）

Question

我有这个功能可以在按降序对数字进行排序时进行快速选择分区。该函数引用在其范围之外定义的

arr

（分区是另一个函数中的嵌套函数）。

我的问题是，由于 Swift 中的数组是值类型，当我进行交换时，每次都会创建一个新副本吗？还是同一个内存被覆盖了？

将函数定义为

partition(start: Int, end: Int, arr: inout [(Int, Int)])

是不是更好，这样 arr 就可以通过引用传递？

后续问题，当我们这样做

arr.append((4, 8))

时会发生什么？这会在内存中创建一个新副本吗？

var arr = [(Int, Int)]() // [(1, 2), (3, 5), (2, 8)]
func partition(start: Int, end: Int) -> Int {
    var swap = start 

    for i in start..<end {
        if arr[i].1 > arr[end].1 {
            (arr[i], arr[swap]) = (arr[swap], arr[i]) // arr copied on write?
            swap += 1
        }
    }
    (arr[end], arr[swap]) = (arr[swap], arr[end]) // arr copied on write?
    return swap
}

Answer 1

您似乎误解了在这种情况下写时复制的含义。我们说 Swift 数组是写时复制，并不是因为每次我们写入它时，都会创建一个副本。

写时复制意味着“在写入时复制”，而不是“在其他时间时复制”。您可能将其误解为“写入时复制”，而不是“写入时保持使用相同的存储”。如果这样的话，就不会被称为“优化”:)

考虑

var foo = bar

，其中

foo

和

bar

是数组。

bar

的内容不会复制到

foo

，因为没有 writes。

foo

和

bar

共享相同的内部缓冲区，直到

bar

或

foo

被写入，此时将创建一个副本。

另请参阅 文档，了解

Array

：

数组，像标准库中的所有可变大小集合一样， 使用写时复制优化。数组的多个副本共享 相同的存储，直到您修改其中一个副本。当这种情况发生时， 正在修改的阵列将其存储替换为唯一拥有的 其自身的副本，然后就地修改。优化是 有时应用可以减少复印量。

这意味着如果一个阵列与其他副本共享存储，则 该数组上的第一次变异操作会产生复制数组的成本 大批。作为其存储的唯一所有者的阵列可以执行 变异操作到位。

如果像您的代码中一样，只有一个数组变量，则不需要副本。所有写入都可以写入同一数组的内部缓冲区。

如果您在调用

arr

之前先将

partition

分配给另一个变量，则将在第一次交换时创建一个副本，此后不再创建副本。

至于调用

append

，数组可能需要增长其

capacity

来追加新元素。如果

count == capacity

，则需要分配新的内存。这可能涉及重新定位数组的内容，您可以将其视为“复制”：

当一个数组在追加之前需要重新分配存储或者其存储与另一个副本共享时，追加的时间复杂度为 O(n)，其中 n 是数组的长度。