How to get a non-const top element from priority_q

问题:

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?

回答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.

回答2:

I don't think value semantics play any least role here. All other containers have the same value semantics and almost all of them provide front() with mutable reference.

There is one exact reason why priority_queue disallows modification of the top() element: this is because particular element is at top because it has been accordingly qualified so, according to its present value. Elements in the priority queue are always sorted according to the comparison criteria configured for the queue (operator < by default). By altering the element you can potentially destroy this condition and cause that all operations that use the sorted precondition would cause undefined behavior.

In short, the reason why priority_queue does not allow to modify contained elements is exactly the same as in case of set and keys for map.

I understand that you may have some dedicated comparison method, you use a field that contains the value to comparison, and you're going to modify any content of the object, except this very field. This way you don't violate the requirement of sorted order. There are two things you can do:

1. Make your class's parts that should be modified as mutable. This way you can get the element by top() and modify the mutable contents, even though this is const.

2. Create your own priority queue class by deriving std::priority_queue. It has a field named c (in protected section though), which contains a reference to the underlying container - and an underlying container rather always has a front() method that accesses the same element as top() in priority_queue. For your own safety, though, you should make your key field const, so that it's set during construction and never altered - just to minimize the risk.

Ah, and this problem cannot be also solved by using pointers - pointed objects will be exactly the same constant. These "reference semantics" also won't help you in any way because if you want to have a dedicated comparison method, it will have to look into the objects' contents, and this way you'll have exactly the same problem. This would help you, if you relied on simply comparing pointer values, but I'd rather doubt this could be a solution for 99% of cases.