New overloads for pop methods

[morw...@gmail.com]

A feature commonly esked for is a pop method for containers that would return the popped value.
To be sure that the function actually returns something, even if the container is empty, the user
shall provide a default value of type value_type which will be returned if the container is empty.
The behaviour of the function would look like this (here, for std::stack):

    template<typename T>
    T pop(const T& default_value)
    {
        if (empty())
        {
            return default_value;
        }
        T ret = top();
        pop();
        return ret;
    }

It's easy to extend this behaviour to pop_front and pop_back methods.
I bet that it has already been discussed back in time, but I did not  find any proof that a discussion
happened, so I just created my own. Since this overload does not exist, I assume there are some
strong arguments against?

[Jonathan Wakely]

At the return statement, if the copy constructor of T throws an exception you don't get the return value, but have already removed the element from the container, so it is lost forever. If the object contained the only copy of your swiss bank account details you have no way to access your money.  Much sadness ensues.

This is why std::stack forces you to access the top element separately from popping it. If copying the top element throws, the original is still in the container.

[morw...@gmail.com]

Le jeudi 20 juin 2013 12:22:53 UTC+2, Jonathan Wakely a écrit :

At the return statement, if the copy constructor of T throws an exception you don't get the return value, but have already removed the element from the container, so it is lost forever. If the object contained the only copy of your swiss bank account details you have no way to access your money.  Much sadness ensues.

This is why std::stack forces you to access the top element separately from popping it. If copying the top element throws, the original is still in the container.

What about returning a RAII wrapper that can be converted to T and performs the pop only when destructed?
Just kidding, I get your point.

[sean.mid...@gmail.com]

An alternative then might be a try_pop_back (and so on), something like:

   bool try_pop_back(T& out)

   {

     if (empty())

       return false;

     out = std::move(back());

     pop_back();

     return true;

   }

The pop_back() won't get called until after the move assignment into the "final" destination is complete (so exceptions shouldn't be any more of a problem than they usually are), and this variant has the added bonus that you can easily check if something exists while retrieving it without dealing with a default value, which at least personally I've found significantly more useful than wanting a default value.  It makes code like the following just a little sweeter:

   // current way

   if (!foo.empty())

   {

     auto v = foo.back();

     foo.pop_back();

     something(v);

   }

   // new way

   element_t v;

   if (foo.try_pop_back(v))

     something(v);

The big downside is that you must predeclare/initialize the output variable, which also means you can't really use auto (I can think of ways the language could make this nicer, but that's an entirely different discussion).

One big upside is that the semantics can be made to match the concurrent queue proposals and popular concurrency libraries such that there's a nice consistent API between concurrent and non-concurrent containers which makes writing algorithms and such way easier.  This matters in particular because the "current way" is a non-starter for concurrent queues due to an obvious race.  Having one interface that works on all containers seems to me like a gigantic win.

[DeadMG]

More relevantly, that logic doesn't hold in a world of noexcept move construction. There's no exception safety issue here if T's move constructor is noexcept.

[Nevin Liber]

> On Jun 20, 2013, at 6:25 PM, DeadMG <wolfei...@gmail.com> wrote:
>
> More relevantly, that logic doesn't hold in a world of noexcept move construction.

But that isn't the only world the standard has to support.

> There's no exception safety issue here if T's move constructor is noexcept.

There is no exception safety issue if T's copy constructor was throw()
in C++03 either.

I don't see how any of this is relevant, since the standard library
supports throwing move/copy constructors.
--
Nevin ":-)" Liber <mailto:ne...@eviloverlord.com> (312) 623-5420

[Xeo]

On Friday, June 21, 2013 1:52:31 AM UTC+2, Nevin ":-)" Liber wrote:

I don't see how any of this is relevant, since the standard library
supports throwing move/copy constructors.

Maybe, but the stdlib also doesn't care if the move constructor throws - for example, when regrowing a std::vector. If the type is move-only, it will move regardless of noexcept-ness. If it's copyable, it will favor noexcept move over copy over throwing move.

[DeadMG]

There is precedence for enabling extra features for types with noexcept moves if this is possible, and such a function would seem to be a good candidate.

[Nevin Liber]

Again, why is that relevant?  That isn't a changing interface; just a best effort to (a) preserve user data in the face of exceptions and (b) be efficient (in that order).

--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  (847) 691-1404

[Nevin Liber]

On 20 June 2013 19:12, DeadMG <wolfei...@gmail.com> wrote:

