Am 18.05.2012 03:05, schrieb Zoltan Juhasz:
> Let's say you've got a move-only type (such as std::unique_ptr< T>
> or std:ackaged_task) with an associated Compare functor that
> defines some kind of ordering on objects of the move-only type:
>
> struct Node;
> std:riority_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:riority_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()

I agree that this looks like a problematic restriction.

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

I agree as well.

> 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:riority_queue. Can you please comment on that?

I think you are right, that priority_queue should provide a better
support for move-only element types. You may want to submit a library
issue for this by sending one to the email address in the reply-to
section of this document:

http://www.open-std.org/jtc1/sc22/wg...wg-active.html

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

So what about adding

reference top() { return c.front(); }

instead? This would also be in sync with the std::queue and std::stack
templates and the remaining container templates.

> 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()

I see no real advantage over a non-const version of top returning a
non-const reference having the additional advantage of being
consistent with the remaining container adaptor interfaces.

HTH & Greetings from Bremen,

Daniel Krügler



--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]