如何以惯用方式在可变的Vec中删除前N个元素？

Question

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

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

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

---

1. 我可以使用不安全的API（ptr::drop_in_place、ptr::copy、Vec::set_len）来处理这个问题，但我希望有一种更方便的方式来解决它。

2. 是否可能有一种替代方案，在其中Vec指针被偏移，并标记起始范围为空闲状态，而无需进行内存复制。（不需要进行内存复制）。 我现在意识到这需要Rust的底层分配器以范围而不是最初分配的指针释放内存，但事实并非如此。

- ideasman42

---

请注意，此问题与https://dev59.com/Xl4b5IYBdhLWcg3wlSdq非常相似，只是它询问向量的开始而不是结束。 - ideasman42

Answer 1

使用 drain 可以尽可能高效地一次性从向量中删除多个连续的元素（实现 使用 ptr::copy 移动剩余的元素）：

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

关于第二点，避免移动剩余元素是不可行的。这种优化需要更改向量的表示方式、分配器或两者都需要更改，并且所有这些都是为了使用案例而进行的，而向量并不设计用于覆盖这些情况。如果您需要高效地从前面删除，请使用VecDeque。

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

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

- user4815162342

---

谢谢，假设这个大概和使用(ptr::drop_in_place, ptr::copy, Vec::set_len)同样高效。 - ideasman42

@ideasman42，这确实是意图 - 有关详细信息，请参见impl Drop for Drain。编译器希望足够聪明，使循环中获取和丢弃的对象等同于ptr::drop_in_place，但如果有疑问，请测量以检查它是否适用于您的用例。 - user4815162342

注意：VecDeque 不使用连续的存储空间（它使用两个切片，这些切片指向单个连续缓冲区的连续存储空间；但这对于与 C 的交互是不足够的）。 - Matthieu M.

Answer 2

如果你一心想要直接使用Vec，那么@user4815162342已经解释了为什么你所要求的是不可能的。

然而，如果(1)你确实需要高效地从前面删除元素，且(2)连续性很重要，这时使用VecDeque就不合适了。但你可以构建自己的容器，我曾在C++中有过这两个严格的要求，而在这种情况下，C++比Rust要困难得多。

基本结构如下：

struct DVec<T> {
    data: *mut T,
    length: usize,
    offset: usize,
    capacity: usize,
    _marker: PhantomData<T>,
}

根据您的需求，您通常可以通过使用u32代替usize来缩小大小（仍然允许40亿个元素！）。

之后，DVec :: drain（..n）和DVec :: drain（0..n）通过将offset增加n来实现。

此数据结构提供与VecDeque类似的接口，具有以下更改：

• 数据以连续方式存储，因此它实现了Deref<Target =[T]>，
• 在两端插入元素的平摊复杂度为O（1），
• 在两端删除元素的复杂度为O（1）。

在C++中编写这个过程很麻烦，因为不是所有对象都可移动，移动可能会导致异常；在Rust中，所有对象都是可移动的，并且移动是无异常的，因此它要简单得多。

- Matthieu M.

---

@Shepmaster：用户页面，有些用户有更改昵称的令人讨厌的习惯，所以我更喜欢固定他们 :) - Matthieu M.

但是，如果您链接到答案，它将始终与该答案的发布者相关联，而不受名称更改的影响。如果您的答案位于其他答案之上，则链接到另一个答案提供了一种简便的跳转方式。 - Shepmaster

你可能是想用 DVec::drain(..n)。此外，仅仅增加偏移量是不够的，还必须对已排空的对象进行 drop_in_place 操作。考虑到这一点，如果对象没有实现 Drop，那么 drain(..n) 的时间复杂度为 O(1)，否则为 O(n)。但无论哪种情况，复杂度都与整个向量的大小无关，这在需要从一个巨大的数组中删除少量元素时非常重要。 - user4815162342

@user4815162342：确实，我明确表示O(1)插入和删除是指单个元素的插入和删除。这不是一个可以拼接东西的链表。 - Matthieu M.

我开始实现一个像你描述的DVec数据结构。这只是一个概念验证，以向自己展示这是可能的，它需要实现更多的方法和特性才能变得有用，但如果你感兴趣，这里是代码。 - Michael Hewson