The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

C++ Stacks

This is probably a commonly talked about topic.

Consider this code:
#include <iostream>
using namespace std;

template <class T>
class Stack {
    Stack() : index(-1) {}
    ~Stack() {}
    void push(T val)
        // Increment index, then store
        data[++index] = val;
    T pop()
        // Retrieve, then decrement index
        return data[index--];

    T data[100];
    int index;

Anyone see any problems with the pop() method?

NOTE:  No, this is not a college test or quiz nor anything of the sort.
Wednesday, May 03, 2006
Popping on an empty stack needs to throw an exception, return null or something.
Cade Roux Send private email
Wednesday, May 03, 2006
Why not use the STL Stack?
Honu Send private email
Wednesday, May 03, 2006
Wednesday, May 03, 2006
Cade Roux:

Good catch -- I didn't notice that.  This code was presented to me as an example to show basics.  I assume the missing empty stack check would have complicated the original goals. 

STL Stack: Yes, possible to do.  This was to demonstrate something.

I don't like the POP call.  In particular "return (index--)"

When does index get decremented relative to the return or exit point of pop() ?

It's confusing.  Consider this:


--no good, index has the wrong value.


--no good, index is never decremented.


--This makes more sense to me...
Wednesday, May 03, 2006
The code does what you want (although open to a notation-induced ambiguity panic attack).

I haven't programmed in C++ in over 10 years, but what you are talking about is sequence points:
Cade Roux Send private email
Wednesday, May 03, 2006
Eric, try to translate it to assembly code in your head. The  return data[index--]; statement probably gets translated into something like this:

# pseudo assembly discounting the need to move
# some of the registers into memory again after decrementing
mov data[index], return_register
dec index

Personally i'd prefer to make a zero based stack so the pre and post operations get swapped. It's a personal preference, and it shouldn't change the semantics seen from the outside.
Peter Monsson Send private email
Wednesday, May 03, 2006
Herb Sutter points out that the method "T Pop();" cannot be made exception safe. He has a full writeup in Exceptional C++, and the original GOTW is here:
dobie Send private email
Wednesday, May 03, 2006
The logic is made clearer if you look at the assembly code generated by the following functions (do a gcc -S):

      1 int
      2 B()
      3 { 
      4  int a;
      5  return --a;
      6 }

    14    leal    -4(%ebp), %eax
    15    decl    (%eax)
    16    movl    -4(%ebp), %eax
    17    leave
    18    ret

      8 int
      9 A()
    10 { 
    11  int a;
    12  return a--;
    13 }

    33    movl    -4(%ebp), %eax
    34    leal    -4(%ebp), %edx
    35    decl    (%edx)
    36    leave
    37    ret

In B(), decl comes before %eax is used as the return value, and in A(), decl comes after %eax is used.
Wednesday, May 03, 2006
Beside the buffer underflow in the pop() method, on the other side there is a buffer overflow in the push() method.
Thursday, May 04, 2006

Thanks much!  The sequence points and the dissassembly definitly shed the light I was looking for.

I know much of this is personal preference... So how would you change it and if you care to share this, would you also mind telling me why you choose your way over the example?

Thanks again!
Thursday, May 04, 2006

in the given version you have to manually count the number of elements you stored in the stack to ensure that you don't call push() or pop() too often.

Thus I would add checks for under- and overflow in both methods. Additionally, I would initialize index with 0 and use
data[index++] = val;
return data[--index];
because index then equals the number of elements currently stored in the stack. Consequently I would rename it to 'count' and add another method to retrieve it, so I no longer need to count it manually. This can additionally be used as an is_empty check (when it returns 0).

Because a count can't become negative, I would then use an  unsigned int - but that's another topic on its own.
Thursday, May 04, 2006

Totally agree.  In fact, I just read a blurb on this in Effect C++ (Meyers) and he touches on this point exactly.  Meyers suggest implementing a class to manage the stack (inserting, deleting, changing, etc...) and a class that defines the object being managed.  Something I do often in other code areas but was not aware that what I was doing had a philosophy or best practice behind it.  :)

Good point!
Friday, May 05, 2006
Friday, May 05, 2006

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz