Rust 如何为向量分配更多空间？

Question

考虑以下代码：

fn main() {
  let mut vec: Vec<u8> = Vec::new();
  vec.push(0);
  vec.push(1);
  vec.push(2);
  vec.push(3);
  vec.push(4);
  vec.push(5);
  vec.push(6);
  vec.push(7);
  vec.push(8);
}

当Vec::new()被调用时，Rust 不知道分配多少，每次它需要为一个向量分配更多空间时，它malloc以新的大小调用，然后将堆中旧位置的所有数据克隆到新位置，对？

Rust 知道要分配的新大小的策略是什么？

例如，每次将某些东西推送到向量上时，Rust 是否会像这样分配？

[]
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
etc...

这似乎效率低下。也许 Rust 会做这样的事情：

[]
[0, <empty>]
[0, 1] 
[0, 1, 2, <empty>, <empty>, <empty>, <empty>, <empty>]
[0, 1, 2, 3, <empty>, <empty>, <empty>, <empty>]
[0, 1, 2, 3, 4, <empty>, <empty>, <empty>]
etc...

Answer 1

在VEC文档说这个：

Vec 在已满时重新分配时或在调用 Reserve 时不保证任何特定的增长策略。当前的策略是基本的，使用非常数增长因子可能会被证明是可取的。无论使用什么策略，当然都会保证 O(1) 摊销推送。

摊销 O(1) 推送的保证意味着 Rust 不会在每次推送时重新分配。它必须看起来更像您描述的第二个场景，它分配额外的容量来为要推送的其他元素腾出空间。

如果我们深入研究 Rust 标准库的源代码，我们会看到在这种情况下（一次推送一个元素），Vec 的当前实现实际上在每次重新分配时将 Vec的容量加倍。当然，这个确切的策略并没有被指定，并且可能会在未来的实现中发生变化。

如果您从一开始就知道您的 Vec 需要多大，您可以使用Vec::with_capacity构建它以避免任何重新分配的需要。

Answer 2

Vec有长度和容量。容量是无需重新分配即可存储的元素数量Vec。当达到容量并推送新元素时，容量会增加并Vec重新分配。

该策略尚未指定，并且将来可能会发生变化。当前的策略是在必须增加容量时将容量加倍。然而，有一种特殊情况：Vec::new()不分配，但第一次压入一个元素会为最多 8 个元素分配足够的空间：

• 如果每个元素只有1个字节（例如bool或u8），则容量设置为8，即64位
• 如果元素大小在 2 字节到 1 KiB 之间，则容量设置为 4
• 否则，容量设置为 1

请注意，这是一个实现细节，可能会发生变化。事实上，最近情况发生了变化。