What should the 'pop()' method return when the stack is empty?

Question

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

When designing a stack in C++, what should the pop() method (or front() method) return when the stack is empty? Which of the following design is better?

1. Throw an exception
2. Undefined, but require the user calling isempty() method to check before calling pop()
3. Return a bool code, while using an extra parameter (a reference) to pass the popped element
4. Define an unique empty element

---

OK, I see that my question is not that clear, let me try to rewrite it:

There are some data structures which can be implemented based on linked list like stack, queue, and each of them has a methods returning the front element (or the tail).

I want to know, is there any principle guideline about designing such a method regarding the case when the data is empty.

And my definition of better is "easy to use correctly and hard to use incorrectly".

Solution 1

The programming-by-contract style would be that having a non-empty stack is a precondition of calling pop, and that calling a method without meeting its preconditions has an undefined outcome. My implementation would throw a std::logic_error, but that would not be required. In C, my implementation would abort via assert.

The caller of popis responsible for ensuring that the precondition that the stack is not empty holds before calling pop. The stack should therefore have an isEmpty method for the caller to check.

Solution 2

The C++ STL actuall doesn't return anything via pop() since it decouples returning the value of an object and actually popping an object off the stack's internal data-structure, making them two separate functions. So that's another option to consider in your design of a stack data-structure.

Your third option is also a pretty idiomatic approach for these types of data-structures.

For your fourth option, rather than a "unique empty element", I would actually do a variation on your third option where your pop() function that takes a pointer argument rather than a reference type, and returns NULL if there are no objects left in the stack.

Solution 3

Which environment type is the code to run in? Often it is far better to match existing paradigms of behavior than to strike out on your own way of doing things.

When you ask for a element from an empty abstract list, does it throw an exception? If so, it is far better to make popping off a non-full stack throw an exception.

Undefined behavior is a bad choice when it is trivially easy to define the behavior.

If most of the code returns items via the return statement, then returning a control (bool for if it worked) is a bad design. If most of the code returns items via the parameter list, then returning a control via the return statement is a good design provided that the other calls on similar collections do likewise.

An empty element doesn't make a lot of sense, it becomes a magic value. For example, if I create a list and push five empty elements in it, is it the same as a list with no empty elements in it? Is it the same as a list with one empty element in it? Is it the same a list with some elements and an empty element in it? Empty lists being a "special" object is one thing, but empty elements are problematic because they don't really contain the behavior of the element, they contain the behavior of the list. Good object orientation has contents of the behavior encapsulated in the same object it describes.

Note that empty elements are not the same as sentinels. Sentinels are implementation details contained within a collection (and ideally should never be exposed externally). When I read "returns an empty element", I think one would have to be intimately knowledgeable about the implementation of the stack to use it. Too much intimacy between classes is called tight coupling, and it can make the code much more difficult to modify / fix / change going forward.

If you do strike out on your own way of doing things, then you should minimally make your entire side of the code behave the same. It makes it easier to read an maintain.

Solution 4

I might suggest having both pop and trypop methods. pop would simply call trypop and throw and exception if it fails. My reasoning is that, for some uses of a stack, attempting to pop when the stack is empty is indicative of a program logic error that should not happen - either unbalanced push/pop, or mishandling of an earlier failure to push due to resource exhaustion. For other uses, failure to pop just means you're at the end of input. When using a programming model with exceptions, distinguishing these uses allows you to avoid cluttering the caller with performing the check for empty stack and throwing the exception.

Solution 5

The SGI STL implementation of stack has this design note:

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.

SGI further specifies for pop():

Precondition: empty() is false. Postcondition: size() will be decremented by 1.

As for the behavior of top(), SGI specifies this:

Precondition: empty() is false.

View more solutions

Comments

[Jiri Kriz]

In this case the question could be: what should top() do when applied to an empty stack? Interestingly few information about it can be found on the web.

[zhanwu]

thanks for Jiri's comment, it's exactly my point

[zhanwu]

I agree that I should keep all behaving the same way, I am just looking for the way... I thought there might be something like the advises from "Effective C++", giving me some direction

[Edwin Buck]

There's a lot of choices to be made. If you are building your own collection library (it happens sometimes) then it's appropriate to do things differently (based on your needs). As far as the best practices go, it's best to be consistent, and to use good coding practices beneficial to all types of coding (unit testing, language specific practices (like if (0 == x)), etc).

[Jason]

This is one reason I like pointer types ... you can always return NULL which indicates you did not get a valid response. That's always a much better option to me than a "default empty type" which can end up being ambiguous or create further confusion (i.e., a list of "default empty types"??).

[SingleNegationElimination]

the C++ philosophy of "Dont pay for what you don't use" would suggest that popping an element off an empty stack should be undefined behavior. Correct algorithms either won't attempt to pop from an empty stack because of the structure of the algorithm, or correctly range check; either by explicitly calling empty() or using a different method that does bounds checking and raises as needed or returns a sentinel.

[R.. GitHub STOP HELPING ICE]

I thought that was the C philosophy, and the C++ philosophy was "pay double for everything you don't use"... :-)