C++ Logo

STD-PROPOSALS

Advanced search

Subject: [std-proposals] priority_queue doesn't work with move-only types
From: Phil Endecott (std_proposals_list_at_[hidden])
Date: 2021-02-21 06:38:58


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?

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.


STD-PROPOSALS list run by std-proposals-owner@lists.isocpp.org

Standard Proposals Archives on Google Groups