How to get a non-const top element from priority_queue with user-defined objects?

Question

std::priority_queue::top returns a constant value. However, I would like to remove the top element from the priority queue and be able to modify it somewhere else.

priority_queue<SomeClass, vector<SomeClass>, SomeClassCompare > pQueue;
...
SomeClass *toBeModified = &(pQueue.top());
pQueue.pop();
toBeModified->setMember(3); // I would like to do this

Is there a way I can grab the top element from a priority queue (and remove from the queue) and modify it as I wish?

Answer 1

Standard containers and container adapters have value semantics. When you push an element into the queue, a copy is created. When you remove an object from the queue, that object is destroyed.

Even if top() would return you a reference to non-const, that reference would become dangling as soon as you remove the element from the queue, and dereferencing it would result in undefined behavior.

This said, std::priority_queue returns you a reference to const in order to prevent you from messing (intentionally or unintentionally) with its internal ordering - that's pretty much the same reason why the key of associative containers such as std::map and std::set is const.

What you can do, instead, is to construct a copy of the value returned by top(), modify that copy, remove the original, and push the copy into the queue:

SomeClass obj = pQueue.top();
pQueue.pop();
obj.setMember(42);
pQueue.push(std::move(obj)); // You can move obj into the queue if you no more need it

If you need reference semantics, on the other hand, then you will have to push pointers into the queue (possibly smart pointers, depending on your use case) and provide an appropriate custom ordering criterion that would order those pointers based on properties of the objects they point to.

In this case, be careful not to modify those properties at run-time in a way that would make their ordering different. That would count as "messing with the internal ordering of the container", and will result in undefined behavior.