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 start of a vector?

I would like to avoid multiple removals which cause unnecessary memory copying operations.

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

---

1. I could use unsafe API's (ptr::drop_in_place, ptr::copy, Vec::set_len), but was hoping there were a more convenient way to handle this.

2. Might an alternative solution be possible where the Vec pointer is offset and the range at the start is marked as free? (no memory copying required). I now realize this requires Rust's underlying allocator to free memory by range not the initially allocated pointer, but it turns out this isn't the case.

Answer 1

Use drain to remove multiple contiguous elements from a vector at once as efficiently as possible (the implementation uses ptr::copy to move the elements that remain):

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

Regarding #2, it is not feasible to avoid shifting the remaining elements. That optimization would require changes to the representation of the vector, changes to the allocator, or both, and all for a use case the vector is not designed to cover. If you need efficient removal from the front, use a VecDeque.

Vec is represented by a triple comprising <pointer-to-first-element, capacity, length>. If removal from the front avoided shifting the remaining elements by moving the start pointer forward, deallocation would crash because the start pointer would no longer be the one provided by the allocator. Either the vector would need to get a new field for "original pointer", which would make all vectors pay for the optimization, or the allocation interface would need to be extended with a method for freeing the beginning of a block. Every front removal would call into the allocator, which would have performance consequences that are hard to assess, given that the allocator must perform its own bookkeeping and possibly acquire a lock. It would also add burden to the allocator, requiring it to keep track of these potentially tiny unaligned free blocks positioned before the blocks it originally delivered. It would also make vectors incompatible with virtually all native allocators such as malloc() and mmap().

Finally, the optimization would contradict the guarantees currently provided by Vec. The documentation explicitly states that shrinking a Vec will not reduce its capacity or deallocate it, unless a call to shrink_to_fit is made. This is to avoid excessive allocations for vectors that shrink and grow a lot.