Re: Broken interaction between std::priority_queue and move-only
types
On Friday, 18 May 2012 17:29:30 UTC-4, Daniel Kr?gler wrote:
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.
Yes, sorry, actually in my original post I meant to provide the top()
with the above-mentioned signature (non-const), and point out what
you described.
What we really need is a new pop:
void pop( value_type& e )
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.
As far as I see, while
const_cast< ... >( top() )
certainly works, but it is essentially a
reference top()
hacked together by the end-user.
My proposal would be a new pop( value_type & e ), where the
'top' is copied / moved to 'e' as described here:
If there is a noexecpt move-assignment operator for value_type,
enable moving 'top'; otherwise make a copy of 'top' and use
the copy-assignment operator.
Note: This semantic is very similar to what std::vector uses
to relocate elements by move or copy, while maintaining
the strong exception-safety guarantees.
template< ... >
void std::priority_queue< ... >::pop( value_type & e )
{
e = std::move_if_noexcept_assignable( internal_top() );
// invariant might be broken at this point, but this is
// not observeable from outside (assuming single thread)
internal_pop(); // invariant is fixed
}
Examples:
1. Copy-assignment case
// type is copy-able and move-able, w/o noexcept move-assignment
struct node_cm_throw;
std::priority_queue< node_cm_throw, ... > queue;
node_cm_throw node;
// copy top to node, then pop
queue.pop( node );
2. Move-assignemnt case
// type is copy-able and move-able, with noexcept move-assignment
struct node_cm_nothrow;
std::priority_queue< node_cm_nothrow, ... > queue;
node_cm_nothrow node;
// move top to node, then then pop
queue.pop( node );
3. Error case
// type is move-only, w/o noexcept move-assignment
struct node_m_throw;
std::priority_queue< node_m_throw,... > queue;
node_m_throw node;
// error: missing copy-assignment operator
// or nothrow move-assignment operator
queue.pop( node );
4. Copy-assignemnt case
// (copy-able only)
struct node_c;
std::priority_queue< node_c, ... > queue;
node_c node;
// copy top() to node, then pop()
queue.pop( node );
The pop( value_type & e ) therefore
- provides strong exception-safety guarantees
- enables types with noexcept declared move-assignment operator
to move elements from the container
- makes sure that the heap property is upheld.
Pros over the const_cast< ... >( top() ):
- broken invariant is not observed from outside
- supports copy-able, move-able and certain move-only types
- makes the right choice if a type is both copy-able and
move-able at the same time (depending on move-assignment
operator noexcept declaration)
Cons:
- if the value_type's move-assignment operator is not declared
as noexcept, this 'pop' still does not work with it
- does not support move-construction as the target object has to
be readily available, thus potentially requires that the type
is Default Constructible to support reasonable use-cases
I think the first restriction is reasonable to provide strong
exception-safety guarantees.
Second restriction might sounds worse, but in practice most
move-enabled types are also Default Constructible...
How does that sound?
-- Zoltan
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]