title: c++ Why std::multimap is slower than std::priority_queue
body: <p>I implemented an algorithm where I make use of an priority queue.
  I was motivated by this question:
  <a href="https://stackoverflow.com/questions/18913613/transform-a-stdmultimap-into-stdpriority-queue">Transform a std::multimap into std::priority_queue</a></p>
  
  <p>I am going to store up to 10 million elements with their specific priority value.</p>
  
  <p>I then want to iterate until the queue is empty.
  Every time an element is retrieved it is also deleted from the queue.</p>
  
  <p>After this I recalculate the elements pririty value, because of previous iterations it can change.</p>
  
  <p>If the value did increase I am inserting the element againg into the queue.
  This happens more often dependent on the progress. (at the first 25% it does not happen, in the next 50% it does happen, in the last 25% it will happen multiple times).</p>
  
  <p>After receiving the next element and not reinserting it, I am going to process it. This for I do not need the priority value of this element but the technical ID of this element.</p>
  
  <p>This was the reason I intuitively had chosen a <code>std::multimap</code> to achieve this, using <code>.begin()</code> to get the first element, <code>.insert()</code> to insert it and <code>.erase()</code> to remove it.
  Also, I did not intuitively choose <code>std::priority_queue</code> directly because of other questions to this topic answering that <code>std::priority_queue</code> most likely is used for only single values and not for mapped values.</p>
  
  <p>After reading the link above I reimplemented it using priority queue analogs to the other question from the link.
  My runtimes seem to be not that unequal (about an hour on 10 mio elements).
  Now I am wondering why <code>std::priority_queue</code> is faster at all.</p>
  
  <p>I actually would expect to be the <code>std::multimap</code> faster because of the many reinsertions.
  Maybe the problem is that there are too many reorganizations of the multimap?</p>