What is the idiomatic way to remove the first N elements in a mutable Vec?

Question

Is there a good way to remove multiple elements at the beginning of a vector?

I would like to avoid multiple deletions that cause unnecessary memory copy operations.

while vec.len() > n { vec.remove(0); } 

---

• I could use an unsafe API ( ptr::drop_in_place , ptr::copy , Vec::set_len ), but hoped there was a more convenient way to handle this.

• Is an alternative solution possible if the Vec pointer is offset and the range at the beginning is marked as free? (no memory copy required). Now I understand that this requires a Rust basic allocator in order to free memory by range, rather than the initially allocated pointer, but it turns out that this is not so.

Answer 1

Use drain to remove several adjacent elements from the vector as efficiently as possible (the implementation uses ptr::copy to move the remaining elements):

 let mut v = vec![1, 2, 3, 4]; v.drain(0..2); assert!(v == vec![3, 4]); 

As for No. 2, it is impossible to avoid the displacement of the remaining elements. This optimization will require changes in the presentation of the vector, changes in the distributor, or both, and for all use the vector is not intended to be covered. If you need effective removal from the front, use VecDeque .

Vec is represented by a triple containing <a pointer to the first element, capacity, length> . If the removal from the front did not allow the remaining elements to be moved by moving the start pointer forward, the reset will fail because the start pointer will no longer be provided by the dispenser. Either the vector will need to get a new field for the "source pointer", which forces all vectors to pay for optimization, or the selection interface should be expanded using the method of freeing the beginning of the block. Each deletion in the front caused the dispenser, which would have performance implications that are difficult to evaluate, given that the dispenser must run its own account and possibly acquire a lock. This would also add to the load on the dispenser, requiring it to keep track of these potentially tiny unconnected free blocks located in front of the blocks that it originally supplied. This will also make the vectors incompatible with almost all native distributors, such as malloc() and mmap() .

Finally, optimization will run counter to the guarantees currently provided by Vec . The documentation explicitly states that Vec compression will not reduce its capacity or release it, unless the shrink_to_fit call. This is done in order to avoid excessive distributions for vectors, which greatly contract and grow.

Answer 2

If you are inclined to use Vec directly, then @ user4815162342 explained why what you are asking for is not possible.

However, if (1) you really need efficient removal from the front and (2) the adjacency value, so that VecDeque not suitable, then you can also create your own container. I once had those (two) strict requirements in C ++, and C ++ in this case is much more dangerous than Rust.

The basic structure:

 struct DVec<T> { data: *mut T, length: usize, offset: usize, capacity: usize, _marker: PhantomData<T>, } 

Depending on your requirements, you can reduce the size down by using u32 instead of usize (which still allows you to use 4 billion elements!).

After that, DVec::drain(..n) and DVec::drain(0..n) are implemented by bumping offset by n .

This data structure offers an interface similar to VecDeque , with the following changes:

• data is stored contiguously, so it implements Deref<Target = [T]> ,
• The element insert at both ends is amortized O (1),
• removing an element from either end is O (1).

In C ++, it hurts to write because not all objects are movable, and moving can throw an exception; in Rust, all objects are movable, and moving is an exception, so it is much simpler.