# An API for multiple vec insertion?

Is there a crate or API for performing linear time multiple insertion into a vector? Here's an implementation:

``````struct VecPatch<T>(SmallVec<[(usize, T); 2]>);

impl<T> VecPatch<T> {
fn new() -> Self { Self(SmallVec::new()) }

fn insert(&mut self, idx: usize, val: T) { self.0.push((idx, val)) }

fn apply(self, vec: &mut Vec<T>) {
self.0.sort_by_key(|p| p.0);
vec.reserve(self.0.len());
let mut end = vec.len();
let mut diff = self.0.len();
let new_len = end + diff;
for (i, val) in self.0.into_iter().rev() {
assert!(i <= end, "index out of bounds");
let p = unsafe { vec.as_mut_ptr().add(i) };
unsafe { std::ptr::copy(p, p.add(diff), end - i); }
diff -= 1;
end = i;
}
unsafe { vec.set_len(new_len); }
}
}

#[test] fn foo() {
let mut vec = vec![1,4,2,6,8,2];
let mut patch = VecPatch::new();
patch.insert(0, 10);
patch.insert(2, 11);
patch.insert(2, 12);
patch.insert(4, 13);
patch.insert(6, 14);
patch.apply(&mut vec);
assert_eq!(vec, [10, 1, 4, 11, 12, 2, 6, 13, 8, 2, 14])
}
``````

You can use `Vec::splice` with an empty range such as `4..4`.

``````fn main() {
let mut v = vec![1, 2, 3, 4];

v.splice(2..2, [10, 10, 10].iter().copied());

println!("{:?}", v);
}
``````
``````[1, 2, 10, 10, 10, 3, 4]
``````

I did find that function in my investigations, but it only handles insertions into a single contiguous range in the vector. To do the equivalent of `VecPatch` would require several, possibly linearly many, calls to `splice`.

I’m not aware of any crate offering this, but I haven’t searched for it either. Possible improvements to your code:

• fix the compile error of not writing `mut self`
• only do the `i <= end` assertion for the largest `i`. Assertion failures after the first iteration of the loop can’t happen and panicking would be fatal anyways since the `Vec` is already in an invalid intermediate state.

Ah, both issues are a side effect of the late addition of the `sort_by_key`. In my application I know the inserts are already ordered so it isn't needed.

Maybe I'll make a crate for it myself then. I haven't written a utility crate like this before, seems like everything has already been done before somewhere in crates.io.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.