如何从 Rust 中的 Vec 获取项目? [英] How can I take an item from a Vec in Rust?

问题描述

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

I'm looking for a method that consumes a Vec and returns one element, without the overhead of restoring Vec's invariants the way remove and swap_remove do:

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

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

However, I can't find such a method. Am I missing something? Is this actually unsafe or impossible?

这是一个与 内置 *safe* 不同的问题搬出 Vec 的方法?那里的目标是一个 remove 方法，它不会因越界访问而恐慌并返回一个 Result.我正在寻找一种使用 Vec 并返回其中一个元素的方法.上述问题的答案都没有解决我的问题.

This is a different question from Built in *safe* way to move out of Vec<T>? There the goal was a remove method that didn't panic on out of bounds access and returned a Result. I'm looking for a method that consumes a Vec and returns one of the elements. None of the answers to the above question address my question.

推荐答案

你可以这样写你的函数:

You can write your function like this:

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

The code you see here (get and swap_remove) is guaranteed O(1).

然而，有点隐藏，vec 在函数的末尾被删除，这个删除操作可能不是 O(1)，而是 O(n) (其中 n 是 vec.len()).如果 T 实现了 Drop，那么 drop() 会为仍在向量中的每个元素调用，这意味着删除向量是保证 O(n).如果T没有实现Drop，那么Vec只需要释放内存.dealloc 操作的时间复杂度取决于分配器并且没有指定，所以我们不能假设它是 O(1).

However, kind of hidden, vec is dropped at the end of the function and this drop operation is likely not O(1), but O(n) (where n is vec.len()). If T implements Drop, then drop() is called for every element still inside the vector, meaning dropping the vector is guaranteed O(n). If T does not implement Drop, then the Vec only needs to deallocate the memory. The time complexity of the dealloc operation depends on the allocator and is not specified, so we cannot assume it is O(1).

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

To mention another solution using iterators:

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

我正要写这个:

虽然Iterator::nth() 通常是一个线性时间操作，但向量上的迭代器会覆盖此方法，使其成为 O(1) 操作.

While Iterator::nth() usually is a linear time operation, the iterator over a vector overrides this method to make it a O(1) operation.

但后来我注意到，这仅适用于迭代切片的迭代器.上面代码中使用的 std::vec::IntoIter 迭代器不会覆盖 nth().已经在此处尝试过，但似乎并不那么容易.

But then I noticed, that this is only true for the iterator which iterates over slices. The std::vec::IntoIter iterator which would be used in the code above, doesn't override nth(). It has been attempted here, but it doesn't seem to be that easy.

所以，截至目前，上面的迭代器解决方案是一个 O(n) 操作！更不用说删除向量所需的时间了，如上所述.

So, as of right now, the iterator solution above is a O(n) operation! Not to mention the time needed to drop the vector, as explained above.

这篇关于如何从 Rust 中的 Vec 获取项目?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！