C++ Logo


Advanced search

Re: priority_queue doesn't work with move-only types

From: Bo Persson <bo_at_[hidden]>
Date: Sun, 21 Feb 2021 16:04:33 +0100
On 2021-02-21 at 13:38, Phil Endecott via Std-Proposals wrote:
> Dear Experts,
> std::priority_queue doesn't work with move-only types, because
> it only has a const top() method.
> This is in contrast to std::queue and std::stack, which have both
> const and non-const front() or top() methods.
> Example:
> #include <queue>
> #include <memory>
> void test()
> {
> using moveonly = std::unique_ptr<int>;
> std::queue<moveonly> q;
> q.push( std::make_unique<int>(1) );
> auto x = std::move(q.front()); // OK
> q.pop();
> std::priority_queue<moveonly> pq;
> pq.push( std::make_unique<int>(1) );
> auto y = std::move(pq.top()); // Doesn't compile
> pq.pop();
> }
> The rationale for not having a non-const top() method is that
> allowing the top element to be modified allows the priority
> queue's heap constraint to be broken - which is reasonable.
> Of course in this particular case it is safe as the moved-from
> top element is immediately popped.
> One possible solution would be to provide a combined top-and-pop
> method. I believe that traditionally such a value-returning pop method
> had been avoided because its implementation would require more copying
> of the removed item than separate top() and void pop() methods, but
> it seems to me that this is moot now that we have move semantics.
> Perhaps we should now provide value-returning top-and-pop / front-and-
> pop methods for all containers and adaptors that have pop?

The reason for not having top-and-pop methods is that copying out the
element might throw. And if it is already popped at that point, it is lost.

     Bo Persson

Received on 2021-02-21 09:04:42