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

Question

有没有一种很好的方法可以在向量的开头删除多个元素？

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

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

---

1. 我可以使用不安全的API( ,ptr::drop_in_place,ptr::copy),Vec::set_len但希望有来处理这更方便的方式.

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

Answer 1

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

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

关于#2,避免移动剩余元素是不可行的.该优化需要更改向量的表示,更改分配器或两者,以及所有用于矢量未设计覆盖的用例.如果您需要从前面有效移除,请使用VecDeque.

Vec由包含< 指向第一元素的指针,容量,长度 > 的三元组表示.如果从前面移除避免通过向前移动开始指针来移动剩余元素,则解除分配将会崩溃,因为启动指针将不再是分配器提供的指针.向量需要获得"原始指针"的新字段,这将使所有向量为优化付费,或者需要使用释放块开头的方法来扩展分配接口.考虑到分配器必须执行自己的簿记并可能获得锁定,每次正面删除都会调用分配器,这会产生很难评估的性能影响.它还会给分配器增加负担,要求它跟踪位于最初传送的块之前的这些可能很小的未对齐空闲块.它还会使向量与几乎所有本机分配器(例如malloc()和)不兼容mmap().

最后,优化将与目前提供的保证相矛盾Vec.该文档明确指出,缩小a Vec不会减少其容量或取消分配它,除非进行调用shrink_to_fit.这是为了避免过度分配收缩和增长很多的向量.