There is precedence for enabling extra features for types with noexcept moves if this is possible, and such a function would seem to be a good candidate.

Where is this precedence?  The previous vector example is an implementation detail, not an interface change.

So far, this just looks like being clever for the sake of being clever, and nothing else.  I would vote strongly against such a proposal.

--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  (847) 691-1404

[DeadMG]

Offering move semantics over copy semantics is not an implementation detail at all. Not to mention the hideous performance ramifications of copying over moving, but the existence of move-only types clearly shows that being able to move, as opposed to copy, is a serious interface consideration. A std::stack<std::unique_ptr<int>> is going to notice the difference in the interface. I also notice that, at least according to MSDN, there is only a const T& overload for `push`, preventing move-only types.

This is exactly the same case as the std::vector- it's a serious interface consideration which is important for the support of move-only types.

[Nevin Liber]

On 21 June 2013 10:58, DeadMG <wolfei...@gmail.com> wrote:

Offering move semantics over copy semantics is not an implementation detail at all. Not to mention the hideous performance ramifications of copying over moving, but the existence of move-only types clearly shows that being able to move, as opposed to copy, is a serious interface consideration.

I have *no* idea what you are talking about.  top() returns a reference; if the user needs it as a value (which is typically far more expensive than just using the reference), they can call std::move on it themselves.

What optimization does this schizophrenic interface proposal enable that can't be done otherwise?

A std::stack<std::unique_ptr<int>> is going to notice the difference in the interface.

That's a tautology; if the interface is different, of course some people will notice it.  I fail to see any optimization benefits this opens up.
 

I also notice that, at least according to MSDN, there is only a const T& overload for `push`, preventing move-only types.

I look at the standard or future drafts (such as N3690 for C++14) when talking about what is in the standard, as 2nd hand sources may be out of date, incorrect, or may only reflect current implementations.
 

This is exactly the same case as the std::vector- it's a serious interface consideration which is important for the support of move-only types.

*shrug*  Good luck with your proposal.

[Jonathan Wakely]

On Friday, June 21, 2013 4:58:28 PM UTC+1, DeadMG wrote:

Offering move semantics over copy semantics is not an implementation detail at all. Not to mention the hideous performance ramifications of copying over moving, but the existence of move-only types clearly shows that being able to move, as opposed to copy, is a serious interface consideration. A std::stack<std::unique_ptr<int>> is going to notice the difference in the interface. I also notice that, at least according to MSDN, there is only a const T& overload for `push`, preventing move-only types.

MSDN is wrong.

There is an issue with priority_queue::top() though, as *that* doesn't support move-only types, the other adaptors are OK.

See https://groups.google.com/a/isocpp.org/d/topic/std-proposals/TIst1FOdveo/discussion
 

[Richard Smith]

On Thu, Jun 20, 2013 at 4:52 PM, Nevin Liber <nli...@gmail.com> wrote:
>> On Jun 20, 2013, at 6:25 PM, DeadMG <wolfei...@gmail.com> wrote:
>>
>> More relevantly, that logic doesn't hold in a world of noexcept move construction.
>
> But that isn't the only world the standard has to support.
>
>> There's no exception safety issue here if T's move constructor is noexcept.
>
> There is no exception safety issue if T's copy constructor was throw()
> in C++03 either.
>
> I don't see how any of this is relevant, since the standard library
> supports throwing move/copy constructors.

This seems to be a problem with the proposed implementation, not with
the idea; the function becomes exception safe if the pop is performed
*after* the return value is constructed. I don't think that's actually
possible to guarantee in current C++, but we can get very close. (We
could get all the way if we added Jens' std::uncaught_exception_count
feature, or if we had guaranteed copy-elision in some cases, for
instance.)

[Sean Middleditch]

My original message seems to be stuck in a moderation queue for some time now (forgot to "join" before sending that message), so I apologize if a semi-duplicate shows up later.

In response to some of the concerns with exceptions in this proposal, and more importantly a desire to add some consistency with concurrent queues, I'd propose a slightly different addition; an example for just vector::pop_back (easily expandable to the other pop* functions for deque, list, and so on):

  bool try_pop_back(T& out_value)

  {

    if (empty())

     return false;

    out_value = std::move(back());

    pop_back();

    return true;

  }

  // old way

  if (!stack.empty())

  {

    auto v = stack.back();

    stack.pop_back();

    do_stuff(v);

  }

  // new way

  decltype(c)::value_type v;

  if (c.try_pop_back(v))

    do_stuff(v);

  // new way just wanting a default

  decltype(c)::value_type v; // v could be explicitly initialized if a different default value is needed

  c.try_pop_back(v); // don't care if there was a value to pop or we're just keeping the default value, no need to check return

  do_stuff(v);

