Re: Broken interaction between std::priority_queue and move-only types

Let's say you've got a move-only type (such as std::unique_ptr< T>
or std::packaged_task) with an associated Compare functor that
defines some kind of ordering on objects of the move-only type:

     struct Node;
     std::priority_queue<
         std::unique_ptr< Node>,
         std::vector< std::unique_ptr< Node> >,
         ...>
     > maxHeap;

You insert elements to the container by using emplace:

     std::unique_ptr< Node> node{ new Node() };
     // other operations on node ...
     maxHeap.emplace( std::move( node ) );
     // add further elements ...

At some point you want to consume the elements; you can only move
them, as the type is not copy-able. Unfortunately you are pretty
much stuck, as std::priority_queue< T> does not provide an interface
to move elements out from the container, as it only defines:

     const value_type& top() const
     void pop()

which is insufficient to be able to move elements from the
container.

You can work around he problem by applying a const_cast on top():

     std::unique_ptr< Node> node2 =
         std::move(
             const_cast< std::unique_ptr< Node>& >( maxHeap.top() )
             );

     // oops, invariant might be broken, heap property is not upheld...

     maxHeap.pop(); // ok, invariant is fixed

but that is pretty far from ideal.

So as a first step, I would like to confirm that this is indeed an
example of a broken interaction of move-only types and
std::priority_queue. Can you please comment on that?

As far as the solution is concerned, I guess providing

     value_type& top() const

would open the door wide open to mess with the invariant of the
container, so that is not a good idea.

What we really need is a new pop:

     void pop( value_type& e )

that is capable of moving the top element from the queue to 'e',
under certain circumstances. I can see some problems with strong
exception guarantees along this path, but I am fairly sure that
would be still a better option than forcing the user to
const_cast top() :)