What's the most efficient way to insert an element into a sorted vector?

Question

I have a sorted v: Vec<EventHandler<T>> and I want to insert an element into it while keeping it sorted. What's the most efficient way to do so? Rust doesn't seem to have a built-in way to do it.

EventHandler<T> is as follows:

struct EventHandler<T: Event + ?Sized> {     priority: i32,     f: fn(&mut T), } 

Because of how sorting works, inserting and sorting would be inefficient, with O(n log n) time complexity and 2*n allocation cost.

Answer 1

The task consists of two steps: finding the insert-position with binary_search and inserting with Vec::insert():

match v.binary_search(&new_elem) {     Ok(pos) => {} // element already in vector @ `pos`      Err(pos) => v.insert(pos, new_elem), } 

If you want to allow duplicate elements in your vector and thus want to insert already existing elements, you can write it even shorter:

let pos = v.binary_search(&new_elem).unwrap_or_else(|e| e); v.insert(pos, new_elem); 

---

But: be aware that this has a runtime complexity of O(n). To insert into the middle, the vector has to move every element right of your insert-position one to the right.

So you shouldn't use it to insert more than a few elements into a vector, which isn't tiny in size. Particularly, you shouldn't use this method to sort a vector, as this insertion sort algorithm runs in O(n²).

A BinaryHeap might be a better choice in such a situation. Each insert (push) has a runtime complexity of just O(log n) instead of O(n). You can even convert it into a sorted Vec with into_sorted_vec(), if you so desire. You can also continue to use the heap instead of converting it.