I'm not at all fond of needing to predeclare the out value using the more verbose decltype syntax, but the result is still less code than now and roughly the same efficiency and behavior of the proposed defaulted-value pop_top(), minus the exception problems.

Far, far more importantly IMO is the part where the current interface cannot be used for concurrent data structures.  It's a huge race to separately check if empty and then access an element and then pop that same element from a data structure without wrapping the whole series of operations in a lock, so a try_pop* type of interface is required for lock-free efficient queues and other concurrent data structures.  Adding this version of the pop* function to all containers ensures that algorithms can be written which are neutral to whether a particular container is a concurrent variant or not (assuming this interface matches closely enough the interface of any concurrent containers being adding to the library).

Note that wrappers like stack - to be compatible with concurrent types - would need to implement try_pop_top as a wrapper over try_pop_back and the like in order to maintain compatibility with concurrent types.

It's also better than a default value as for many containers there is no sensible default value if you wanted to differentiate between "use default" and "not there," but as demonstrated allows a similar use to the proposed functions with only a little tiny bit more code (while still being concurrency-friendly).  For instance, with a vector of ints, there may not be a sensible default int value that isn't a legal value to be stored in the container, so you'd be forced to use the race-heavy current interface to check if you're getting a default or not.

[David Krauss]

On Thu, Jun 20, 2013 at 5:48 PM, <morw...@gmail.com> wrote:

 

To be sure that the function actually returns something, even if the container is empty, the user shall provide a default value of type value_type which will be returned if the container is empty.

 

You can add whatever interface you like using an adaptor. Now that we have inheriting constructors, derivation from standard containers is viable. This is doubly true for a

I don't think the default_value stuff will be very popular. pop*() on an empty container is UB. Constructing a default value just to remove UB when the user commits an error is very un-C++.

It would be nice to add a tag to pop() to enable range checking, as a std::nothrow_t function parameter or function template argument.

For what it's worth, I don't comprehend the objections to popping into the return value for nothrow moveable types. A throwing move constructor is such a smell that a compiler really should issue a warning. Few users are actually competent to understand the issue, and the code such a person writes to get around it will be just as exception-unsafe, and likely add more problems on top. If someone is surprised when pop() is void for their throwing moveable type, they will at least get a handle on the issue, or some keywords for online research that could lead to a real resolution of design problems.

[Nevin Liber]

On 22 June 2013 22:47, David Krauss <pot...@gmail.com> wrote:

For what it's worth, I don't comprehend the objections to popping into the return value for nothrow moveable types.

It makes the language *much* harder to learn.  You have to go into noexcept, implicit constructors, design decisions for the standard library (changing string to vector<char> suddenly stops your code from compiling), etc., just to explain the behavior.

Also, given current language rules, if you are clever it is performance neutral (assuming both RVO and that you need it by value instead of by reference); if not, it is a pessimization.  A typical implementation in pseudocode:

T pop_back()
{
    T t(std::move(back()));  // line 1
    back().~T();
    deallocate(&back());
    return t;
}

Are compilers allowed to optimize out line 1?  If not, then this is *always* a pessimization on current code and generic code (since generic code typically would not assume that the move constructors are marked noexcept).
 

A throwing move constructor is such a smell that a compiler really should issue a warning.

If you wish to propose that the standard library have all its move constructors marked noexcept, well, good luck with that.
 

Few users are actually competent to understand the issue, and the code such a person writes to get around it will be just as exception-unsafe, and likely add more problems on top.

Given that this has been the status quo for a decade and a half, can you please show the real world examples you have encountered where the code to get around this is exception-unsafe and has more problems?  We would all benefit from your experience in this area.

[Lawrence Crowl]

On 6/22/13, Sean Middleditch <sean.mid...@gmail.com> wrote:
> My original message seems to be stuck in a moderation queue for some time
> now (forgot to "join" before sending that message), so I apologize if a
> semi-duplicate shows up later.
>
> In response to some of the concerns with exceptions in this proposal, and
> more importantly a desire to add some consistency with concurrent queues,

See N3533.

> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposal...@isocpp.org.
> To post to this group, send email to std-pr...@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.
>
>
>


--
Lawrence Crowl

[Sean Middleditch]

On Monday, June 24, 2013 8:02:50 PM UTC-7, Lawrence Crowl wrote:

