Node-based stack class (need peer review)

Question

I recently wrote a node-based stack class, per instructions (specs in the comments before the code, taken from the forum post). I was told to post it here for review by one of the friendlier members of the SO community, so here it is. For simplicity's sake: I put the definitions with the implementation. I understand when to use header files =)

Mainly, I want to know if my use of delete is sound. I am still unsure of myself when it comes to using destructors; the specs made it sound like the ONLY time I should be deleting nodes should be during pop, and anything else is unsafe. I also don't understand the use of a copy constructor/assignment constructor here.

Anyways, any bugs or comments about the code would be great.

/*stack class

Background: the specs for this are, verbatim: 

"Write a node-based stack class smile.gif

The stack is one of the most fundamental data structures used in computer science.

A stack has three basic operations:

push(value) - puts a value on the top of the stack
pop() - removes and returns the value that's on the top of the stack
peek() - return (but does not remove) the value off the top of the stack

Before creating the stack, you first have to create a Node class, which is a 
very basic class with just two member variables: the value of the node, and a 
pointer to the previous node in the stack.

Your stack should have only one member variable: the top node of the stack. 
When you push, you add a node with the new value, with it's previous pointer 
pointing towards the current stack top item. When you pop, you delete the top 
node and then set the top of the stack to whatever that node's previous node 
pointer was.

push, pop, and peek must all run in constant time.

You should write it so that it can only push (and pop/peek) ints."
*/

#include <string>
#include <iostream>

class Node
{
    private:
        int value;
        Node* prev;

    public:
        int returnValue() { return value; }
        Node* returnPtr() { return prev; }

        /* constructors and destructors */

        Node(int val, Node* ptrToLast) 
        {
            value = val;            
            prev = ptrToLast; 
        }
};

class Stack
{
    private:
        Node* top;
        int size;

    public:
        Stack() { size = 0; top = NULL; }
        //added this after told the need for a destructor; not sure if it works
        ~Stack() {   
                    while (top != NULL) 
                    {  
                        Node* tempPtr = top.returnPtr();
                        delete top;
                        top = tempPtr;
                    }
                 }     

        Node* returnTopPtr() { return top; }

        void push(int);
        int pop();
        int peek();

        //bonus; figured it might be worth knowing how many
        //nodes are in a given stack 
        int returnSize();
};

int Stack::returnSize()
{
    return size; 
}

void Stack::push(int value)
{ 
    ++size;
    Node* tempPtr = top;
    top = new Node(value, tempPtr); 
}

int Stack::peek()
{
    return top->returnValue();
}


int Stack::pop()
{    
    const std::string throwStr = "You are trying to access/delete a node that doesn't exist. Seriously. ";

    if (size == 0)
    {
        throw(throwStr);
    }

    --size; 

    Node* tempPtr = top->returnPtr();
    int tempVal = top->returnValue();
    delete top;
    top = tempPtr;

    return tempVal;    
}

Solution 1

First, a few general comments which don't cause problems in this case, but some may do so in other situations:

You should only throw exceptions derived from the class std::exception. C++ does allow you to throw any type (like a string, in your case), but it's a really bad idea.

