vector - 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上的文档说this:

Vec does not guarantee any particular growth strategy when reallocating when full, nor when reserve is called. The current strategy is basic and it may prove desirable to use a non-constant growth factor. Whatever strategy is used will of course guarantee O(1) amortized push.

摊销O(1)推送的保证意味着Rust不会在每次推送时重新分配。它必须看起来更像您描述的第二种情况，在该方案中，它分配了额外的容量，以便为要推送的其他元素腾出空间。
如果我们深入研究Rust标准库的源代码，我们将看到在这种情况下(一次按下一个元素)，实际上是Vec的当前实现，即每次重新分配时Vec的doubles the capacity。当然，没有指定此确切策略，并且在将来的实现中可能会更改。
如果从一开始就知道Vec的大小，则可以使用Vec::with_capacity构造它，以避免需要任何重新分配。