Why should pop() take an argument?

Question

Quick background
I'm a Java developer who's been playing around with C++ in my free/bored time.

Preface
In C++, you often see pop taking an argument by reference:

void pop(Item& removed);

I understand that it is nice to "fill in" the parameter with what you removed. That totally makes sense to me. This way, the person who asked to remove the top item can have a look at what was removed.

However, if I were to do this in Java, I'd do something like this:

Item pop() throws StackException;

This way, after the pop we return either: NULL as a result, an Item, or an exception would be thrown.

My C++ text book shows me the example above, but I see plenty of stack implementations taking no arguments (stl stack for example).

The Question
How should one implement the pop function in C++?

The Bonus
Why?

Answer 1

Using C++0x makes the whole thing hard again.

As

stack.pop(item); // move top data to item without copying

makes it possible to efficiently move the top element from the stack. Whereas

item = stack.top(); // make a copy of the top element
stack.pop(); // delete top element

doesn't allow such optimizations.

Answer 2

The problem with the Java approach is that its pop() method has at least two effects: removing an element, and returning an element. This violates the single-responsibility principle of software design, which in turn opens door for design complexities and other issues. It also implies a performance penalty.

In the STL way of things the idea is that sometimes when you pop() you're not interested in the item popped. You just want the effect of removing the top element. If the function returns the element and you ignore it then that's a wasted copy.

If you provide two overloads, one which takes a reference and another which doesn't then you allow the user to choose whether he (or she) is interested in the returned element or not. The performance of the call will optimal.

The STL doesn't overload the pop() functions but rather splits these into two functions: back() (or top() in the case of the std::stack adapter) and pop(). The back() function just returns the element, while the pop() function just removes it.

Answer 3

IMO, a good signature for the eqivalent of Java's pop function in C++ would be something like:

boost::optional<Item> pop();

Using option types is the best way to return something that may or may not be available.

Answer 4

To answer the question: you should not implement the pop function in C++, since it is already implemented by the STL. The std::stack container adapter provides the method top to get a reference to the top element on the stack, and the method pop to remove the top element. Note that the pop method alone cannot be used to perform both actions, as you asked about.

Why should it be done that way?

1. Exception safety: Herb Sutter gives a good explanation of the issue in GotW #82.
2. Single-responsibility principle: also mentioned in GotW #82. top takes care of one responsibility and pop takes care of the other.
3. Don't pay for what you don't need: For some code, it may suffice to examine the top element and then pop it, without ever making a (potentially expensive) copy of the element. (This is mentioned in the SGI STL documentation.)

Any code that wishes to obtain a copy of the element can do this at no additional expense:

Foo f(s.top());
s.pop();

Also, this discussion may be interesting.

If you were going to implement pop to return the value, it doesn't matter much whether you return by value or write it into an out parameter. Most compilers implement RVO, which will optimize the return-by-value method to be just as efficient as the copy-into-out-parameter method. Just keep in mind that either of these will likely be less efficient than examining the object using top() or front(), since in that case there is absolutely no copying done.

Answer 5

The only reason I can see for using this syntax in C++:

void pop(Item& removed);

is if you're worried about unnecessary copies taking place.

if you return the Item, it may require an additional copy of the object, which may be expensive.

In reality, C++ compilers are very good at copy elision, and almost always implement return value optimization (often even when you compile with optimizations disabled), which makes the point moot, and may even mean the simple "return by value" version becomes faster in some cases.

But if you're into premature optimization (if you're worried that the compiler might not optimize away the copy, even though in practice it will do it), you might argue for "returning" parameters by assigning to a reference parameter.

More information here