Re: Broken interaction between std::priority_queue and move-only
types
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::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()
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::priority_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/wg21/docs/lwg-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! ]