AppendList：一个只追加列表，保留对其元素的引用

此列表允许您在持有对列表中某个元素的引用时添加新元素到末尾。它还避免了重新分配。

何时使用它？

• 您需要在列表的其他元素被借用时插入
• 您有如此多的数据，以至于 Vec 的重新分配非常显著

不应何时使用它？

• 您存储的是列表中的索引，而不是实际的引用（只需使用 Vec<T> 即可）
• Vec 的重新分配并不重要（通常是这种情况！）

有哪些功能？

• 一个 push(&self, item: T) 方法（您会期望 push(&mut self, item: T)）
• 非摊销常数时间插入和索引（通常插入是 摊销 常数时间，如 Vec，或者索引是线性时间，如 LinkedList）
• 您可以在列表中保留引用
• 只有2行不安全的代码

这让我能做什么？

以下示例无法编译，因为当调用 list.push() 时，second_element 有对 list 的引用。

let list: Vec<u32> = (1..=10).collect();

let second_element = &list[1];

list.push(11); // Push needs &mut self, but list is already borrowed

assert_eq!(*second_element, 2); // Fails to compile

但如果你只是用 AppendList 替换 Vec，一切都会正常工作！

use appendlist::AppendList;

let list: AppendList<u32> = (1..=10).collect();

let second_element = &list[1];

list.push(11); // Push only needs &self, so this works fine

assert_eq!(*second_element, 2); // All OK!

所有这些关于重新分配的是什么意思？

一般来说，Vec 非常酷，你应该默认使用它。但是它有一个弱点：当你创建它时，它会有一个有限的空间。当空间用完时，它需要重新分配：获取一块新的内存（通常是当前大小的两倍），然后复制所有内容，然后释放旧内存。

重新分配需要 O(n) 的时间：你需要复制列表中的所有 n 个元素。但是你不必经常这样做：只需要 O(log n) 次重新分配就可以进行 n 次插入（对于当前的 Vec 实现）。实际上，重新分配很少，如果你将它们分散到所有的插入中，它们只是增加了常数额外时间。这就是为什么 Rust 文档说 Vec 有 "O(1) 摊销 插入" —— 它通常需要常数时间来插入，偶尔需要线性时间，但如果将那些昂贵的插入分散到所有的便宜插入中，它仍然是常数。

重新分配还有一个问题：对 Vec 内部元素的任何引用都会失效。如果你在元素被复制时有一个对它的引用，你的引用将无法知道其新位置，仍然会指向旧位置，现在是无效内存。使用那个引用将是一个 use-after-free 漏洞，因此 Rust 强制你在推送另一个元素之前没有对 Vec 的引用，以防那个推送会重新分配。

AppendList 通过保留数据块来解决这个问题。当你推送一个新元素时，它会被添加到当前块的末尾。如果一个块满了，而不是重新分配它，AppendList 创建一个全新的空块。每个块的大小是上一个块的两倍，所以只需要 O(log n) 次分配，并且每次分配的时间是常数（对于大多数分配器）而不是线性时间。通过消除重新分配，AppendList 相比于 Vec 提供了一些好处。

• 你可以保持引用在推送时
• 你不必支付偶尔的线性重新分配和复制成本

然而，它也有一些缺点

• 索引需要更长的时间（你必须先索引到块中，然后索引到你的项目）
• CPU 缓存行为可能在块边界附近稍微差一些（因为下一个块通常不是连续的）

我应该使用这个 crate 吗？

可能不是。

一般来说，你应该只使用一个 Vec 并跟踪索引而不是引用。但如果保持引用非常重要，那么这是你的解决方案。