title: Most efficient way to sort one element in a vector?
body: <p>I have a vector of elements which are sorted based some external value. It is a large container and looking up the sort-value is relatively expensive. At some point one element (only) needs to be re-sorted. What is the most efficient way to just re-sort that element? <code>std::sort()</code> the vector? erase-insert the element? compare the element to its immediate neighbours?</p>
  
  <p>EDIT: to clarify, by erase-insert the element I mean something like this:</p>
  
  <pre><code>// erase the key and then insert-sort it
  auto iter = std::find(keys.begin(), keys.end(), key);
  
  keys.erase(iter);
  SortedInsert(keys, index, &lt;cmp&gt;);
  </code></pre>
  
  <p>EDIT2: the container needs to be a vector for other performance reasons</p>