我该如何从Rust的Vec中取出一个元素？

Question

我正在寻找一种方法，可以消耗一个Vec并返回一个元素，而不需要像remove和swap_remove那样恢复Vec的不变量开销:

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

然而，我找不到这样的方法。我有什么遗漏吗？这是否实际上是不安全或不可能的？

这与从Vec<T>中移出元素的内置*安全*方法？是不同的问题。 那里的目标是一个remove方法，它不会在超出边界访问时引发恐慌，并返回Result。我正在寻找一种消耗Vec并返回其中一个元素的方法。上述问题的任何答案都没有回答我的问题。

- Others

---

你是指特别的Option<T>而不是从vec.get(index)得到的Option<&T>，还是你忽略了.get的存在？ - loganfsmyth

@loganfsmyth 我特别指的是像我问题中所说的 Option<T>。我的意思是，我想要类似于 option.take() 的功能，如果这样说有意义的话？ - Others

注意：如果你经常需要使用 Vec，你可能需要看看是否可以避免一开始就将它们实例化。不做任何事情总是比做任何事情都要快，无论你在做什么时有多么高效。 - Matthieu M.

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 个元素。

- Lukas Kalbertodt

---

啊，这个解决方案有点丑陋，但我认为它应该能够工作！我仍然认为在Vec上添加一个“take”方法会很棒... - Others

@其他人 也许你应该开一个 RFC。 - Boiethios

第一个解决方案中将mut vec: Vec<T>更改为vec: &mut Vec<T>如何？ - lukwol

@lukwol：为什么？原帖明确要求消耗向量。 - Matthieu M.

我不知道回答写作时的情况，但截至今天，into_iter().nth() 的时间复杂度是O(1)，除非这些项实现了 Drop - 但这也适用于 "swap_remove() 然后丢弃 Vec" 的方法。 - Chayim Friedman

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并返回一个元素，而无需像remove和swap_remove那样恢复Vec的不变性开销。

这似乎是过早的微观优化。

首先，请注意需要销毁向量的元素；您可以通过两种方式实现：

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

我不确定后者是否比前者更快；如果有什么区别，它看起来更加复杂，有更多分支（我建议使用两个循环），这可能会使预测器失效，并且可能不利于矢量化。

其次，在抱怨恢复Vec的不变性开销之前，您是否正确地进行了分析？

如果我们查看swap_remove变体，有3个步骤：

1. swap_remove（O(1)），
2. 销毁每个剩余元素（O(N)），
3. 释放支持内存。

如果元素没有Drop实现，则步骤2可以优化掉，但否则我认为（2）或（3）哪个占主导成本是不确定的。

简而言之：我担心您正在解决虚假问题，请在尝试优化之前进行分析。

- Matthieu M.

---

我并不仅仅抱怨恢复Vec的不变性所带来的开销（尽管我正在处理的代码位于紧密的内部循环中，因此速度确实对我很重要），我还想编写符合我的意图的代码。在这种情况下，我真的想表达“take”操作，而不是“remove”操作。即使这只是一个速度问题，我也需要另一种替代方案进行性能分析。 - Others

@其他人: "紧密的内部循环"和"删除Vec"听起来不太好。当你编写代码时，我鼓励你将其发布到Code Reviews或Reddit，并询问如何优化它；希望有一种方法可以避免在内部循环中进行内存释放，因为这些操作是昂贵的。 - Matthieu M.