Most efficient way to sort one element in a vector?
<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>