An API for multiple vec insertion?

help
1

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;
      unsafe { std::ptr::write(p.add(diff), val); }
      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])
}
2

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]
3

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.

4

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.
5

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.

6

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.