On 6/22/13, Sean Middleditch <sean.mid...@gmail.com> wrote:
> My original message seems to be stuck in a moderation queue for some time
> now (forgot to "join" before sending that message), so I apologize if a
> semi-duplicate shows up later.
>
> In response to some of the concerns with exceptions in this proposal, and
> more importantly a desire to add some consistency with concurrent queues,

See N3533.

Forgive me if I'm missing something, I'm not sure if you were just adding information or try to make a counter-point, but my point was to add compatible member functions to the existing non-concurrent interfaces to match those added in N3533.

[Nevin Liber]

On 20 June 2013 13:50, <sean.mid...@gmail.com> wrote:

An alternative then might be a try_pop_back (and so on), something like:

   bool try_pop_back(T& out)

   {

     if (empty())

       return false;

     out = std::move(back());

     pop_back();

     return true;

   }

The pop_back() won't get called until after the move assignment into the "final" destination is complete (so exceptions shouldn't be any more of a problem than they usually are),

Except with the current two liner, it is obvious in user code that user left the back() element in a weird state.
 

and this variant has the added bonus that you can easily check if something exists while retrieving it without dealing with a default value, which at least personally I've found significantly more useful than wanting a default value.  It makes code like the following just a little sweeter:

   // current way

   if (!foo.empty())

   {

     auto v = foo.back();

     foo.pop_back();

     something(v);

   }

   // new way

   element_t v;

   if (foo.try_pop_back(v))

     something(v);

The big downside is that you must predeclare/initialize the output variable, which also means you can't really use auto (I can think of ways the language could make this nicer, but that's an entirely different discussion).

In other words, it is still a pessimization.

The original question was is about turning a two-liner into a one-liner.  This is way more complicated for very little gain and no practical experience.  I would vote strongly against such a proposal, if it were to come up.

[Sean Middleditch]

On Thursday, June 27, 2013 11:53:39 AM UTC-7, Nevin ":-)" Liber wrote:

The pop_back() won't get called until after the move assignment into the "final" destination is complete (so exceptions shouldn't be any more of a problem than they usually are),

Except with the current two liner, it is obvious in user code that user left the back() element in a weird state.

Exceptions should not be leaving things in "weird" states, especially in a move constructor, or you are already in enough trouble.  If your move constructor can throw an exception after _partially_ moving, you have potentially serious problems all through the standard library and elsewhere in your code.  The exception problems with the OP suggestion are avoided with mine entirely.

 

The big downside is that you must predeclare/initialize the output variable, which also means you can't really use auto (I can think of ways the language could make this nicer, but that's an entirely different discussion).

In other words, it is still a pessimization.

 I'm not sure what you mean by that.

The original question was is about turning a two-liner into a one-liner.  This is way more complicated for very little gain and no practical experience.  I would vote strongly against such a proposal, if it were to come up.

No, it isn't.  The existing code is not two lines.   The original proposal is about popping values, getting the back value, and safely handling the case of an empty container, so that following logic can work independent of whether the container had been empty or not.  That's 5 lines at best right now, 6 with some formatting styles.

   value v{};

   if (!c.empty()) {

     v = c.back();

     c.pop_back();

   }

With the OP suggestion, that turns into a nicely concise:

   auto v = c.pop_back({});

Compared to the version I suggested:

   value v;

   c.try_pop_back(v);

So yes, my suggestion is ever so slightly more verbose than the one in the original suggestion, but it's still more concise than what we have now,  It also has the advantage that in cases where you actually care if the container was empty and a defaulted value is not sufficient (say, a stack of integers, or std::string, etc.) it still works.  Extrapolating to data structures like set or map, a try_erase(key) is also a big improvement:

  // now

  auto it = map.find(key);

  if (it != map.end())

    map.erase(key);

  use(it->second);

  // try_erase

  value v;

  if (map.try_erase(key, v))

    use(v);

Going a bit down that rabbit hole, various alternative versions of unordered_map and unordered_set which can contain significant performances improvements over the stdlib implementations (by having different conditions, e.g. allowing insert and erase to invalidate iterators and requiring that value move assignment is noexcept) once again cannot be implemented using the old-style interface (since you can't find an iterator, erase its key, and then reuse that iterator), and the original proposal doesn't work for types which have no "nil" state (and you may not want or just can't use something like std::optional<> for values).  Not supporting the generic and reusable-everywhere interface just makes C++ more complicated to use.

Plus, not that I enjoy hitting the same nail repeatedly, but consistency with concurrent containers would be nice.