title: What's the most efficient way to insert an element into a sorted vector?
body: <p>I have a sorted <code>v: Vec&lt;EventHandler&lt;T&gt;&gt;</code> 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.</p>
  
  <p><code>EventHandler&lt;T&gt;</code> is as follows:</p>
  
  <pre><code>struct EventHandler&lt;T: Event + ?Sized&gt; {
      priority: i32,
      f: fn(&amp;mut T),
  }
  </code></pre>
  
  <p>Because of how sorting works, inserting and sorting would be inefficient, with <a href="http://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_by" rel="noreferrer"><code>O(n log n)</code> time complexity and <code>2*n</code> allocation cost</a>.</p>