Databases
StackOverflow2013
Postsdbo
POShould use an insertion sort or construct a heap to improve performance?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POShould use an insertion sort or construct a heap to improve performance?
    text
    copied!<p>We have large (100,000+ elements) ordered vectors of structs (operator &lt; overloaded to provide ordering):</p> <pre><code>std::vector &lt; MyType &gt; vectorMyTypes; std::sort(vectorMyType.begin(), vectorMyType.end()); </code></pre> <p>My problem is that we're seeing performance problems when adding new elements to these vectors while preserving sort order. At the moment we're doing something like:</p> <pre><code>for ( a very large set ) { vectorMyTypes.push_back(newType); std::sort(vectorMyType.begin(), vectorMyType.end()); ... ValidateStuff(vectorMyType); // this method expects the vector to be ordered } </code></pre> <p>This isn't <em>exactly</em> what our code looks like since I know this example could be optimised in different ways, however it gives you an idea of how performance could be a problem because I'm sorting after every <code>push_back</code>.</p> <p>I think I essentially have two options to improve performance:</p> <ol> <li><p>Use a (hand crafted?) <em>insertion sort</em> instead of <code>std::sort</code> to improve the sort performance (insertion sorts on a partially sorted vector are blindingly quick)</p></li> <li><p>Create a heap by using <code>std::make_heap</code> and <code>std::push_heap</code> to maintain the sort order</p></li> </ol> <p>My questions are:</p> <ul> <li><p><strong>Should I implement an insertion sort? Is there something in Boost that could help me here?</strong></p></li> <li><p><strong>Should I consider using a heap? How would I do this?</strong></p></li> </ul> <hr> <p><strong>Edit:</strong></p> <p>Thanks for all your responses. I understand that the example I gave was far from optimal and it doesn't fully represent what I have in my code right now. It was simply there to illustrate the performance bottleneck I was experiencing - perhaps that's why this question isn't seeing many up-votes :)</p> <p>Many thanks to you <a href="https://stackoverflow.com/users/13005/">Steve</a>, it's often the simplest answers that are the best, and perhaps it was my over analysis of the problem that blinded me to perhaps the most obvious solution. I do like the neat method you outlined to insert directly into a pre-ordered vector.</p> <p>As I've commented, I'm constrained to using vectors right now, so std::set, std::map, etc aren't an option.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload