Exception-safe stack pop

• • Introduction
  • Discussion
  • Nothing is ever that simple
    • Add noexcept to std::deque::pop_back()
    • Make pop_value() on have basic exception-safety guarantee
  • Proposed wording
  • References

Introduction

The interface of std::stack is unergonomic, for exception-safety reasons described by Tom Cargill^[1].

Since the addition of move semantics and the noexcept operator in C++11 we can do better. Let's do better.

Discussion

Conventionally, a stack type provides this operation to remove the top of the stack and return it:

    auto i = a_stack.pop();

But this presents a problem for C++. The element has to be removed from the stack before returning, but in the general case copying the removed element into the return value could throw an exception. If that happens, the value has been lost. It's no longer in the stack, and it isn't returned. As Tom Cargill wrote:

So top is decremented before the copy construction. It is therefore impossible for a caller to recover from this exception and repeat the pop operation to retrieve that element off the stack.

C++'s std::stack avoids this problem by defining a different interface. The pop() member function returns void, so you have to do it like this:

    auto i = a_stack.top();
    a_stack.pop();

To avoid unnecessary copies, you typically want to do:

    auto i = std::move(a_stack.top());
    a_stack.pop();

This is ... not great.

It has been possible to improve since C++11, by adding a pop operation that is only enabled if std::is_nothrow_move_constructible<value_type> is true. It becomes even easier in C++20 using concepts:

    // Existing functions
    value_type&       top() noexcept;
    const value_type& top() const noexcept;
    void              pop();

    // New overload
    value_type        pop() noexcept
      requires is_nothrow_move_constructible_v<value_type>
               && noexcept(c.back()) && noexcept(c.pop_back());

The new overload is only available if returning the value can't throw, and if removing it from the underlying container can't throw.

The implementation is trivial:

    value_type pop() noexcept
      requires is_nothrow_move_constructible_v<value_type>
               && noexcept(c.pop_back())
    {
      auto v = std::move(top());
      pop();
      return v;
    }

Adding this as an overload of pop() does have some drawbacks.

There is no way for existing code to take advantage of the new overload without modifying the code to replace the top-pop-combo with just pop. (Contrast with other cases where adding move semantics to library components gives "free" speed-ups even to code that doesn't do any explicit moves itself). All existing code expects pop() to have a void return, so never does anything with the return value.

Existing code that continues to use the top-pop-combo will silently start to use the new overload if the constraints are satisfied, even though the value isn't used (because the code still expects the pop() call to have a void return). If the non-throwing move construction performs non-trivial work (e.g. transferring ownership of allocated memory) there could be a non-zero runtime overhead to returning the value.

It's also possible that generic code will be written using the new function, and then fail to compile when the template is instantiated with a value type that doesn't satisfy the constraints for the new overload. Adding an overload that has substantially different semantics is generally not a good idea.

A more conservative solution would be to add it with a new name:

    value_type        pop_value() noexcept
      requires is_nothrow_move_constructible_v<value_type>
               && noexcept(c.pop_back());

Since code has to be modified to take advantage of the new function, adjusting to the new name at the same time is trivial. This also avoids the risk of writing code that accidentally assumes that pop() always returns a value.

Nothing is ever that simple

The problem is that std::deque::pop_back() is not guaranteed to be noexcept, it's left up to the implementation. So std::stack<int>::pop_value() would not be guaranteed to be usable. That makes the feature a lot less useful.

Add noexcept to std::deque::pop_back()

There is no reason for pop_back() to throw. It might want to deallocate memory, but the allocator requirements say that the deallocate function doesn't throw.

Make pop_value() on have basic exception-safety guarantee

Don't constrain it, and only provide basic exception-safety? Caller can decide if they want to trust it or not, by querying with noexcept:

value_type pop_value() noexcept(is_nothrow_move_constructible_v<value_type> && noexcept(c.back()) && noexcept(c.pop_back()));

Proposed wording

[TODO: Declaration and effects as shown above. Add feature test macro.]

References

[1] Tom Cargill, Exception Handling: A False Sense of Security, C++ Report, Nov-Dec 1994.