Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Broken interaction between std::priority_queue and move-only types
246 views
Skip to first unread message
Zoltan Juhasz
May 17, 2012, 9:05:08 PM5/17/12
to
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?
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! ]
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! ]
Daniel Krügler
May 18, 2012, 5:22:50 PM5/18/12
to
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.
> 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?
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.
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() :)
non-const reference having the additional advantage of being
consistent with the remaining container adaptor interfaces.
HTH & Greetings from Bremen,
Daniel Krügler
Daniel Krügler
May 18, 2012, 5:29:30 PM5/18/12
to
Am 18.05.2012 03:05, schrieb Zoltan Juhasz:
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() :)
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
Zoltan Juhasz
May 19, 2012, 4:45:51 PM5/19/12
to
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()
> 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.
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
> 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.
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
Joshua Maurice
May 20, 2012, 10:48:09 AM5/20/12
to
On May 17, 6:05 pm, Zoltan Juhasz <zoltan.juh...@gmail.com> wrote:
> 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.
>
[...]
> 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.
>
> What we really need is a new pop:
>
> void pop( value_type& e )
Why not
>
> void pop( value_type& e )
value_type&& pop2()
or something?
(Insert whatever magic syntax to make this actually work. Sorry, I'm
still new to move-stuff.)
(As for the name "pop2" - I'm sorry, but I suck at naming.)
I recall reading that combining the top() and pop() functionality into
one function is "bad" or "less good" for some reason, but in this case
it seems to be the obvious solution. It would be nice to reuse the
existing pop() functionality, but I don't know how bad that would be
for backwards compatibility.
Zoltan Juhasz
May 21, 2012, 12:19:11 AM5/21/12
to
On Sunday, 20 May 2012 10:48:09 UTC-4, Joshua Maurice wrote:
> Why not
> value_type&& pop2()
> or something?
> (Insert whatever magic syntax to make this actually work. Sorry, I'm
> still new to move-stuff.)
> (As for the name "pop2" - I'm sorry, but I suck at naming.)
The problem with returning rvalue reference - or any reference as
> Why not
> value_type&& pop2()
> or something?
> (Insert whatever magic syntax to make this actually work. Sorry, I'm
> still new to move-stuff.)
> (As for the name "pop2" - I'm sorry, but I suck at naming.)
a matter of fact - that you have to be able to store the object, on
which you return a reference to, someplace that outlives
the function-call.
For example this code introduces a dangling reference:
value_type&& bad_pop()
{
auto e = { move_if_noexcept( internal_top() ) };
internal_pop();
return e; // oops, reference returned to temporary
}
You can apply an implementation specific trick, to establish
such a 'persistent' storage, for example a naive, binary-heap
implementation on a vector could swap the 0th element (top)
with the nth (last) element, then fix the heap property
between [0, n-1], while returning an rvalue reference to the
nth element, which is not part of the heap.
While it is certainly possible to come up with such a trick,
it might not be trivial in other cases.
> I recall reading that combining the top() and pop() functionality into
> one function is "bad" or "less good" for some reason, but in this case
> it seems to be the obvious solution. It would be nice to reuse the
> existing pop() functionality, but I don't know how bad that would be
> for backwards compatibility.
example if you are dealing with thread-safe queue or stack,
combining pop and top is a well-known way to eliminate inherent
race-conditions on the container's interface, I guess the question
is how do you combine them, for example:
value_type faulty_pop()
{
auto e = move_if_noexcept( internal_top() );
internal_pop();
return e;
}
does not provide strong exception guarantees, b/c when you return 'e',
an exception might occur, and at that point you've changed the
container in an irreversible way.
The pop( value_type& e ), on the other hand, does not suffer from
these kind of problems; until now, there were no reason to provide
such an overload, since top() + pop() provides the same functionality.
I am not against the value_type&& pop2() on the other hand, the
question is how feasible the implementation in a real-life scenario.
-- Zoltan
Joshua Maurice
May 21, 2012, 3:53:00 AM5/21/12
to
On May 20, 9:19 pm, Zoltan Juhasz <zoltan.juh...@gmail.com> wrote:
> On Sunday, 20 May 2012 10:48:09 UTC-4, Joshua Maurice wrote:
> > Why not
> > value_type&& pop2()
> > or something?
> > (Insert whatever magic syntax to make this actually work. Sorry, I'm
> > still new to move-stuff.)
> > (As for the name "pop2" - I'm sorry, but I suck at naming.)
>
> The problem with returning rvalue reference - or any reference as
> a matter of fact - that you have to be able to store the object, on
> which you return a reference to, someplace that outlives
> the function-call.
>
> For example this code introduces a dangling reference:
>
> value_type&& bad_pop()
> {
> auto e = { move_if_noexcept( internal_top() ) };
> internal_pop();
> return e; // oops, reference returned to temporary
>
> }
I see. I need more work with move types. I haven't had a chance to
> On Sunday, 20 May 2012 10:48:09 UTC-4, Joshua Maurice wrote:
> > Why not
> > value_type&& pop2()
> > or something?
> > (Insert whatever magic syntax to make this actually work. Sorry, I'm
> > still new to move-stuff.)
> > (As for the name "pop2" - I'm sorry, but I suck at naming.)
>
> The problem with returning rvalue reference - or any reference as
> a matter of fact - that you have to be able to store the object, on
> which you return a reference to, someplace that outlives
> the function-call.
>
> For example this code introduces a dangling reference:
>
> value_type&& bad_pop()
> {
> auto e = { move_if_noexcept( internal_top() ) };
> internal_pop();
> return e; // oops, reference returned to temporary
>
> }
play around with them yet. I spoke too soon.
I do like your
pop(value_type& );
now.
Thanks for your explanation.
Seungbeom Kim
May 21, 2012, 9:18:49 AM5/21/12
to
On 2012-05-20 21:19, Zoltan Juhasz wrote:
>
> I am not sure if combining top and pop is essentially bad, for
> example if you are dealing with thread-safe queue or stack,
> combining pop and top is a well-known way to eliminate inherent
> race-conditions on the container's interface, I guess the question
> is how do you combine them, for example:
>
> value_type faulty_pop()
> {
> auto e = move_if_noexcept( internal_top() );
> internal_pop();
> return e;
> }
>
> does not provide strong exception guarantees, b/c when you return 'e',
> an exception might occur, and at that point you've changed the
> container in an irreversible way.
Can't we enable that function only for value_types with a non-throwing
>
> I am not sure if combining top and pop is essentially bad, for
> example if you are dealing with thread-safe queue or stack,
> combining pop and top is a well-known way to eliminate inherent
> race-conditions on the container's interface, I guess the question
> is how do you combine them, for example:
>
> value_type faulty_pop()
> {
> auto e = move_if_noexcept( internal_top() );
> internal_pop();
> return e;
> }
>
> does not provide strong exception guarantees, b/c when you return 'e',
> an exception might occur, and at that point you've changed the
> container in an irreversible way.
move constructor?
> The pop( value_type& e ), on the other hand, does not suffer from
> these kind of problems;
ask the top element to be move-assigned to it. It may not be always
possible or desirable to default construct such an object, just to
be overwritten later.
This signature reminds me of the "hack" of using reference parameters
for what should semantically be return values just to avoid expensive
copying:
void get_some_large_value(vector<string>& result);
vector<string> result;
get_some_large_value(result);
I thought that it was ugly, and that finally with C++11 we wouldn't need
it any more. And this thread seems to suggest that we still need it. :(
> until now, there were no reason to provide
> such an overload, since top() + pop() provides the same functionality.
exception safety. If we don't copy but just move without exceptions, or
even if we do copy but it is guaranteed not to throw, then the two don't
really to be separated. In fact, as you mentioned, there are situations
where we want them to be combined.
--
Seungbeom Kim
Gene Bushuyev
May 21, 2012, 3:28:09 PM5/21/12
to
On May 21, 6:18 am, Seungbeom Kim <musip...@bawi.org> wrote:
> On 2012-05-20 21:19, Zoltan Juhasz wrote:
>
> > I am not sure if combining top and pop is essentially bad, for
> > example if you are dealing with thread-safe queue or stack,
> > combining pop and top is a well-known way to eliminate inherent
> > race-conditions on the container's interface, I guess the question
> > is how do you combine them, for example:
>
> > value_type faulty_pop()
> > {
> > auto e = move_if_noexcept( internal_top() );
> > internal_pop();
> > return e;
> > }
>
> > does not provide strong exception guarantees, b/c when you return
> > 'e', an exception might occur, and at that point you've changed
> > the container in an irreversible way.
>
> Can't we enable that function only for value_types with a
> non-throwing move constructor?
>
> > The pop( value_type& e ), on the other hand, does not suffer from
> > these kind of problems;
>
> But then you need to default construct an object of value_type and
> ask the top element to be move-assigned to it. It may not be always
> possible or desirable to default construct such an object, just to
> be overwritten later.
To avoid default constructing an object one would need the function
> On 2012-05-20 21:19, Zoltan Juhasz wrote:
>
> > I am not sure if combining top and pop is essentially bad, for
> > example if you are dealing with thread-safe queue or stack,
> > combining pop and top is a well-known way to eliminate inherent
> > race-conditions on the container's interface, I guess the question
> > is how do you combine them, for example:
>
> > value_type faulty_pop()
> > {
> > auto e = move_if_noexcept( internal_top() );
> > internal_pop();
> > return e;
> > }
>
> > does not provide strong exception guarantees, b/c when you return
> > 'e', an exception might occur, and at that point you've changed
> > the container in an irreversible way.
>
> Can't we enable that function only for value_types with a
> non-throwing move constructor?
>
> > The pop( value_type& e ), on the other hand, does not suffer from
> > these kind of problems;
>
> But then you need to default construct an object of value_type and
> ask the top element to be move-assigned to it. It may not be always
> possible or desirable to default construct such an object, just to
> be overwritten later.
returning by value, how about simply modifying pop to return a value:
template<typename T, typename Container, typename Compare>
T priority_queue<T, Container, Compare>::pop()
{
T tmp(move(container.front()));
container.erase(container.begin());
make_heap(container.begin(), container.end(), compare);
return tmp;
}
It will not break existing code that relies on copy and assumes pop()
doesn't return anything.
--
Wil Evers
May 21, 2012, 5:24:18 PM5/21/12
to
Seungbeom Kim wrote:
> On 2012-05-20 21:19, Zoltan Juhasz wrote:
[snip]
> On 2012-05-20 21:19, Zoltan Juhasz wrote:
>> for example:
>>
>> value_type faulty_pop()
>> {
>> auto e = move_if_noexcept( internal_top() );
>> internal_pop();
>> return e;
>> }
>>
>> does not provide strong exception guarantees, b/c when you return
>> 'e', an exception might occur, and at that point you've changed the
>> container in an irreversible way.
>
> Can't we enable that function only for value_types with a
> non-throwing move constructor?
>
>> The pop( value_type& e ), on the other hand, does not suffer from
>> these kind of problems;
>
> But then you need to default construct an object of value_type and
> ask the top element to be move-assigned to it. It may not be always
> possible or desirable to default construct such an object, just to
> be overwritten later.
I agree. Paradoxically, a movable type without a default constructor
>>
>> value_type faulty_pop()
>> {
>> auto e = move_if_noexcept( internal_top() );
>> internal_pop();
>> return e;
>> }
>>
>> does not provide strong exception guarantees, b/c when you return
>> 'e', an exception might occur, and at that point you've changed the
>> container in an irreversible way.
>
> Can't we enable that function only for value_types with a
> non-throwing move constructor?
>
>> The pop( value_type& e ), on the other hand, does not suffer from
>> these kind of problems;
>
> But then you need to default construct an object of value_type and
> ask the top element to be move-assigned to it. It may not be always
> possible or desirable to default construct such an object, just to
> be overwritten later.
seems like a strange beast, because it presumably implements a "valid,
but resourceless" state for its objects to be left in after having
been moved from.
I would say that a type with a default constructor clearly advertises
that such a state exists and must be reckoned with.
- Wil
--
Joshua Maurice
May 22, 2012, 12:23:29 PM5/22/12
to
On May 21, 12:28 pm, Gene Bushuyev <publicfil...@gbresearch.com>
wrote:
struct Foo { void pop(); };
void bar(Foo & x) { return x.pop(); }
int main() { Foo x; bar(x); }
This is pretty obfuscated code IMHO, but legitimate code like it may
appear in template programming. Possibly not for this particular case,
but again I'm in pedantic anal mode.
If we change pop() to have a non-void return value, then we get a
compiler error. Error from Comeau:
http://www.comeaucomputing.com/tryitout/
"ComeauTest.c", line 2: error: return value type does not match
the function type
void bar(Foo & x) { return x.pop(); }
Of course, I think it might be ok to break obscure code like this.
wrote:
> To avoid default constructing an object one would need the function
> returning by value, how about simply modifying pop to return a value:
>
> template<typename T, typename Container, typename Compare>
> T priority_queue<T, Container, Compare>::pop()
> {
> T tmp(move(container.front()));
> container.erase(container.begin());
> make_heap(container.begin(), container.end(), compare);
> return tmp;
>
> }
>
> It will not break existing code that relies on copy and assumes pop()
> doesn't return anything.
To be pedantically anal, this isn't true. Consider:
> returning by value, how about simply modifying pop to return a value:
>
> template<typename T, typename Container, typename Compare>
> T priority_queue<T, Container, Compare>::pop()
> {
> T tmp(move(container.front()));
> container.erase(container.begin());
> make_heap(container.begin(), container.end(), compare);
> return tmp;
>
> }
>
> It will not break existing code that relies on copy and assumes pop()
> doesn't return anything.
struct Foo { void pop(); };
void bar(Foo & x) { return x.pop(); }
int main() { Foo x; bar(x); }
This is pretty obfuscated code IMHO, but legitimate code like it may
appear in template programming. Possibly not for this particular case,
but again I'm in pedantic anal mode.
If we change pop() to have a non-void return value, then we get a
compiler error. Error from Comeau:
http://www.comeaucomputing.com/tryitout/
"ComeauTest.c", line 2: error: return value type does not match
the function type
void bar(Foo & x) { return x.pop(); }
Of course, I think it might be ok to break obscure code like this.
Zoltan Juhasz
May 22, 2012, 2:34:01 PM5/22/12
to
On Monday, 21 May 2012 09:18:49 UTC-4, Seungbeom Kim wrote:
> Can't we enable that function only for value_types with a non-throwing
> move constructor?
I guess an
> Can't we enable that function only for value_types with a non-throwing
> move constructor?
value_type emplace_pop()
could be a reasonable alternative. Ofc. then it cannot be used with
types that provides no nothrow move-ctor (or nothrow cpy-ctor), plus
this one potentially requires two move (or copy) instead of one
(not taking RVO into account).
I guess the advantage of pop( value_type& e ) that it works happily
with types that are not move-able at all, and only one copy or move
is involved.
> > The pop( value_type& e ), on the other hand, does not suffer from
> > these kind of problems;
>
> But then you need to default construct an object of value_type and
> ask the top element to be move-assigned to it. It may not be always
> possible or desirable to default construct such an object, just to
> be overwritten later.
probably not unreasonable, IIRC most - if not all - current
move-only types in standard template library provides default
constructor.
I also agree with Wil, when you move the resources out from an
object, it is very similar to a default constructed state that
has not acquired the resources yet (e.g. it has to be destructible
and assignable).
Having said that, I am not against an emplace_pop(), but cannot
clearly see the advantage either.
--
Seungbeom Kim
May 22, 2012, 2:38:24 PM5/22/12
to
On 2012-05-21 14:24, Wil Evers wrote:
> Seungbeom Kim wrote:
>> On 2012-05-20 21:19, Zoltan Juhasz wrote:
>>> The pop( value_type& e ), on the other hand, does not suffer from
>>> these kind of problems;
>>
>> But then you need to default construct an object of value_type and
>> ask the top element to be move-assigned to it. It may not be always
>> possible or desirable to default construct such an object, just to
>> be overwritten later.
>
> I agree. Paradoxically, a movable type without a default
> constructor seems like a strange beast, because it presumably
> implements a "valid, but resourceless" state for its objects to be
> left in after having been moved from.
>
> I would say that a type with a default constructor clearly
> advertises that such a state exists and must be reckoned with.
You have a good point. Then in most sensible cases, the default
> Seungbeom Kim wrote:
>> On 2012-05-20 21:19, Zoltan Juhasz wrote:
>>> The pop( value_type& e ), on the other hand, does not suffer from
>>> these kind of problems;
>>
>> But then you need to default construct an object of value_type and
>> ask the top element to be move-assigned to it. It may not be always
>> possible or desirable to default construct such an object, just to
>> be overwritten later.
>
> I agree. Paradoxically, a movable type without a default
> constructor seems like a strange beast, because it presumably
> implements a "valid, but resourceless" state for its objects to be
> left in after having been moved from.
>
> I would say that a type with a default constructor clearly
> advertises that such a state exists and must be reckoned with.
constructor should be available and its cost should reduce to
initializing a few small scalar objects such as pointers or booleans.
The remaining problem is that of aesthetics: "value_type e = q.pop();"
is much more elegant than "value_type e; q.pop(e);" and I'd love to be
able to write so.
--
Seungbeom Kim
Zoltan Juhasz
May 22, 2012, 2:43:01 PM5/22/12
to
On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
> To avoid default constructing an object one would need the function
> returning by value, how about simply modifying pop to return a value:
>
> template<typename T, typename Container, typename Compare>
> T priority_queue<T, Container, Compare>::pop()
> {
> T tmp(move(container.front()));
> container.erase(container.begin());
> make_heap(container.begin(), container.end(), compare);
> return tmp;
> }
>
> It will not break existing code that relies on copy and assumes pop()
> doesn't return anything.
Unfortunately this implementation does not provide strong exception
> To avoid default constructing an object one would need the function
> returning by value, how about simply modifying pop to return a value:
>
> template<typename T, typename Container, typename Compare>
> T priority_queue<T, Container, Compare>::pop()
> {
> T tmp(move(container.front()));
> container.erase(container.begin());
> make_heap(container.begin(), container.end(), compare);
> return tmp;
> }
>
> It will not break existing code that relies on copy and assumes pop()
> doesn't return anything.
safety guarantees, e.g. if an exception is thrown when you return tmp,
the container has been already modified, in an irreversible way, and
the returned element is lost.
-- Zoltan
Gene Bushuyev
May 22, 2012, 9:11:03 PM5/22/12
to
On May 22, 11:43 am, Zoltan Juhasz <zoltan.juh...@gmail.com> wrote:
> On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
> > To avoid default constructing an object one would need the function
> > returning by value, how about simply modifying pop to return a value:
>
> > template<typename T, typename Container, typename Compare>
> > T priority_queue<T, Container, Compare>::pop()
> > {
> > T tmp(move(container.front()));
> > container.erase(container.begin());
> > make_heap(container.begin(), container.end(), compare);
> > return tmp;
> > }
>
> > It will not break existing code that relies on copy and assumes pop()
> > doesn't return anything.
>
> Unfortunately this implementation does not provide strong exception
> safety guarantees, e.g. if an exception is thrown when you return tmp,
> the container has been already modified, in an irreversible way, and
> the returned element is lost.
>
But does priority_queue have a strong exception guarantee of pop()?
> On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
> > To avoid default constructing an object one would need the function
> > returning by value, how about simply modifying pop to return a value:
>
> > template<typename T, typename Container, typename Compare>
> > T priority_queue<T, Container, Compare>::pop()
> > {
> > T tmp(move(container.front()));
> > container.erase(container.begin());
> > make_heap(container.begin(), container.end(), compare);
> > return tmp;
> > }
>
> > It will not break existing code that relies on copy and assumes pop()
> > doesn't return anything.
>
> Unfortunately this implementation does not provide strong exception
> safety guarantees, e.g. if an exception is thrown when you return tmp,
> the container has been already modified, in an irreversible way, and
> the returned element is lost.
>
Implementation of heap requires copies or moves of its elements on pop
anyway. To provide a strong guarantee pop() would need to keep the
original vector and work on copy, which is 1) expensive, and 2) the
same can be used in the new implementation.
SG
May 23, 2012, 1:49:19 PM5/23/12
to
On May 23, 3:11 am, Gene Bushuyev wrote:
> Implementation of heap requires copies or moves of its elements on pop
> anyway. To provide a strong guarantee pop() would need to keep the
> original vector and work on copy, which is 1) expensive,
Exactly. But this won't be possible for move-only types, of course.
So, for move-only types with a potentially throwing move assignment,
pop simply can't give the strong exception safety guarantee regardless
of whether it returns something or not. So, a move assignment for the
popped element in a function like
void pop(value_type & into);
would also not be able to make the strong guarantee. Therefore, I'd
prefer an additional pop-like function with a different name that
simply returns by value ("pop_return", "pop_move", etc). It may be an
additional move (in case of NRVO not being applicable) but it's much
much nicer to be able to write
value_type foo = queue.pop_move();
without any default constructions going on.
Well, the default construction could be also removed with a pop
function that receives a reference to a type like
boost::optional<value_type>. To generalize this, the function could
accept a "sink functor":
template<class Sink>
void pop(Sink sink)
{
...
sink(std::move(...)); // move_if_noexcept is pointless here,
right?
...
}
and its use:
boost::optional<value_type> v;
queue.pop([&](value_type&& x){v=std::move(x);});
But this is not a serious suggestion. Just an idea. As I said, I'd
prefer a simple
value_type pop_move();
function which conditionally offers the nothrow guarantee (in case
value_type is nothrow-movable).
Cheers!
SG
> On May 22, 11:43 am, Zoltan Juhasz wrote:
> > On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
> > > To avoid default constructing an object one would need the function
> > > returning by value, how about simply modifying pop to return a value:
>
> > > template<typename T, typename Container, typename Compare>
> > > T priority_queue<T, Container, Compare>::pop()
> > > {
> > > T tmp(move(container.front()));
> > > container.erase(container.begin());
> > > make_heap(container.begin(), container.end(), compare);
> > > return tmp;
> > > }
>
> > > It will not break existing code that relies on copy and assumes pop()
> > > doesn't return anything.
>
> > Unfortunately this implementation does not provide strong exception
> > safety guarantees, e.g. if an exception is thrown when you return tmp,
> > the container has been already modified, in an irreversible way, and
> > the returned element is lost.
>
> But does priority_queue have a strong exception guarantee of pop()?
No, not generally. Good point.
> > On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
> > > To avoid default constructing an object one would need the function
> > > returning by value, how about simply modifying pop to return a value:
>
> > > template<typename T, typename Container, typename Compare>
> > > T priority_queue<T, Container, Compare>::pop()
> > > {
> > > T tmp(move(container.front()));
> > > container.erase(container.begin());
> > > make_heap(container.begin(), container.end(), compare);
> > > return tmp;
> > > }
>
> > > It will not break existing code that relies on copy and assumes pop()
> > > doesn't return anything.
>
> > Unfortunately this implementation does not provide strong exception
> > safety guarantees, e.g. if an exception is thrown when you return tmp,
> > the container has been already modified, in an irreversible way, and
> > the returned element is lost.
>
> But does priority_queue have a strong exception guarantee of pop()?
> Implementation of heap requires copies or moves of its elements on pop
> anyway. To provide a strong guarantee pop() would need to keep the
> original vector and work on copy, which is 1) expensive,
So, for move-only types with a potentially throwing move assignment,
pop simply can't give the strong exception safety guarantee regardless
of whether it returns something or not. So, a move assignment for the
popped element in a function like
void pop(value_type & into);
would also not be able to make the strong guarantee. Therefore, I'd
prefer an additional pop-like function with a different name that
simply returns by value ("pop_return", "pop_move", etc). It may be an
additional move (in case of NRVO not being applicable) but it's much
much nicer to be able to write
value_type foo = queue.pop_move();
without any default constructions going on.
Well, the default construction could be also removed with a pop
function that receives a reference to a type like
boost::optional<value_type>. To generalize this, the function could
accept a "sink functor":
template<class Sink>
void pop(Sink sink)
{
...
sink(std::move(...)); // move_if_noexcept is pointless here,
right?
...
}
and its use:
boost::optional<value_type> v;
queue.pop([&](value_type&& x){v=std::move(x);});
But this is not a serious suggestion. Just an idea. As I said, I'd
prefer a simple
value_type pop_move();
function which conditionally offers the nothrow guarantee (in case
value_type is nothrow-movable).
Cheers!
SG
Wil Evers
May 24, 2012, 4:40:43 AM5/24/12
to
Zoltan Juhasz wrote:
> On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
>> To avoid default constructing an object one would need the function
>> returning by value, how about simply modifying pop to return a value:
>>
>> template<typename T, typename Container, typename Compare>
>> T priority_queue<T, Container, Compare>::pop()
>> {
>> T tmp(move(container.front()));
>> container.erase(container.begin());
>> make_heap(container.begin(), container.end(), compare);
>> return tmp;
>> }
>>
>> It will not break existing code that relies on copy and assumes pop()
>> doesn't return anything.
>
> Unfortunately this implementation does not provide strong exception
> safety guarantees, e.g. if an exception is thrown when you return tmp,
> the container has been already modified, in an irreversible way, and
> the returned element is lost.
Which is why, as Seungbeom Kim suggested, this version of pop() should
> On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
>> To avoid default constructing an object one would need the function
>> returning by value, how about simply modifying pop to return a value:
>>
>> template<typename T, typename Container, typename Compare>
>> T priority_queue<T, Container, Compare>::pop()
>> {
>> T tmp(move(container.front()));
>> container.erase(container.begin());
>> make_heap(container.begin(), container.end(), compare);
>> return tmp;
>> }
>>
>> It will not break existing code that relies on copy and assumes pop()
>> doesn't return anything.
>
> Unfortunately this implementation does not provide strong exception
> safety guarantees, e.g. if an exception is thrown when you return tmp,
> the container has been already modified, in an irreversible way, and
> the returned element is lost.
only be enabled if T has a non-throwing move constructor (or, if
it doesn't have a move constructor, a non-throwing copy constructor).
- Wil
Frank Birbacher
May 25, 2012, 6:32:34 PM5/25/12
to
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hi!
Am 22.05.12 20:38, schrieb Seungbeom Kim:
the opposite of "emplace."
I'd love to use "const" as well:
auto const e = q.displace_pop();
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: keyserver x-hkp://pool.sks-keyservers.net
iEYEARECAAYFAk++t4QACgkQhAOUmAZhnmpTBgCcDe3B8IH/e/jchyQRlm8ndNXc
LOAAn3EwLCjXfYI4G609P0hQ/p+92Hwi
=mRzt
-----END PGP SIGNATURE-----
--
Hash: SHA1
Hi!
Am 22.05.12 20:38, schrieb Seungbeom Kim:
> The remaining problem is that of aesthetics: "value_type e =
> q.pop();" is much more elegant than "value_type e; q.pop(e);" and
> I'd love to be able to write so.
For the naming I suggest "displace_pop()" where I think "displace" is
> q.pop();" is much more elegant than "value_type e; q.pop(e);" and
> I'd love to be able to write so.
the opposite of "emplace."
I'd love to use "const" as well:
auto const e = q.displace_pop();
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: keyserver x-hkp://pool.sks-keyservers.net
iEYEARECAAYFAk++t4QACgkQhAOUmAZhnmpTBgCcDe3B8IH/e/jchyQRlm8ndNXc
LOAAn3EwLCjXfYI4G609P0hQ/p+92Hwi
=mRzt
-----END PGP SIGNATURE-----
--
Dave Abrahams
May 28, 2012, 12:59:57 AM5/28/12
to
on Tue May 22 2012, Zoltan Juhasz <zoltan.juhasz-AT-gmail.com> wrote:
> On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
>> To avoid default constructing an object one would need the function
>> returning by value, how about simply modifying pop to return a value:
>>
>> template<typename T, typename Container, typename Compare>
>> T priority_queue<T, Container, Compare>::pop()
>> {
>> T tmp(move(container.front()));
>> container.erase(container.begin());
>> make_heap(container.begin(), container.end(), compare);
>> return tmp;
>> }
>>
>> It will not break existing code that relies on copy and assumes pop()
>> doesn't return anything.
>
> Unfortunately this implementation does not provide strong exception
> safety guarantees, e.g. if an exception is thrown when you return tmp,
> the container has been already modified, in an irreversible way, and
> the returned element is lost.
That's not so terrible. The basic guarantee is perfectly adequate for
> On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
>> To avoid default constructing an object one would need the function
>> returning by value, how about simply modifying pop to return a value:
>>
>> template<typename T, typename Container, typename Compare>
>> T priority_queue<T, Container, Compare>::pop()
>> {
>> T tmp(move(container.front()));
>> container.erase(container.begin());
>> make_heap(container.begin(), container.end(), compare);
>> return tmp;
>> }
>>
>> It will not break existing code that relies on copy and assumes pop()
>> doesn't return anything.
>
> Unfortunately this implementation does not provide strong exception
> safety guarantees, e.g. if an exception is thrown when you return tmp,
> the container has been already modified, in an irreversible way, and
> the returned element is lost.
many situations.
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Wil Evers
May 28, 2012, 1:12:08 PM5/28/12
to
Dave Abrahams wrote:
> on Tue May 22 2012, Zoltan Juhasz <zoltan.juhasz-AT-gmail.com> wrote:
>
>> On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
>>
>>> To avoid default constructing an object one would need the
>>> function returning by value, how about simply modifying pop to
>>> return a value:
>>>
>>> template<typename T, typename Container, typename Compare>
>>> T priority_queue<T, Container, Compare>::pop()
>>> {
>>> T tmp(move(container.front()));
>>> container.erase(container.begin());
>>> make_heap(container.begin(), container.end(), compare);
>>> return tmp;
>>> }
>>>
>>> It will not break existing code that relies on copy and assumes
>>> pop() doesn't return anything.
>>
>> Unfortunately this implementation does not provide strong exception
>> safety guarantees, e.g. if an exception is thrown when you return
>> tmp, the container has been already modified, in an irreversible
>> way, and the returned element is lost.
>
> That's not so terrible. The basic guarantee is perfectly adequate
> for many situations.
For priority_queue, I agree. As Gene explained elsewhere in this
> on Tue May 22 2012, Zoltan Juhasz <zoltan.juhasz-AT-gmail.com> wrote:
>
>> On Monday, 21 May 2012 15:28:09 UTC-4, Gene Bushuyev wrote:
>>
>>> To avoid default constructing an object one would need the
>>> function returning by value, how about simply modifying pop to
>>> return a value:
>>>
>>> template<typename T, typename Container, typename Compare>
>>> T priority_queue<T, Container, Compare>::pop()
>>> {
>>> T tmp(move(container.front()));
>>> container.erase(container.begin());
>>> make_heap(container.begin(), container.end(), compare);
>>> return tmp;
>>> }
>>>
>>> It will not break existing code that relies on copy and assumes
>>> pop() doesn't return anything.
>>
>> Unfortunately this implementation does not provide strong exception
>> safety guarantees, e.g. if an exception is thrown when you return
>> tmp, the container has been already modified, in an irreversible
>> way, and the returned element is lost.
>
> That's not so terrible. The basic guarantee is perfectly adequate
> for many situations.
thread, popping an element from a priority_queue involves moving a few
elements around in the underlying container, so in the face of a T
with a throwing move/copy constructor, even 'void pop()' cannot
provide the strong guarantee.
For most of the other standard containers, the situation is different:
they do provide the strong guarantee for pop{back,front}(). This is
possible because they do not attempt to return a T. I still remember
how long it took for the C++ community to realise and accept that, for
a T with a throwing copy constructor, you cannot have a 'T pop()' that
offers the strong guarantee. Some experts even insisted that this was
evidence of a fundamental flaw in C++'s exception concept.
With the introduction of move semantics, it seems we can finally have
our cake and eat it too: a 'T pop_and_return()' or somesuch would be
able to both return the former top element and provide the strong
exception guarantee.
But unlike 'void pop()', that strong guarantee can only be provided
if T has a non-throwing move constructor (or copy constructor).
Keeping that in mind, it seems to me that a 'T pop_and_return()'
should be disabled if it cannot provide the strong guarantee. The
alternative is just way too subtle. It will cause lots of confusion,
which is terrible indeed.
- Wil
--
0 new messages