Zoltan Juhasz
2012-05-18 01:05:08 UTC
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 > >,
... >
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() :)
-- Zoltan
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() :)
-- Zoltan
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]