title: A variation of priority queue
body: <p>I need some kind of priority queue to store pairs <code>&lt;key, value&gt;</code>. Values are unique, but keys aren't. I will be performing the following operations (most common first):</p>
  
  <ol>
  <li>random insertion;</li>
  <li>retrieving (and removing) all elements with the least key.</li>
  <li>random removal (by value);</li>
  </ol>
  
  <p>I can't use <code>std::priority_queue</code> because it only supports removing the head.</p>
  
  <p>For now, I'm using an unsorted <code>std::list</code>. <strong>Insertion</strong> is performed by just pushing new elements to the back (O(1)). <strong>Operation 2</strong> sorts the list with <code>list::sort</code> (O(N*logN)), before performing the actual retrieval. <strong>Removal</strong>, however, is O(n), which is a bit expensive.</p>
  
  <p>Any idea of a better data structure?</p>