5
\$\begingroup\$

I am learning C++ and I made a simple stack class using a (reversed) linked-list to test my knowledge.

Are there any problems with the following code, or any suggestions to improve it?

I want to make sure I am getting things correct in the beginning so I don't make the same mistakes again in the future - especially memory management and avoiding leaks.

One thing to point out is that I included the implementation in the header file... I wouldn't normally do this but apparently there are problems when implementing methods with templates in .cpp files.

#ifndef TEST_STACK_H
#define TEST_STACK_H

#include <stdexcept>

template <class T>
class stack {

    struct node {
        T data;
        node* previous;

        node(T data, node *previous) : data(data), previous(previous) {}
    };

    node* head = nullptr;

    int size = 0;
    int max = -1; // -1 so isFull() == false when default constructor used

public:
    stack() = default;

    stack(int max) {
        if (max <= 0) throw std::out_of_range("stack size must be > 0");
        this->max = max;
    }

    ~stack() {
        node* n = head;

        while (n != nullptr) {
            node* previous = n->previous;
            delete n;

            n = previous;
        }
    }

    void push(const T &object) {
        if (isFull()) throw std::overflow_error("cannot push to a full stack");

        head = new node(object, head);
        ++size;
    }

    T pop() {
        if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

        T item = head->data;
        head = head->previous;

        --size;

        delete head;
        return item;
    }

    T peek() {
        if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");
        return head->data;
    }

    int getSize() {
        return size;
    }

    bool isFull() {
        return size == max;
    }

    bool isEmpty() {
        return head == nullptr;
    }
};

#endif
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Jan 18 at 21:57
4
\$\begingroup\$

Bug

Your main issue is memory management.

You did not implement the "Rule of Three" (you can google it).

The problem is that if you do not define the copy constructor or the assignment operator the compiler will generate these methods for you automatically. Under most conditions these generated methods work correctly. BUT when your class contains an "Owned" pointer they do not work.

Note: An "Owned" pointer is a pointer you are responsible for deleting.

{
    stack<int>   x;
    x.push(12);


    stack<int>   y(x);  // Copy constructor used.
                        // The default implementation does a shallow copy
                        // of each member from x into y.
                        // This means that x and y point at the same list.

}
// Here your destructor has destroyed the same list twice.
// This is a bug.

To fix this you need to define the copy constructor and assignment operator. But there is a nice pattern that allows you to define the assignment operator in terms of the copy constructor. Look up the "Copy And Swap Idiom".

You need to add the following to your class:

class stack
{
    // Stuff
    public:
        stack(stack const& rhs)
            : head(copyList(rhs.head))
            , size(rhs.size)
            , max(rhs.size)
        {}
        stack& operator=(stack const& rhs)
        {
            stack tmp(rhs);            // make a copy using copy constructor.
            swap(tmp);                 // swap the tmp and this object
            return *this;
        }
        void swap(stack& other) noexcept
        {
            using std::swap;
            swap(head, other.head);
            swap(size, other.size);
            swap(max,  other.max);
        }

    private:
        node* copyList(node* l)
        {
            if (l == nullptr) {
                return null;
            }
            return new node{l->data, copyList(l->previous)};
        }
    // STUFF
};

Your pop() has a bug. You delete the NEW head item before returning but leak the original head item.

T pop() {
    if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

    T item = head->data;
    head = head->previous;     // You just leaked the old head.
                               // You need to keep a pointer to the old head

    --size;

    delete head;               // So you can delete the old head here.
    return item;
}

Other Stuff

Design of pop()

You make your pop() method return the top value and remove it from the stack. This is fine if your T type is simple. But if T is a complex type there is no way to do this safely (and maintain "Strong Exception Guarantee"). So most implementations of stack split this into two separate functions. A top() that returns the top value and a pop() that simply removes the top value.

So I would rewrite this:

void pop() {
    if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

    node* old = head;
    head = head->previous;

    --size;
    delete old;
}
T const& top() {
    if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

    return head->data;
}

Return by reference

Your pop() and peek() return the result by value. This is OK for simple types of T (like integer). But if T is a complex object you are making a copy of this complex object. Instead you should return a reference to the object. If the user is doing somehting simple they can do the action without copying if they want to keep a copy they can make that decision and save the value in a local variable.

