Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

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

like image 276
Debajit Avatar asked Feb 03 '11 21:02

Debajit


People also ask

What happens if you pop an empty stack?

The element is popped from the top of the stack and is removed from the same. Parameters: The method does not take any parameters. Return Value: This method returns the element present at the top of the stack and then removes it. Exceptions: The method throws EmptyStackException is thrown if the stack is empty.

What happened when pop () called on the empty queue?

pop() function is used to remove an element from the front of the queue i.e. the oldest element in the queue is being removed.

What happens when you pop from an empty stack while implementing using the stack ADT in Java?

7. What happens when you pop from an empty stack while implementing using the Stack ADT in Java? Explanation: The Stack ADT throws an EmptyStackException if the stack is empty and a pop() operation is tried on it.

What if an array is empty but stack implementation wants to pop from it?

They are stack underflow and stack overflow. When we try to pop an element from an empty stack, it is said that the stack underflowed. However, if the number of elements exceeds the stated size of a stack, the stack is said to be overflowed.


1 Answers

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.

like image 128
Martin Ba Avatar answered Jan 30 '23 09:01

Martin Ba