STL Priority Queue: When/How Does Resorting Occur?

Question

If I have a STL priority_queue of structs, where priority is based on some attribute of the struct, and I change the attribute of one of the structs, such that the new order would be different, would the priority queue know to resort itself? Or would I have to remove it from the queue and push it in again? I read somewhere that the sorting is done when push() and pop() are called, but I'd like to make sure.

Answer 1

The priority_queue push() and pop() member functions are defined in terms of the behavior of the push_heap() and pop_heap() library functions with the full contents of the underlying container passed in as the range.

Those function require that the range (except for the last item in the container on a push_heap(), since that's the item that is being added) "shall be a valid heap". If you modify the contained elements such that the container is no longer a valid heap, then you'll get undefined behavior.

So if you need to modify an element in that manner, you'll need to do it by removing it, modifying it, then adding it back. Alternatively, you could, mess with the contents then call make_heap() to rebuild the heap.

See C++11 23.6.4.3 "priority_queue members", 25.4.6.1 "push_heap", and 25.4.6.2 "pop_heap".