c++ - How to do an efficient priority update in STL priority_queue?

Question

I have a priority_queue of some object:

typedef priority_queue<Object> Queue;
Queue queue;

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:

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

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:

• extract out the instance with the changed priority and insert a new one with the new priority value
• update the instance with the changed priority and then update the queue so that it is correctly sorted

What is the best way to do this?

question from:https://stackoverflow.com/questions/649640/how-to-do-an-efficient-priority-update-in-stl-priority-queue

Answer 1

I think you are out of luck with standard priority queue because you can't get at the underlying deque/vector/list or whatever. You need to implement your own - it's not that hard.