New member functions for standard container adapters

[Diego R.]

Priority queues cannot be used with types non-copyable. Because top() returns a constant reference. For example I can't create something like priority_queue<std::unique_ptr<MyPolymorphicClass>>.

I propose that priority_queue have more support for move semantics by using of new member functions. Additionaly I would add these new members functions to stack and queue for simmetry.

Below I show an idea.

template <class T, class Container, class Comparer>

 class priority_queue

 {

  ...

   value_type move_top()

   {

      value_type v;

      pop(v);

      return v;  

   }

   void pop(value_type& v)

   {

     std::pop_heap(c.begin(), c.end(), comp); 

     v = std::move(c.back());

     c.pop_back();

   }

 

 };

template <class T, class Container>

 class stack

 {

  ...

   value_type move_top()

   {

      value_type v;

      pop(v);

      return v;  

   }

   void pop(value_type& v)

   { 

     v = std::move(c.back());

     c.pop_back();

   }

 

 };

template <class T, class Container>

 class queue

 {

  ...

   value_type move_front()

   {

      value_type v;

      pop(v);

      return v;  

   }

   void pop(value_type& v)

   { 

     v = std::move(c.front());

     c.pop_front();

   }

 

 };

[Nicol Bolas]

I can't say I care much for the "pop-into-value" functions, but you should write it up into a proposal.

[Vicente J. Botet Escriba]

Le 26/05/13 08:42, Diego R. a �crit :

> Priority queues cannot be used with types non-copyable. Because top()
> returns a constant reference. For example I can't create something
> like priority_queue<std::unique_ptr<MyPolymorphicClass>>.
>
> I propose that priority_queue have more support for move semantics by
> using of new member functions. Additionaly I would add these new
> members functions to stack and queue for simmetry.
>
> Below I show an idea.
>
> template <class T, class Container, class Comparer>
> class priority_queue
> {
> ...
> value_type move_top()
> {
> value_type v;
> pop(v);
> return v;
> }
>
> void pop(value_type& v)
> {
> std::pop_heap(c.begin(), c.end(), comp);
> v = std::move(c.back());
> c.pop_back();
> }
> };
>

Yes, there is an issue here. I guess top() returns a const_reference to
ensure the class invariants.
Maybe pull() could be used to name both operations.

> template <class T, class Container>
> class stack
> {
> ...
> value_type move_top()
> {
> value_type v;
> pop(v);
> return v;
> }
>
> void pop(value_type& v)
> {
> v = std::move(c.back());
> c.pop_back();
> }
> };
>
> template <class T, class Container>
> class queue
> {
> ...
> value_type move_front()
> {
> value_type v;
> pop(v);
> return v;
> }
>
> void pop(value_type& v)
> {
> v = std::move(c.front());
> c.pop_front();
> }
> };
>

I don't see the problem with stack and queue. stack top() returns a
reference and queue has no member top() and front() and back() returns a
reference.

Best,
Vicente

[Jonathan Wakely]

On Sunday, May 26, 2013 4:46:06 PM UTC+1, Vicente J. Botet Escriba wrote:

>
Yes, there is an issue here. I guess top() returns a const_reference to
ensure the class invariants.

Yes, returning a const-reference prevents the queue's ordering being invalidated, similar to set::iterator not being a mutable iterator.

 

Maybe pull() could be used to name both operations.

 

I prefer that name to move_top(), because the name "move_top" doesn't immediately tell me it combines the pop and top operations.  However we already have push/pop as the names for the pair of operations throughout Clause 23 so introducing push/pull in contrast to push/pop is a bit confusing.  My preference would be pop_value() instead of move_top(), however ...

 

I don't see the problem with stack and queue. stack top() returns a
reference and queue has no member top() and front() and back() returns a
reference.

I agree, the only issue I see is priority_queue::top() to allow std::priority_queue<MoveOnly>.  The other proposed changes allow a different coding style when using the adaptors but don't add any new functionality or allow anything that can't be done today.  I don't agree with the symmetry argument for adding members to std::queue and std::stack, the different adaptors serve different purposes and do not need to be interchangeable in generic code.

Adding the priority_queue::pop(value_type&) overload and nothing else would be enough to solve the MoveOnly case.

I'd prefer to write:

     auto x = pq.move_top();

rather than:

    PQ::value_type x;
    pq.pop(x);

but move_top() doesn't provide the strong exception safety guarantee.  If move_top() throws I don't know if it happened during the move-assignment in pop(value_type&) or during the return in move_top(), so the container is in an unspecified state and I might have lost data.  Any proposal would need to have wording to say that, and/or have is_nothrow_move_constructible<value_type> as a precondition for the strong exception safety guarantee.

[Vicente J. Botet Escriba]

Le 28/05/13 15:25, Jonathan Wakely a écrit :

On Sunday, May 26, 2013 4:46:06 PM UTC+1, Vicente J. Botet Escriba wrote:

>
Yes, there is an issue here. I guess top() returns a const_reference to
ensure the class invariants.

Yes, returning a const-reference prevents the queue's ordering being invalidated, similar to set::iterator not being a mutable iterator.

 

Maybe pull() could be used to name both operations.

 

I prefer that name to move_top(), because the name "move_top" doesn't immediately tell me it combines the pop and top operations.  However we already have push/pop as the names for the pair of operations throughout Clause 23 so introducing push/pull in contrast to push/pop is a bit confusing.  My preference would be pop_value() instead of move_top(), however ...

My preference is for pull, but pop_value would be acceptable.

Adding the priority_queue::pop(value_type&) overload and nothing else would be enough to solve the MoveOnly case.

I'd prefer to write:

     auto x = pq.move_top();

rather than:

    PQ::value_type x;
    pq.pop(x);

but move_top() doesn't provide the strong exception safety guarantee.  If move_top() throws I don't know if it happened during the move-assignment in pop(value_type&) or during the return in move_top(), so the container is in an unspecified state and I might have lost data.  Any proposal would need to have wording to say that, and/or have is_nothrow_move_constructible<value_type> as a precondition for the strong exception safety guarantee.

Agreed.

Best,
Vicente

[DeadMG]

move_top() does provide strong exception guarantee if nothrow moves.

[Lawrence Crowl]

There are similar issues and approaches in N3533 C++ Concurrent Queues.
http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2013/n3533.html

--
Lawrence Crowl

[Diego R.]

I agree in most, but I don't understand why move_top() has to provide strong exception guarantee since priority_queue use heap operations and they are often swapping objects without any verification. For example an exception could be thrown in middle of pop_heap and therefore to invalidate the priority queue. Am I right?

I like the name pull(),

   value_type pull()

    {

       std::pop_heap(c.begin(),c.end(),comp);

       value_type tmp = std::move(c.back());

       c.pop_back();

       return tmp;

    }