Menu
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;
}
517
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
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);
}
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 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;
}
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!
:)
196
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.
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