Class members should be initialized with initializer lists, as shown below: (this can cause errors in other cases. If you don't use the initializer list, the members are first default-constructed, and then the assignment operator is used in the body of the constructor to overwrite them. Not all types have an assigment operator, or the assignment operator may have undesirable side effects, so not using initializer lists can be problematic)

Node(int val, Node* ptrToLast) : value(val), prev(ptrToLast) {}
Stack() : size(0), top(NULL) {}

Naming your functions return* us pretty pointless. Just call them size() and topPtr(), or perhaps getSize() and getTopPtr()

Second, you didn't follow the rules. ;) Your stack class has two member variables, it was only allowed to have one. :)

Finally, things that break the stack:

This will crash, as you try to dereference a null pointer:

void test() {
  Stack s;
  s.peek(); // crashes
}

This will leak memory, as the allocated node is never deleted (the Stack destructor should do that):

void test() {
  Stack s;
  s.push(1);
}

The destructor should look something like this:

~Stack() {
  while (top != NULL){
    Node* next = top.returnPtr();
    delete top;
    top = next;
  }
}

This one should be fun too:

void test() {
  Stack s;
  s.push(1);
  Stack t(s);
  s.pop();
}

t.returnSize() will now return 1, but t.top points to the node in s that was just deleted. This should be fixed by defining a copy constructor and an assigment operator for the stack (and perhaps for the node class as well) The copy constructor would look like this:

Stack(const Stack& s);

and is called if you initialize one stack from another, like in the above. The assignment operator looks like this:

Stack& operator= (const Stack& s);

and is called if I assign one stack to another, after both are initialized:

Stack s;
Stack t;
t = s; // now both are already initialized, so the assigment operator is used, not the copy constructor

The role of these functions is to ensure that t becomes a copy of s. So each node in s should be copied, and assigned to t, to avoid them pointing to the same nodes. (Which is a wonderful example of your question about ownership earlier, btw. The nodes should belong to exactly one Stack object. If it becomes shared between multiple, you have a problem, and it's just a matter of time before it turns into a crash)

And finally, if we want to get a bit nastier:

void test() {
  Stack s;
  s.push(1);
  s.push(2);
}

What happens if the memory allocation for the second node fails (perhaps we ran out of memory. Unlikely, but it can happen). An exception is thrown after you incrmented size. The size of s will now be 2, even though top still points to the first node If you think this is too unlikely a problem to be taken seriously, imagine a small extension to your class. Let's say it was a template, so that it could store other types than an int.

That means that every time we create a node, we have to call the value type's copy constructor. That could throw an exception too. We don't know, because we have no clue which type the user might try to store in the stack.

The notion of "Exception safety" is important and really really difficult to get right. Basically, which state is your class in if an exception is thrown? Is it still in a valid state? (it should always be). Has it lost any data (for some cases that might be unavoidable, for others it can be avoided with care), and if it has lost data, has it been deleted correctly? Destructors called, memory released? (again, this should always be the case)

The last point here is why I was so sure you'd have at least one bug. Everyone gets exception safety wrong, including me most of the time. Writing a correct implementation of sometihng as simple as a stack is surprisingly difficult in C++. :)

Bonus:

In response to comments asking about copy constructors, destructors and RAII, let's just do the whole thing: First, let me say that there is probably one or two bugs left I haven't spotted. Second, here's the code I tested against, and all the following passes it. Feel free to run your own code through it as well. (it should work as is, except you'll have to rename the getSize function): (the live variable is one I added for debugging. I've modified my Stack implementations so that constructors increment it, and destructors decrement it, just to verify that the number of constructions and destructions are equal. This should obviously be removed from the Stack class once you're sure it works

Test code

static int live; // debugging - keeps track of how many nodes have been allocated. Constructors add 1, destructors subtract. It should end in 0

#include "stack.h"
#include <iostream>
#include <cassert>

int main(){
    {
        // test stack creation + push
        Stack s;
        s.push(1);
        s.push(2);
        s.push(3);
        assert(s.getSize() == 3);

        Stack t;
        t.push(4);
        t.push(5);
        t.push(6);
        assert(t.getSize() == 3);

        // test assigment operator when both stacks contain data
        s = t;
        assert(s.getSize() == 3);
        assert(s.peek() == 6);
        assert(t.peek() == 6);

        Stack u(s);
        // test self assigment when stack contains data
        u = u;
        assert(u.getSize() == 3);
        assert(u.peek() == 6);


        Stack v;
        // test copy construction from stack with data
        Stack w(t);
        assert(w.getSize() == 3);
        assert(w.peek() == 6);
        assert(t.getSize() == 3);
        assert(t.peek() == 6);

        // test assignment operator when source is empty, destination contains data
        w = v;
        assert(w.getSize() == 0);
        assert(v.getSize() == 0);

        // test copy construction from empty stack
        Stack x(v);
        assert(x.getSize() == 0);
        assert(v.getSize() == 0);

        // test pop
        assert(t.pop() == 6);
        assert(t.pop() == 5);
        assert(t.pop() == 4);

        assert(s.pop() == 6);
        assert(s.pop() == 5);
        assert(s.pop() == 4);
    } // at this point, all allocated stacks go out of scope, so their destructors are called, so now is a good time to check for memory leaks:
    assert(live == 0);
}

---

Fixed implementation

Now, first the straightforward fix. Copy constructor, assignment operator and destructor have been added on the Stack class. The Node class is still problematic if used in isolation, but as long as it is only used through the Stack, we can make sure nodes get copied and deleted properly. Unfortunately, Stack now needs access to Node.tail_ in order for copying to work, so I made it a friend. So it works, but it's not elegant.

#include <stdexcept> // for std::exception

class Stack;

class Node
{
    private: // changed naming to head/tail, which are commonly used in implementations of linked lists like this. The head is the current element, tail is a pointer to the remainder
        int head_;
        Node* tail_;

    public:
        friend class Stack; // this is necessary for the Stack copy constructor in order to modify the tail pointer after the node is created.
        // the elegant solution had been to define a copy constructor on the Node class as well, but we'll get to that

        int head() const { return head_; }
        Node* tail() const { return tail_; }

        Node(int val, Node* prev) : head_(val), tail_(prev) { ++live; } // use initializer list
        ~Node() { --live; }

        Node(const Node& other) : head_(other.head_), tail_(other.tail_){ ++live; }; // this could be omitted, but I use it to update 'live' for debugging purposes
};

class Stack
{
    private:
        Node* top;
//        int size; // we don't actually need the size at all, according to spec, so I removed it to keep things simple

        bool empty() const { return top == NULL;}

        void freeNodes() { // helper function to avoid duplicate code
            while (!empty()){
                pop();
            }
        }
    public:
        Stack() : top() {} // use initializer list
        ~Stack() { // destructor - the stack is being deleted, make sure to clean up all nodes
            freeNodes();
        }
        Stack(const Stack& other) : top() { // copy constuctor - we're being initialized as a copy of another stack, so make a copy of its contents
            if (other.empty()){
                return;
            }

            top = new Node(*other.top); // copy the first node, to get us started

            Node* otherNext = other.top->tail();            
            Node* current = top;

            while (otherNext != NULL){
                current->tail_ = new Node(*otherNext); // copy the current node
                current = current->tail(); // move to the next node
                otherNext = otherNext->tail();
            }
        }
        Stack& operator= (const Stack& other) {
            if (this == &other){ // If we assign this stack to itself (s = s), bail out early before we screw anything up
                return *this;
            }

            //now create the copy
            try {
                if (other.empty()){
                    freeNodes();
                    top = NULL;
                    return *this;
                }
                // naively, we'd first free our own stack's data before constructing the copy
                // but what happens then if an exception is thrown while creating the copy? We've lost all the current data, so we can't even roll back to a previous state
                // so instead, let's simply construct the copy elsewhere
                // this is almost straight copy/paste from the copy constructor. Should be factored out into a helper function to avoid duplicate code
                Node* newTop = new Node(*other.top); // copy the first node, to get us started

                Node* otherNext = other.top->tail();
                Node* current = newTop;

                while (otherNext != NULL){
                    current->tail_ = new Node(*otherNext); // copy the current node
                    current = current->tail(); // move to the next node
                    otherNext = otherNext->tail();
                }
                // once we're sure that we're able to create the copy of the other stack, we're ready to free the current one
                // this is a bit of duplicate code
                freeNodes();
                top = newTop;
                return *this;
            }
            catch (...){      // if an exception was thrown
                throw;        // and rethrow the exception so the application can deal with it
            }
        }

        // Node* returnTopPtr() { return top; } // not necessary. It's not a required part of the public interface, and class members can just access the top variable directly

        void push(int);
        int pop();
        int peek() const;

        int getSize() const{
            if (empty()){ return 0; }
            int i = 0;
            for (Node* cur = top; cur != NULL; cur = cur->tail_, ++i){}
            return i;
        }
};

void Stack::push(int value)
{ 
    Node* currentTop = top;
    top = new Node(value, currentTop); // this could throw an exception, but if it does, our stack will simply be left unchanged, so that's ok
}

int Stack::peek() const
{
    if (empty()){
        throw std::exception("Stack is empty");
    }
    return top->head();
}

int Stack::pop()
{    
    if (empty()){
        throw std::exception("Stack is empty");
    }

    Node* tail = top->tail();
    int result = top->head();
    delete top;
    top = tail;

    return result;
}

---

RAII v. 1

RAII is a lousy name for a vital technique. The basic idea is that every resource allocation (including, but not limited to, memory allocations with new.) should be wrapped in a class which takes care of copying or deleting the resource as necessary. In our case, rather than having Stack keep track of all the nodes, we could simplify things a bit by making the Node class itself do most of that work. Now Node has been given copy constructor, assignment operator and destructor too. The stack now just has to keep track of the top node... almost. It is still a bit iffy because Stack.push allocates new nodes, but Node is now responsible for most of the deletions. . However, it does allow us to get rid of the loops we needed before to delete or copy the node list.

Stack still needs to access thetail_member ofNode`, but this time, I made an accessor function instead of making the class a member. Overall, better, but I'm still not happy with it.

#include <stdexcept>

class Node
{
private:
    int head_;
    Node* tail_;

public:
    int head() const { return head_; }
    Node* tail() const { return tail_; }
    Node*& tail() { return tail_; } // Another way to allow Stack to modify the tail. Needed for pop()


    Node(int val, Node* prev = NULL) : head_(val), tail_(prev) { ++live; }

    ~Node(){ --live; delete tail_; } // it is safe to call delete on a NULL pointer

    Node(const Node& other) : head_(other.head()), tail_(NULL) {
        ++live;
        if (other.tail() == NULL){
            return;
        }
        tail_ = new Node(*other.tail());
    }

    Node& operator= (const Node& other){
        if (this == &other){
            return *this;
        }
        head_ = other.head();
        if (other.tail() != NULL){
            return *this;
        }

        Node* oldTail = tail_;

        try {
            tail_ = new Node(*other.tail());
        }
        catch(...){
            tail_ = oldTail;
            throw;
        }
    }
};

class Stack
{
private:
    Node* top;

    bool empty() const { return top == NULL;}

public:
    Stack() : top() {} 
    ~Stack() {
        delete top;
    }

    Stack(const Stack& other) : top(){
        if (other.empty()){
            return;
        }

        top = new Node(*other.top);
    }

    Stack& operator= (const Stack& other) {
        if (this == &other){
            return *this;
        }

        Node* oldTop = top;

        try {
            top = NULL;
            if (other.top != NULL){
                top = new Node(*other.top);
            }
            delete oldTop;
            return *this;
        }
        catch (...){ 
            delete top;
            top = oldTop;
            throw;  
        }
    }

    void push(int);
    int pop();
    int peek() const;

    int getSize() const{
        if (empty()){ return 0; }
        int i = 0;
        for (Node* cur = top; cur != NULL; cur = cur->tail(), ++i){}
        return i;
    }
};

void Stack::push(int value)
{ 
    Node* currentTop = top;
    top = new Node(value, currentTop);
}

int Stack::peek() const
{
    if (empty()){
        throw std::exception("Stack is empty");
    }
    return top->head();
}

int Stack::pop()
{    
    if (empty()){
        throw std::exception("Stack is empty");
    }

    Node* tail = top->tail();
    int result = top->head();
    if (top != NULL){
        top->tail() = NULL; // detach top from the rest of the list
        delete top;
    }

    top = tail;

    return result;
}

---

RAII v.2

To solve the problems mentioned above, I decided to change my strategy a bit. Node now does all the heavy lifting, including the push/pop/peek operations. Stack is simply a thin wrapper around these. This turned out to solve most of the problems. Stack no longer needs to mess around with private members of Node, and we have some clearer rules for ownership. The stack owns the top node, and every non-top node is owned by its parent -- and this time, the owner both creates, copies and destroys the node. Much more consistent.

To implement this, I had to add an isLast function on the Node class because otherwise, Stack.pop had no way of knowing whether or not it was time to delete top. I'm not 100% happy with this solution either (and if I hadn't removed the size member from the stack, I could have used that to solve the problem)

But overall, this one is both cleaner and simpler than the above attempts. (It's the only one I spent less than an hour debugging, for one thing. ;))

#include <stdexcept>

class Node {
public:
    Node(int value, Node* prev = 0) : head(value), tail(prev) { ++live;}
    ~Node() { 
        --live;
        delete tail;
    }

    Node(const Node& other) : head(other.head), tail(0) {
        ++live;
        if (other.tail != 0){
            tail = new Node(*other.tail);
        }
    }

    Node& operator= (const Node& other){
        if (this == &other){
            return *this;
        }

        Node* oldTail = tail;
        tail = new Node(*other.tail);
        delete oldTail;

        head = other.head;

        return *this;
    }

    void push(int val){
        tail = new Node(head, tail);
        head = val;
    }

    int peek(){
        return head;
    }
    void pop(){
        Node* oldTail = tail;
        head = tail->head;
        tail = tail->tail; // lol
        oldTail->tail = 0;
        delete oldTail;
    }

    bool isLast() { return tail == NULL; }

    int getSize() const{
        int i = 0;
        for (const Node* cur = this; cur != NULL; cur = cur->tail, ++i){}
        return i;
    }


private:
    Node* tail;
    int head;
};

class Stack {
public:
    Stack() : top(){}
    ~Stack() { delete top; }
    Stack(const Stack& other) : top() {
        if (other.empty()){
            return;
        }

        top = new Node(*other.top);
    }

    Stack& operator= (const Stack& other){
        if (this == &other){
            return *this;
        }

        Node* newTop = NULL;
        if (!other.empty()){
            newTop = new Node(*other.top);
        }
        delete top;
        top = newTop;

        return *this;
    }

    void push(int val){
        if (empty()) {
            top = new Node(val);
        }
        else {
            top->push(val); 
        }
    }

    int peek(){
        if (empty()){
            throw std::exception("Empty stack");
        }
        return top->peek();
    }
    int pop(){
        int result = peek();

        if (top->isLast()){
            delete top;
            top = NULL;
        }
        else {
            top->pop();
        }


        return result;
    }

    int getSize() const{
        if (empty()){ return 0; }
        return top->getSize(); 
    }

private:
    bool empty() const { return top == NULL; }
    Node* top;
};

Since all this started as an attempt to show you why C++ isn't a very nice beginners language, I think I can safely say mission accomplished!

:)

Solution 2

Alright - so here's a quick review. Keep in mind that somethings will be my personal opinion (just like the comment I wrote.)

1 - whenever accessing a value or method that you have a pointer into, check if the pointer is valid first! This will cause you to seg-fault otherwise. For example, if you peek before pushing a node in, you call NULL->returnValue(). This is no good.

2 - you don't need the temp pointer you are using in the push & you should check if you are being able to successfully allocate memory.

3 - you need a copy constructor / destructor because your object manages dynamically allocated data. So what happens is that by default, c++ only copies your static values when copying an object & only dealocates memory for static variables when destructing the object. A copy constructor & a destructor makes sure you go through your dynamic memory & take care of it. (IE: for the destructor you want to delete each node.)

4 - returnTopPointer is a horrible idea - it gives people access to your internal data & lets them do whatever they want.

If you need help with the copy constructor & destructor just let us know.

Solution 3

There are many style issues that warrant discussion - but the biggest issue is that whenever you explicitly manage dynamic memory within your class, at a minimum you need a user defined destructor, a copy constructor and an assignment operator to handle all the dynamic memory issues appropriately - or else you will have memory leaks and undefined deletions. The reason you need to explicitly define these functions is because you need a copy or an assignment to make copies of the structures that your head pointer and subsequent nodes point to and not just copy the address that they point to (which is the default behavior of the implementations provided by the compiler) - and the default destructor does not ever delete dynamically allocated memory - which is why you need to define a destructor that does.

Here is a reasonable implementation that you can play with - but more importantly, contrast it with an approach (included at the end) that uses vector and does not have to deal at all with explicit memory management:

    
class Stack
{
  // a nested implementation class that the client needs to know nothing about
  struct Node
  {
     Node* prev;
     int value;
     Node(Node* prev, int value) : prev(prev), value(value) { }
     Node() : prev(0), value(0) { } 
     ~Node() { delete prev; }  // clean up after yourself

     // copy recursively until you hit a null pointer
     Node(const Node& o) : value(o.value), prev( prev ? new Node(*prev) : 0 ) { }
  };

  Node* head_;
  int size_;

public:  

  Stack() : head_(0), size_(0) { }
  ~Stack() { delete head_; }

  // copy recursively until null
  Stack(const Stack& o) : head_(o.head_ ? new Node(*o.head_) : 0) { }

  // use copy constructor to do assignment
  Stack& operator=(const Stack& o)
  {
    Stack copy(o);
    Node* cur = head_;

    head_ = copy.head_;
    size_ = copy.size_;

    copy.head_ = cur;  // copy's destructor will delete
    return *this;
  }

  void push(int value)
  {
    head_ = new Node(head_,value);
    ++size_;
  }
  int peek() const
  {
    if (!head_) throw "Attempting to peek off an empty stack!";
    return head_->value;
  }
  int pop()
  {
    if (!head_) throw "Attempting to pop off an empty stack!";
    int ret = head_->value;

    Node* cur = head_;    // hold on to it so we can delete it
    head_ = head_->prev;  // adjust my pointer
    cur->prev = 0;        // if this is not set to 0, all nodes will be deleted

    delete cur;
    --size_;
    return ret;
  }
  int size() const { return size_; }
};



// -- an easier way to write a stack of ints ;)
struct VecStack
{
    std::vector<int> vec;

    void push(int x)
    {
        vec.push_back(x);
    }
    int peek() const
    {
        if(vec.empty()) throw "Is Empty";
        return *--vec.end(); // you may prefer vec[vec.size() - 1];
    }
    int pop() 
    { 
        if (vec.empty()) throw "Is Empty";
        int ret = *--vec.end();
        vec.pop_back();
        return ret;
    }
    int size() const { return vec.size(); }
};

Solution 4

In Stack::push(), new can fail (out of memory), but you have already incremented size. It's unlikely to happen, but would lead to an inconsistent state.

You initialize top to NULL, so if you call peek() before pushing anything, you will crash. You should handle that. Similar bad things happen if you call pop() before calling push().

Consider using constructor initializer lists, e.g.:

   Node(int val, Node* ptrToLast) : value(val), prev(ptrToLast) {}

Solution 5

Here's a minor suggestion - this code:

Node* tempPtr = top;
top = new Node(value, tempPtr);

can be replaced with

top = new Node(value, top); 

unless you wanted the extra assignment statement to make the code more clear. If that's the case you could do this:

Node* oldTopPtr = top;
top = new Node(value, oldTopPtr);  

View more solutions

Comments

[jkeys]

Please define constructor initalizer lists. As for size, nice tip. As for assigning the ptr to NULL, I assumed crashing (or throwing an exception) would be a superior alternative to trying to access memory some other program is using. Also, once I correct the issue of size in the push function, couldn't I just use size to know if there is at least a single node in there? I actually do that in pop, but not peek. Is that not a good approach?

[jkeys]

Would you mind showing me exactly how to use a destructor in this case? Also, how can I write code to prevent people from leaking memory with future stacks, like in your third example?

[jkeys]

I added the destructor to the first post, thoughts welcome. My main problem with that is that I don't know when the destructor will get called, so how do I know what to write? I do NOT understand what a copy constructor really is, or what an assignment constructor is. Definitions of those should get me started. If I need more help, I'll ask. Btw: I don't know how returnTopPtr made the cut - my "grade code" (the final code) had that removed. He explained to me why it was a bad idea, too.

[jkeys]

Yes, I wanted it for clarity, but I suppose I chose a less than meaningful name to achieve that.

[josesuero]

Oof, those are probably too big topics for a comment. I added brief descriptions of how they should be implemented in my answer, but not in full detail. :)

[GManNickG]

I would suggest making a function called empty() that just returns true if the current node is NULL. Then your destructor will read better: while (!empty()) pop(). And pop() should do the pointer shuffling. Avoid duplicate code.

[josesuero]

agreed. Actually, my preferred solution would be to make Node a RAII class, at which point the Stack destructor would be trivial, and could be omitted entirely. But one step at a time. :)

[jkeys]

Also, what is the actual code of the copy and assignment constructors? Surely the definition alone isn't the necessary code. I don't see what is happening here.

[the_drow]

@Hooked: please google next time... en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization - RAII

[jkeys]

In your second example, shouldn't peek return exactly the end, and the same with pop?

[josesuero]

Ok, added explanations and code for everything, and I do mean everything. ;)

[jkeys]

In response to your last comment: Oh snap. =P Thank you. Now I need to read up on the use of this, const, and the & operator when talking about constructors. Thanks for the explanation! +1

[Steve Jessop]

I personally don't like recursive constructors and destructors. Sometimes you have collections which are bigger than the available stack space. RAII is usually the right way to handle resources, but for linked lists I think you have to ensure iterative copy and destructor.

[Faisal Vali]

+1 - but just wanted to add that your examples don't necessarily illustrate that C++ isn't a nice beginner's language (see one of my sample implementations (using vector) in my answer - which shows how simply one can implement a stack) - just that explicit memory management might not be for beginners (just as metaprogramming in ruby might not be for beginners) :)

[josesuero]

True, it can be done very simply using the STL. The reason it's not a nice beginners language is the ease with which you can create something that seems to work, but still contains many subtle bugs, like I illustrated. :)

[Steve Jessop]

The question really is, how realistic are the requirements? If you're a complete beginner to programming, it might be possible to learn C++ without ever attempting to write a class like this until you're experienced enough. Maybe. Problem is that if you approach C++ from any other programming language, you'll either attempt resource management and get it wrong (coming from C), or expect resources to magically get cleared up (coming from Java). Either way you could well end up trying to write classes like this.

[jkeys]

OK, this is kind of difficult to decipher. For instance, in pop, you delete thisnode - but it doesn't appear to be dynamic. How do you delete that?

[Steve Jessop]

"Where is the variable live?". It's in jalf's test code, which I didn't re-post here. Well spotted :-)

[Steve Jessop]

In pop, thisnode is dynamic. It was allocated in push (or during a copy), and stashed away in the SafeNode to ensure it would be deleted in the destructor. Then top.get() returns it. The line "top.node = thisnode->prev" removes thisnode from the list, so we have to delete it.

[andrewsi]

I'm not sure how this answers the question.