vector - 删除可变 Vec 中前 N 个元素的惯用方法是什么？

Question

有没有什么好的方法可以去除vector开头的多个元素？

我想避免多次删除导致不必要的内存复制操作。

while vec.len() > n {
    vec.remove(0);
}

---

1. 我可以使用不安全的 API(ptr::drop_in_place、ptr::copy、Vec::set_len)，但是希望有更方便的方法来处理这个问题。

2. 如果 Vec 指针偏移并且开始的范围被标记为空闲，是否有可能的替代解决方案？ (不需要内存复制)。 我现在意识到这需要 Rust 的底层分配器按范围而不是最初分配的指针释放内存，但事实证明并非如此。

Answer 1

使用drain尽可能高效地一次从向量中删除多个连续元素(implementation 使用 ptr::copy 移动剩余的元素):

let mut v = vec![1, 2, 3, 4];
v.drain(0..2);
assert!(v == vec![3, 4]);

关于#2，避免移动剩余元素是不可行的。该优化将需要更改向量的表示和/或分配器，并且所有这些都是针对向量不旨在涵盖的用例。如果您需要从前面高效移除，请使用 VecDeque .

Vec 由包含 < pointer-to-first-element, capacity 的三元组表示, length >。如果从前面移除通过向前移动起始指针来避免移动剩余元素，则释放将崩溃，因为起始指针将不再是分配器提供的指针。要么向量需要为“原始指针”获取​​一个新字段，这将使所有向量为优化付出代价，要么分配接口(interface)需要扩展为释放 block 开头的方法。 每次 前端删除都会调用分配器，这将产生难以评估的性能后果，因为分配器必须执行自己的簿记并可能获取锁。它还会增加分配器的负担，要求它跟踪位于它最初交付的 block 之前的这些潜在的微小未对齐空闲 block 。它还会使向量与几乎所有 native 分配器不兼容，例如 malloc() 和 mmap()。

最后，优化将与 Vec 当前提供的保证相矛盾。文档 explicitly states缩小 Vec 不会减少其容量或释放它，除非调用 shrink_to_fit制成。这是为了避免对收缩和增长很多的向量进行过度分配。