How can I take an item from a Vec in Rust?

by

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

The code you see here (get and swap_remove) is guaranteed 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)
}

I was about to write this:

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

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.

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.

More Related Contents:

  1. Simultaneous mutable access to arbitrary indices of a large vector that are guaranteed to be disjoint
  2. What is the best way to concatenate vectors in Rust?
  3. Using max_by_key on a vector of floats [duplicate]
  4. How can a function append a value to a vector and also return that value?
  5. How to filter a vector of custom structs?
  6. How to enforce move semantics when a vector grows?
  7. Cannot move out of borrowed content / cannot move out of behind a shared reference
  8. What are move semantics in Rust?
  9. Cannot move out of borrowed content when trying to transfer ownership
  10. Is a moved-from vector always empty?
  11. How does Rust provide move semantics?
  12. How do I convert a Vec to Vec?
  13. Why is the mutable reference not moved here?
  14. How can I have a collection of objects that differ by their associated type?
  15. Convert Vec into a slice of &str in Rust?
  16. Initializer-list-constructing a vector of noncopyable (but movable) objects
  17. packed vs unpacked vectors in system verilog
  18. three.js set and read camera look vector
  19. How can I initialize an array using a function? [duplicate]
  20. Vector vs Collections.synchronizedList(ArrayList)
  21. Clojure Remove item from Vector at a Specified Location
  22. Why does the compiler not complain that an iterator moved to a for loop is immutable?
  23. Can Rust optimise away the bit-wise copy during move of an object someday?
  24. count vs length vs size in a collection
  25. What is the return type of the indexing operation?
  26. I implemented a trait for another trait but cannot call methods from both traits
  27. Append value to empty vector in R?
  28. Temporary value is freed at the end of this statement [duplicate]
  29. Convert two types into a single type with Serde
  30. Move semantics == custom swap function obsolete?

Leave a Comment