T peek()

// Change to:

T const& peek();   // Don't really need this if you have top()
                   // Or you could use peek instead of top()

But notice the const& as the return type. You are returning a reference to the object so no copy is made. If you need a local copy then you can save it like this:

int   val = x.top();
x.pop();
\$\endgroup\$
  • \$\begingroup\$ Thanks for the guidance. One thing I was confused about was where you commented 'You just leaked the old head.' head->previous is a pointer to the next head (the name for previous comes from the order of the item placement in the stack rather than the order of retrieval in the linked list). So by assigning a pointer and then deleting the old head (which the new head has no relation to) should have no problem right? Another thing I was unsure of is how to get around returning T by value in pop(). I understand how to do it in peek, and I am not sure why I forgot to return by reference but... \$\endgroup\$ – Samueljh1 Jan 18 at 9:20
  • \$\begingroup\$ In pop, how can we return a reference to something we are about to delete? This is why I returned by value in this situation to avoid returning back a dangling pointer. \$\endgroup\$ – Samueljh1 Jan 18 at 9:21
  • \$\begingroup\$ @Samueljh1 When you go head = head->previous; what happens to the old value of head. You no longer have a reference to the old value and thus it is leaked. \$\endgroup\$ – Martin York Jan 18 at 17:04
  • \$\begingroup\$ @Samueljh1 When you do delete head; in pop() you are calling delete on the current head of the list. Which makes no sense. \$\endgroup\$ – Martin York Jan 18 at 17:06
  • \$\begingroup\$ In your version of pop() you have to return by value. But I would change that so that pop() does not return anything. It just removes the top element from the stack. You can not implement pop() that returns a value and provide the "Strong Exception Guarantee". Separate the functionality into two functions. pop() simply removes the top value and peek() returns a reference to the top value. \$\endgroup\$ – Martin York Jan 18 at 17:08
0
\$\begingroup\$

Updated Code

Changes (with the help of Martin):

  • Added copy constructor and assignment operator overload
  • Changed return type of peek() to const T& rather than T (this prevents unnecessary copying of data)
  • Changed return type of pop() to void; it now only removes the top item rather than returning it on top. The user can call peek() and then call pop() to retrieve and then delete the item. This means we don't have to return T by value, and also maintains the "Strong Exception Guarantee".
  • Fixed a bug in pop() where the new head is deleted rather than the old one
#ifndef TEST_STACK_H
#define TEST_STACK_H

#include <stdexcept>

template <class T>
class stack {

    struct node {
        T data;
        node* previous;

        node(T data, node *previous) : data(data), previous(previous) {}
    };

    node* head = nullptr;

    int size = 0;
    int max = -1; // -1 so isFull() == false when default constructor used

public:
    stack() = default;

    stack(int max) {
        if (max <= 0) throw std::out_of_range("stack size must be > 0");
        this->max = max;
    }

    // copy constructor

    stack(stack const& rhs) :
        head(copyList(rhs.head)),
        size(rhs.size),
        max(rhs.size) {}

    // assignment operator

    stack& operator = (stack const& rhs)
    {
        stack tmp(rhs);
        swap(tmp);

        return *this;
    }

    ~stack() {
        node* n = head;

        while (n != nullptr) {
            node* previous = n->previous;
            delete n;

            n = previous;
        }
    }

    void push(const T &object) {
        if (isFull()) throw std::overflow_error("cannot push to a full stack");

        head = new node(object, head);
        ++size;
    }

    const void pop() {
        if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

        node* old = head;
        head = head->previous;

        --size;
        delete old;
    }

    T peek() {
        if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");
        return head->data;
    }

    int getSize() {
        return size;
    }

    bool isFull() {
        return size == max;
    }

    bool isEmpty() {
        return head == nullptr;
    }

private:
    void swap(stack& other) noexcept
    {
        using std::swap;
        swap(head, other.head);
        swap(size, other.size);
        swap(max,  other.max);
    }

    node* copyList(node* l)
    {
        if (l == nullptr) {
            return nullptr;
        }
        return new node{l->data, copyList(l->previous)};
    }
};

#endif
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.