C++ STL stack question: Why does pop() not throw an exception if the stack is empty?

Question

Why does std::stack::pop() not throw an exception if the stack is empty and there is nothing to pop?

(I'm designing a specialized Stack for my own code and would like to know the tradeoffs with this approach (which requires one to manually check if the stack is empty) vs. throwing an exception.

My guess here would be that although C++ supports exception-handling, it comes with a small runtime overhead, and therefore, for maximum performance, the decision was made not to throw an exception in std::stack::pop).

Solution 1

You are correct. The C++ standard always prefers performance to safety. But there may be STL implementations that include debug range checks.

Solution 2

I would argue that the reason pop() doesn't have to throw an exception has nothing to do with efficiency or performance, but with - exceptions.

As is argued elsewhere:

1. SGI explanation: http://www.sgi.com/tech/stl/stack.html One might wonder why pop() returns void, instead of value_type. That is, why must one use top() and pop() to examine and remove the top element, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use top() to inspect the value at the top of the stack.

2. std::stack < T > is a template. If pop() returned the top element, it would have to return by value rather than by reference as per the of above explanation. That means, at the caller side it must be copied in an another T type of object. That involves a copy constructor or copy assignment operator call. What if this type T is sophisticated enough and it throws an exception during copy construction or copy assignment? In that case, the rvalue, i.e. the stack top (returned by value) is simply lost and there is no other way to retrieve it from the stack as the stack's pop operation is successfully completed!

Once we conclude that pop should not return the element it pops and thus its interface is fixed as void pop(), it - this being my opinion - doesn't make any sense anymore to prescribe what happens when pop() is called on an empty stack.

Note that the standard requires !empty()as precondition for calling pop().

UncleBens (in the comments) certainly has a point that not checking preconditions at runtime (which is never prescribed by the C++ std AFAIK) has a certain performance smell to it. However, to quote part of the original question: (emphasis mine)

(I'm designing a specialized Stack for my own code and would like to know the tradeoffs with this approach (which requires one to manually check if the stack is empty) vs. throwing an exception.

I will argue, that the fact that pop() doesn't return anything renders the question moot. It (IMHO) simply doesn't make sense to force pop() to validate if the stack is empty, when we really don't get anything back from it (i.e. if the stack would be empty pop() can simply be a noop, which is (admittedly) not prescribed by the Std either).

I think one can either ask why top() does not throw an exception or one can ask why pop() doesn't return the top element. If pop doesn't return anything, throwing an exception doesn't make sense (in the C++ world) -- Claiming that it doesn't throw an exception "because of the runtime costs of exceptions" like other answers seem to imply is - IMHO - missing the point.

Solution 3

As almost all features in C++, they are designed around the concept that you don't pay for what you don't use. Not all environments support exceptions, traditionally, and most notably game development.

So forcing the use of exceptions if you use std::stack would be failing one of the design guidelines. You want to be able to use stack even if exceptions are disabled.

Solution 4

I think it's worth mentioning that pop() is allowed to throw if the stack is empty -- it's just not required to. In your stack, you could assert that the stack wasn't empty, and that would be perfectly fine (pop on an empty stack seems to give UB, so you can do pretty much whatever you want, really).

Solution 5

Performance aside, I don't think popping from an empty stack is an exceptional scenario - therefore I would't throw there either.

View more solutions

Comments

[asdfjklqwer]

And it's for this reason (efficiency) that STL requires you to call value_type& top() followed by void pop(), rather than having a pop() which returns by value.

[Debajit]

So in an embedded system, vector::at() and new do not throw exceptions at all?

[Jerry Coffin]

@Nathan: Those are separated for exception safety. If the copy ctor throws while returning from a pop that returns by value, you've just leaked the item that was on top of the stack (i.e., the item is lost, and you can't restore it to the stack either). See: gotw.ca/gotw/008.htm

[Debajit]

Where is it documented that pop() is allowed to throw? Does the spec specify this?

[Admin]

@Jerry has it spot on! It has nothing to do with perf. In fact, forcing developers to call top before pop is worse in terms of performance...

[asdfjklqwer]

@Jerry Ah, I didn't consider that - makes perfect sense! @Moron Is top/pop not more efficient if the elements in question are expensive to copy?

[GManNickG]

@Moron: Do you have evidence for that?

[Admin]

@GMan: Of course not :-) One of the cases we talk of does not even exist! Perhaps I should have included the word "probably". And I meant to include the check for empty stack in the previous comment too.

