Efficiently insert or replace multiple elements in the middle or at the beginning of a Vec?

Question

Is there any straightforward way to insert or replace multiple elements from &[T] and/or Vec<T> in the middle or at the beginning of a Vec in linear time?

I could only find std::vec::Vec::insert, but that's only for inserting a single element in O(n) time, so I obviously cannot call that in a loop.

I could do a split_off at that index, extend the new elements into the left half of the split, and then extend the second half into the first, but is there a better way?

Answer 1

As of Rust 1.21.0, Vec::splice is available and allows inserting at any point, including fully prepending:

let mut vec = vec![1, 5]; let slice = &[2, 3, 4];  vec.splice(1..1, slice.iter().cloned());  println!("{:?}", vec); // [1, 2, 3, 4, 5] 

The docs state:

Note 4: This is optimal if:

• The tail (elements in the vector after range) is empty
• or replace_with yields fewer elements than range’s length
• or the lower bound of its size_hint() is exact.

In this case, the lower bound of the slice's iterator should be exact, so it should perform one memory move.

---

splice is a bit more powerful in that it allows you to remove a range of values (the first argument), insert new values (the second argument), and optionally get the old values (the result of the call).

Replacing a set of items

let mut vec = vec![0, 1, 5]; let slice = &[2, 3, 4];  vec.splice(..2, slice.iter().cloned());  println!("{:?}", vec); // [2, 3, 4, 5] 

Getting the previous values

let mut vec = vec![0, 1, 2, 3, 4]; let slice = &[9, 8, 7];  let old: Vec<_> = vec.splice(3.., slice.iter().cloned()).collect();  println!("{:?}", vec); // [0, 1, 2, 9, 8, 7] println!("{:?}", old); // [3, 4]