Typed Stack Implementation in C++

[flux00]

Hello, I can't seem to correctly implement a typed stack class in c++. For some reason I never push anything back, there are many nodes, but they all contain the same value, always the last value I push in.

main.cpp:

#include <iostream>
#include "data/stack.h"
using namespace std;
int main()
{
Stack<double> st = Stack<double>();
for (int i=10; i>=0; --i)
{
double t = (double)(i)+0.5;
st.push(t);
}
while (st.length() > 0)
{
cout << st.pop() << endl;
}
return 0;
}


stack.h:

#ifndef STACK_H_
#define STACK_H_
#include <iostream>
template <class Type>
class Node
{
public:
Node<Type>* next;
Type& value;
Node(Type& v, Node<Type>* n) : value(v), next(n) {}
~Node()
{
delete next;
}
};
template <class Type>
class Stack
{
private:
Node<Type>* root;
unsigned int l;
public:
Stack()
{
root = 0;
l = 0;
}
~Stack()
{
delete root;
}
unsigned int length()
{
return l;
}
void push(Type& t)
{
root = new Node<Type>(t, root);
++l;
}
Type& pop()
{
Type& r = root->value;
Node<Type>* t = root;
root = root->next;
t->next = 0;
delete t;
--l;
return r;
}
Type& peek()
{
return root->value;
}
};
#endif


output:

0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5

[Moulinex]

This is because you are storing references to Type in you Node.
After the push loop, all nodes in your stack reference t which was setted to 0.5 for the last push.

A quick fix is to store values instead of references in your nodes and to also pop values:


template <class Type>
class Node
{
public:
Node<Type>* next;
Type value;
Node(Type& v, Node<Type>* n) : value(v), next(n) {}
~Node()
{
delete next;
}
};
...
...
Type pop()
{
Type r = root->value;
Node<Type>* t = root;
root = root->next;
t->next = 0;
delete t;
--l;
return r;
}
...


This should do the trick. :yes:

Regards,
Moulinex

[flux00]

Hmm, but what if I wanted to store more complex things in the stack, doesn't that copy whatever I try to store in it?

[Reedbeta]

Then you should make the stack hold pointers to the objects, by passing a pointer type as the template parameter:

class BigComplicatedThing;
Stack<BigComplicatedThing *> mystack;

[dave_]

Or make sure they have a copy constructor/assignment operator. You're doing a copy in your Pop method anyway so I dont see why you needed the ref.

[.oisyn]

Hmm, but what if I wanted to store more complex things in the stack, doesn't that copy whatever I try to store in it?

Either you want to store references and you have to make sure the actual object outlives the node in which it is stored (in which case your test-case is flawed - you store a reference to a local object 't' that goes out of scope each iteration, reading from that reference afterwards is undefined behaviour so anything could happen, including a format of your harddrive, so consider yourself lucky ;)), or you want the stack to manage the allocations of the objects you store in it, in which case you'll need to make a copy.

The latter usage is the one used by almost anyone in the industry, since it allows both methods - if you want to store a reference, just put (smart)pointers in the container to keep track of your objects.

Or make sure they have a copy constructor/assignment operator. You're doing a copy in your Pop method anyway so I dont see why you needed the ref.
He's not doing a copy, he's storing the reference from the node->value in another local reference before deleting the node, and then returning that reference. And they all still reference the same object that was used during the push :) (Or where you perhaps mistakenly looking at Moulinex' code example?)

[dave_]

(Or where you perhaps mistakenly looking at Moulinex' code example?)
Whoops yes.

[flux00]

Ah ha! that makes perfect sense, thank you.

Edit: Just another quick question it's ok to delete a null pointer right? I've read different things online.

[Reedbeta]

Yes, IIRC, deleting a null pointer is defined to have no effect by the C++ standard. (But I'm sure .oisyn will chime in here! :))

[Jare]

deleting NULL pointers is safe, in the sense that the destructor will NOT be called with a NULL 'this' pointer.

However, if you define your own delete operators, they MAY be called with a NULL pointer after the destructor call is safely skipped. Remember that when you delete a pointer, the compiler silently inserts a call to the destructor before actually calling the operator delete.

Visual Studio 2005 for example seems to call the delete operator with a NULL pointer for classes that do NOT have a destructor. The likely reason is that when there is a destructor, the pointer needs to be checked BEFORE calling the destructor, and the compiler uses that check to skip the operator delete call as well. However, if there is no destructor, there is no need to place a check, and the operator delete call is inserted directly.

To sum it up, if you define your own operators for new and delete, make sure that the delete ones safely accept NULL pointers.
#include <stdio.h>
#include <stdlib.h>

void* operator new(size_t s) { printf("new(%d)\n", s); return malloc(s); }
void operator delete(void *p) { printf("delete(0x%p)\n", p); free(p); }

struct A
{
A() { puts("A::A"); }
~A() { puts("A::~A"); }
};

struct B
{
B() { puts("B::B"); }
~B() { puts("B::~B"); }
void* operator new(size_t s) { printf("B::new(%d)\n", s); return malloc(s); }
void operator delete(void *p) { printf("B::delete(0x%p)\n", p); free(p); }
};

struct C
{
void* operator new(size_t s) { printf("C::new(%d)\n", s); return malloc(s); }
void operator delete(void *p) { printf("C::delete(0x%p)\n", p); free(p); }
};

void main()
{
char *p = new char;
delete p;
p = 0;
delete p;

A *a = new A;
delete a;
a = 0;
delete a;

B *b = new B;
delete b;
b = 0;
delete b;

C *c = new C;
delete c;
c = 0;
delete c;
}
Output:
new(1)
delete(0x00811A28)
delete(0x00000000)
new(1)
A::A
A::~A
delete(0x00811A28)
B::new(1)
B::B
B::~B
B::delete(0x00811A28)
C::new(1)
C::delete(0x00811A28)
C::delete(0x00000000)

[.oisyn]

I wonder VC++ is in error here. The standard explicitely says that a delete expression on a null pointer has no effect (5.3.5/2). Surely, if it calls a user-defined operator delete() it can have effect, as the standard does not say how a user-defined operator delete() should handle a null pointer. It only specifies that the standard library implementation for operator delete() called with a null pointer has no effect (3.7.3.2/3 and 18.4.1.1/13).