[Jerry Coffin]

@Nocturne: §17.4.4.8/3: "Any other functions defined in the C++ Standard Library that do not have an exception-specification may throw implementation-defined exceptions unless otherwise specified." No exception specification is given for std::stack::pop(). It just invokes pop_back, which doesn't seem to have an exception specification either.

[Admin]

@Nathan: I don't see why pop has to return by value. I meant to also include the check for empty stack in the previous comment (ok, repeated that).

[asdfjklqwer]

Because it doesn't make sense to return a pointer/ref to a deleted element. But I'm guessing you know that and you're questioning whether std::stack must strictly own its contained elements, and therefore whether pop() should be responsible for deallocating an element or simply updating a stack pointer...

[GManNickG]

"lots of C++ code, no exception support from runtimes" Seems contradictory to me. C++ very clearly has exceptions, if your platform doesn't support it, you're not using C++, you're using an implementation-specific derivative of C++.

[Admin]

@Nathan: Yes, that is it. For me, the reason to pop an element off the stack would be to be able to use it! It just does not feel like the stack one learns about. Of course, having the container own the objects has its advantages.

[Debajit]

Thanks, that was informative. Could you provide a link where I can access the C++ standard?

[Admin]

I would argue that it is an exceptional scenario. Given that you would be checking for the empty stack anyway (most algorithms have this check built in), trying to pop an empty stack would be an exception.

[UncleBens]

I fail to see, though, how choosing not to enforce preconditions at runtime has something to do with anything other than performance...

[Omnifarious]

@UncleBens - I think the exception argument is the most compelling. It's impossible for ::std::stack::pop to satisfy the strong exception guarantee if it returns the top element.

[Martin Ba]

@Nocture: open-std.org/jtc1/sc22/wg21 -> open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3126.pdf

[CB Bailey]

To me, I think the more important point is that push_back() is defined to perform a.erase.(--a.end()) which is UB if a.begin() == a.end() and this is what allows "anything to happen". erase is normally guaranteed to throw nothing for list and nothing if the copy constructor or assignment operator of the contained type does not throw for vector and deque; these being the containers that you usually build a stack with.

[CB Bailey]

I don't understand this argument. Whether or not a stack implementation checks whether the stack is empty before popping or not gives the difference between the program being in a valid state after the pop or not. Whether an exception is thrown and how expensive this is, isn't the main issue. The trade off is: is it worth the implementation checking whether it is valid to perform the pop or not. If the program is designed such that it is guaranteed to never pop from an empty stack the check is redundant and pure overhead. Other clients may never be sure and would have to make the check anyway.

[Jerry Coffin]

@Charles Bailey: Presumably you meant pop rather than push_back?

[CB Bailey]

Oops, I meant pop_back being what pop calls.

[Martin Ba]

@Charles : Note that the question asked "why does pop() not throw an exception" and not why does pop not check its preconditions. With the way std::stack is designed, one has to view popand top together. And given a C++ mindset, it kind of becomes obvious that neither of them will check their preconditions. (Though in the case of popit would be trivial for an implementation to make it a no-op in case of an empty stack.) Calling pop or top on an empty stack is simply UB, just as accessing an out-of-bounds index of a std::vector.

[CB Bailey]

@Martin: I still don't understand how your orignal argument applies. The exception safety argument is an argument for top() and void pop() over pop() returning a value but for either interface you can choose to check pre-conditions and throw an exception or let undefined behavior happen when you pop from an empty stack. Checking pre-conditions is a necessary precursor for throwing a meaningful exception so it is valid to consider the fact that pre-conditions don't have to be checked if the interface isn't going to guarantee to throw an exception when popping from an empty stack.

[Martin Ba]

@Charles: pop() is allowed to check its preconditions and it is allowed to throw. Given its interface (returning void) I just think that it doesn't make sense to specify that it should throw one. If pop() were implemented to check whether the stack be empty, it should - IMHO - just ignore the call. (And we could get into a discussion if a failed precondition check should throw an exception or should abort() or assert() ...)

[Marc Mutz - mmutz]

+1 Thanks for being the voice of reason here. Exceptions just shouldn't be thrown in response to failed preconditions that the caller can (easily) check.

[Raedwald]

+1: it is about programming-by-contract, API design and undefined behaviour. pop() has undefined behviour if the stack is empty. A related answer: stackoverflow.com/questions/7390126/…