23

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).

Debajit
  • 46,327
  • 33
  • 91
  • 100
  • 8
    You guessed almost correctly. It's not the overhead of exceptions that's the problem. It's testing if the stack is empty every time. If you use an std::stack, you are expected to know(or check yourself) when it becomes empty. – Benjamin Lindley Feb 03 '11 at 21:49
  • 1
    I'm not sure I understand how checking for stack-empty before each pop would be inefficient. It would be a very small constant-time comparison to make, wouldn't it? – Debajit Feb 03 '11 at 22:10
  • 1
    @Nocturne: It would be small, but it would still be something. Something > Nothing. That said, std::stack is a container adapter, so it just does whatever the underlying container does in this case. – Fred Nurk Feb 03 '11 at 22:31
  • @Fred: Actually come to think of it, most algorithms would probably be checking for empty stack anyway. So providing an IsEmpty() method and having pop throw an exception makes more sense to me (catching bugs and what not), and the issue of performance is kind of irrelevant. –  Feb 03 '11 at 23:36
  • @Moron: To get that behavior you are free to use underlying containers which throw on pop_back when empty, but that's just not the behavior of the stdlib containers. – Fred Nurk Feb 03 '11 at 23:36
  • @Fred: Sure, but that was not the point :-) (context: OP is trying to design his own stack). What happens if you do a top on an empty std::stack? Does it throw an exception? –  Feb 03 '11 at 23:41
  • @Moron: It calls and returns underlying_container.back(). Back() is UB for empty stdlib containers. – Fred Nurk Feb 03 '11 at 23:46
  • @Fred: So in your code, you _will_ be calling the empty check before calling the top, right? So Something > Nothing is probably moot, isn't it? i.e. the argument of empty check being a performance hit is not really valid, isn't it? And it seems to me that most algorithms, like say dfs etc have the empty check built in... Also, it seems like std:stack _requires_/(recommends?) the empty check to be called before a top. Anyway... –  Feb 03 '11 at 23:52
  • 3
    @Moron: Not all algorithms need to check. Depending on what is happening, you might be guaranteed by the rest of the algorithm that you never pop an empty stack. – Fred Nurk Feb 03 '11 at 23:57
  • @Fred: Of course, not arguing against that. Take dfs for instance! If you try to pop an empty stack, you are done :-) So you can perhaps deal with an exception there. In case of STL, the argument of performance is moot as you need to call empty check anyway. OP was looking for guidance whether his stack should have isEmpty or not and that decision should be driven by what the usage patterns would be. Trying to base in on what STL does or does not is actually asking the wrong question. –  Feb 04 '11 at 00:06
  • I wonder if similar conversations were had at some point when implementing `strcpy` vs `strncpy` – Robert Martin Jan 25 '13 at 16:39

6 Answers6

18

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.

Martin Ba
  • 37,187
  • 33
  • 183
  • 337
  • Thanks, that was informative. Could you provide a link where I can access the C++ standard? – Debajit Feb 03 '11 at 22:47
  • 2
    I fail to see, though, how choosing not to enforce preconditions at runtime has something to do with anything other than performance... – UncleBens Feb 04 '11 at 00:01
  • @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. – Omnifarious Feb 04 '11 at 03:32
  • @Nocture: http://www.open-std.org/jtc1/sc22/wg21/ -> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3126.pdf – Martin Ba Feb 04 '11 at 07:21
  • 1
    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. – CB Bailey Feb 04 '11 at 08:13
  • @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 `pop`and `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 `pop`it 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. – Martin Ba Feb 05 '11 at 21:30
  • @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. – CB Bailey Feb 06 '11 at 11:11
  • @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() ...) – Martin Ba Feb 06 '11 at 19:50
8

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

Axel Gneiting
  • 5,293
  • 25
  • 30
  • 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. – asdfjklqwer Feb 03 '11 at 21:52
  • 11
    @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: http://www.gotw.ca/gotw/008.htm – Jerry Coffin Feb 03 '11 at 22:00
  • @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... –  Feb 03 '11 at 22:07
  • @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? – asdfjklqwer Feb 03 '11 at 22:09
  • @Moron: Do you have evidence for that? – GManNickG Feb 03 '11 at 22:10
  • @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. –  Feb 03 '11 at 22:12
  • @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). –  Feb 03 '11 at 22:14
  • 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... – asdfjklqwer Feb 03 '11 at 22:27
  • @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. –  Feb 03 '11 at 22:35
6

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.

David
  • 9,635
  • 5
  • 62
  • 68
3

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).

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • Where is it documented that pop() is allowed to throw? Does the spec specify this? – Debajit Feb 03 '11 at 22:02
  • 4
    @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. – Jerry Coffin Feb 03 '11 at 22:13
  • 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 Feb 04 '11 at 08:06
  • @Charles Bailey: Presumably you meant `pop` rather than `push_back`? – Jerry Coffin Feb 04 '11 at 13:53
  • Oops, I meant `pop_back` being what `pop` calls. – CB Bailey Feb 04 '11 at 15:21
  • +1: it is about programming-by-contract, API design and undefined behaviour. `pop()` has **undefined** behviour if the stack is empty. A related answer: http://stackoverflow.com/questions/7390126/what-should-the-pop-method-return-when-the-stack-is-empty/7390181#7390181 – Raedwald Sep 13 '11 at 11:38
1

exceptions are optional, and the STL wants to be available everywhere. think embedded systems: lots of C++ code, no exception support from runtimes.

just somebody
  • 18,602
  • 6
  • 51
  • 60
  • 2
    So in an embedded system, vector::at() and new do not throw exceptions at all? – Debajit Feb 03 '11 at 21:54
  • 6
    "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++. – GManNickG Feb 03 '11 at 22:31
1

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

Nemanja Trifunovic
  • 24,346
  • 3
  • 50
  • 88
  • 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. –  Feb 03 '11 at 23:31
  • 3
    +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. – Marc Mutz - mmutz May 17 '11 at 15:26