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()
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?
I had just send a reply to your posting when I recognized that I
overlooked the special nature of priority_queue. I apologize for my
first impulsive reply and I withdraw my proposal to add an overload
reference top();
because that would allow for changing the class-invariants of this
queue. In fact, we have a similar situation as we have std::set or
std::unordered_set. While I could think of a way to make such
containers able to support mutable operations (especially: Moving
elements out of the container) due to the node-like nature of these
associative containers, this seems not as easily possible for an
adaptor like priority_queue to me.
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() :)
I would like to see first how the semantics of this function would be
specified. Remember that the container adaptors rely on functions
provided by the wrapped container, so implementations cannot perform
there own "magic" here. It seems to me that the current most
consistent way *is* to use a const_cast, because that is what you
would do with elements of associative containers as well. If you can
point out a semantics of your above suggested pop functions that
provides more advantages, I would be strongly interested to hear them.
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! ]