如何从Rust中的Vec中取出物品？

Question

我想要的是这样的方法:

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

但是,我找不到这样的方法.我错过了什么吗？或者有一个原因,这实际上是不安全的/无法正确完成.

编辑:这是一个与内置*安全*方式移出Vec <T>的不同问题？ 那里的目标是一个Vec没有超出边界访问的方法(而是返回一个Result).这里我正在寻找一个消耗Vec的方法,并返回其中一个元素.上述问题的答案都没有解决我的问题.

编辑2:为了进一步澄清,我正在寻找一种消耗 Vec并返回一个元素的方法,而没有恢复Vec不变量的方法Vec和remove做法.

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))
    }
}

这是保证O(1).

提到使用迭代器的另一种解决方案:

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

我正要写这个:

虽然get通常是线性时间操作,但是向量上的迭代器会覆盖此方法以使其成为O(1)操作.

但后来我注意到,这只适用于迭代切片的迭代器.swap_remove将在上面的代码中使用的迭代器不会覆盖vec.这里已经尝试过,但似乎并不那么容易.

所以:截至目前,上面的代码是O(n)操作!

Answer 2

标准库中不存在的原因fn take<T>(vec: Vec<T>, index: usize) -> Option<T>是它一般来说不是很有用。例如，假设 a 的Vec<String>长度为 10，则意味着扔掉 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这种方式恢复 的不变量的开销。removeswap_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：恐怕您正在与幽灵问题作斗争，请在尝试优化之前进行配置文件。