如何从 Rust 中的 Vec 获取项目？

Question

我正在寻找一种方法，消耗一个

Vec

并返回一个元素，而无需像

Vec

和

remove

那样恢复

swap_remove

的不变量的开销：

fn take<T>(vec: Vec<T>, index: usize) -> Option<T>

但是，我找不到这样的方法。我错过了什么吗？这实际上不安全或不可能吗？

这是一个与以*安全*方式移出Vec不同的问题？ 目标是一个

remove

方法，不会因越界访问而恐慌并返回

Result

。我正在寻找一种消耗

Vec

并返回其中一个元素的方法。上述问题的答案都没有解决我的问题。

Answer 1

你可以这样写你的函数：

fn take<T>(mut vec: Vec<T>, index: usize) -> Option<T> {
    if vec.get(index).is_none() {
        None
    } else {
        Some(vec.swap_remove(index))
    }
}

您在这里看到的代码（

get

和

swap_remove

）保证是O(1)。

但是，有点隐藏，

vec

在函数末尾被删除，并且这个删除操作可能不是O(1)，而是O(n)（其中n是

vec.len()

）。如果

T

实现

Drop

，则对仍在向量内的每个元素调用

drop()

，这意味着删除向量的时间复杂度为 O(n)。如果

T

没有实现

Drop

，那么

Vec

只需要释放内存即可。

dealloc

操作的时间复杂度取决于分配器并且没有指定，所以我们不能假设它是O(1)。

---

提一下使用迭代器的另一种解决方案：

fn take<T>(vec: Vec<T>, index: usize) -> Option<T> {
    vec.into_iter().nth(index)
}

虽然

Iterator::nth()

通常是一个线性时间操作，但向量上的迭代器覆盖此方法以使其成为O(1)操作。当然，如果

T

实现

Drop

，这又是一个 O(n) 函数，因为需要删除 n 个元素。

Answer 2

标准库中不存在

fn take<T>(vec: Vec<T>, index: usize) -> Option<T>

的原因是它一般来说不是很有用。例如，假设你有一个长度为 10 的

Vec<String>

，这意味着扔掉 9 根字符串，只使用 1 根。这看起来很浪费。

一般来说，标准库会尝试提供一个在最多情况下有用的 API，在这种情况下，拥有一个

fn take<T>(vec: &mut Vec<T>, index: usize) -> Option<T>

会更合乎逻辑。

当然，唯一的问题是如何保持不变性：

• 可以通过与最后一个元素交换来保留它，这就是

  Vec::swap_remove

  所做的，
• 可以通过移入后继元素来保留它，这就是

  Vec::drain

  的作用。

这些非常灵活，可以适应更具体的场景，例如您的场景。

---

适应

swap_remove

：

fn take<T>(mut vec: Vec<T>, index: usize) -> Option<T> {
    if index < vec.len() {
        Some(vec.swap_remove(index))
    } else {
        None
    }
}

适应

drain

：

fn take<T>(mut vec: Vec<T>, index: usize) -> Option<T> {
    if index < vec.len() {
        vec.drain(index..index+1).next()
    } else {
        None
    }
}

注意前者效率更高：O(1)。

---

我正在寻找一种消耗

Vec

并返回一个元素的方法，而无需像

Vec

和

remove

那样恢复

swap_remove

的不变量的开销。

这对我来说有点过早的微优化的味道。

首先注意，要销毁向量的元素；您可以通过两种方式完成此操作：

1. swap_remove

   ，然后迭代每个元素以销毁它们，
2. 迭代每个元素以销毁它们，跳过特定的

   index

   。

我不清楚后者是否会比前者更快；如果有什么不同的话，它看起来更复杂，有更多分支（我建议使用两个循环），这可能会抛弃预测器，并且可能不太适合矢量化。

其次，在抱怨恢复

Vec

不变量的开销之前，你是否正确地分析了解决方案？

如果我们看一下

swap_remove

变体，有 3 个步骤：

1. swap_remove

   (O(1)),
2. 销毁每个剩余元素 (O(N)),
3. 释放后备内存。

如果元素没有

Drop

实现，则步骤 2 可能会被优化，但否则我会觉得（2）或（3）是否主导成本是一个折腾。

TL;DR：我担心你正在与幽灵问题作斗争，profile在尝试优化之前。

Answer 3

如果您的类型

T

实现了

Default

特征，那么大多数 Rust 标准库类型都是这种情况 - 除了极少数情况，例如。元组长度超过十二项 -

std::mem::take

几乎符合您的要求：

fn take<T: std::default::Default>(mut vec: Vec<T>, index: usize) -> Option<T> {
    if index < vec.len() {
        Some(std::mem::take(&mut vec[index]))
    }
    else {
        None
    }
}