C++ Logo


Advanced search

priority_queue doesn't work with move-only types

From: Phil Endecott <std_proposals_list_at_[hidden]>
Date: Sun, 21 Feb 2021 12:38:58 +0000
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.


#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

  std::priority_queue<moveonly> pq;
  pq.push( std::make_unique<int>(1) );
  auto y = std::move(pq.top()); // Doesn't compile

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?

In the case where I discovered this, my priority_queue stored a
pair<int,moveonly> and used a compare function that looked only at
the int. In this case, moving from (or otherwise modifying) the
pair's second element would not threaten the heap constraint. This
suggests std::map's reference type where the first is const but the
second is not. I'm not sure how priority_queue could be modified
so it could be used like this, though.

Any thoughts anyone?

Regards, Phil.

Received on 2021-02-21 06:39:00