rust - 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?

question from:https://stackoverflow.com/questions/28678615/efficiently-insert-or-replace-multiple-elements-in-the-middle-or-at-the-beginnin

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]