How to tell a std::priority_queue to refresh its ordering?

Question

I have a priority queue of pointers to a struct city. I modify the objects pointed by these pointers outside the priority queue, and want to tell the priority queue to "reorder" itself according to the new values.

What should I do?

Example:

#include <iostream> #include <queue>  using namespace std;  struct city {     int data;     city *previous; };  struct Compare {     bool operator() ( city *lhs, city *rhs )     {         return ( ( lhs -> data ) >= ( rhs -> data ) );     } };  typedef priority_queue< city *, vector< city * >, Compare > pqueue;  int main() {     pqueue cities;      city *city1 = new city;     city1 -> data = 5;     city1 -> previous = NULL;     cities.push( city1 );      city *city2 = new city;     city2 -> data = 3;     city2 -> previous = NULL;     cities.push( city2 );      city1 -> data = 2;     // Now how do I tell my priority_queue to reorder itself so that city1 is at the top now?      cout << ( cities.top() -> data ) << "\n";     // 3 is printed :(      return 0; } 

Answer 1

This is a bit hackish, but nothing illegal about it, and it gets the job done.

std::make_heap(const_cast<city**>(&cities.top()),                const_cast<city**>(&cities.top()) + cities.size(),                Compare()); 

Update:

Do not use this hack if:

• The underlying container is not vector.
• The Compare functor has behavior that would cause your external copy to order differently than the copy of Compare stored inside the priority_queue.
• You don't fully understand what these warnings mean.

You can always write your own container adaptor which wraps the heap algorithms. priority_queue is nothing but a simple wrapper around make/push/pop_heap.