我如何从Rust中的Vec取物品? [英] How can I take an item from a Vec in Rust?

问题描述

我正在寻找一种消费一个Vec并返回一个元素的方法，而没有像remove和swap_remove那样恢复Vec不变式的开销:

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< T>的方法? 那里的目标是一个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.

推荐答案

您可以这样编写函数:

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为).如果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屋！