title: How to do an efficient priority update in STL priority_queue?
body: <p>I have a priority_queue of some object:</p>
  
  <pre><code>typedef priority_queue&lt;Object&gt; Queue;
  Queue queue;
  </code></pre>
  
  <p>From time to time, the priority of one of the objects may change - I need to be able to update the priority of that object in the queue in an efficient way. Currently I am using this method which works but seems inefficient:</p>
  
  <pre><code>Queue newQueue;
  while (!queue.empty())
  {
    Object obj=queue.top();
    queue.pop();
  
    if (priorityHasChanged(obj))
      newQueue.push_back(Object(new_priority));
    else
      newQueue.push_back(obj);
  }
  
  newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                   // class and exposed a swap method that swaps in the container
  </code></pre>
  
  <p>I implemented it this way because I was in kind of a hurry at the time and this was the quickest thing I could do that I could be sure it would work ok. There has to be a better way than this though. Really what I want is a way to either:</p>
  
  <ul>
  <li>extract out the instance with the changed priority and insert a new one with the new priority value</li>
  <li>update the instance with the changed priority and then update the queue so that it is correctly sorted</li>
  </ul>
  
  <p>What is the best way to do this?</p>