Brtdku

The original question can be seen here: Stack implementation in C++ using linked list

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;

    }



    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 nullptr;

        }

        return new node{l->data, copyList(l->previous)};

    }

};



#endif

#include <stdexcept>

And either <utility> or <algorithm>, for std::swap.

stack(int max) {

I very strongly recommend you make this constructor explicit. Right now it's a non-explicit (implicit) conversion, which means you're permitting your users to convert integers to stacks implicitly:

void foo(stack<int> s);

void bar() {

    foo(42);  // compiles and calls foo with stack<int>(42)

}

The general rule (at least for user codebases) is "make everything explicit unless you have some specific reason that it needs to be implicit." So you should make your node constructor explicit as well.

(I say "at least for user codebases" because the STL itself doesn't follow that principle — partly because the principle wasn't understood in 1998, and partly due to differences of opinion among the authors. "STL style" would be to make stack(int) explicit because it's a one-argument constructor, but leave all zero- and two-argument constructors implicit. I recommend against doing that.)

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

This comment doesn't help me understand. I would understand INT_MAX, but -1 just looks like it's breaking the class invariant enforced by the one-argument constructor:

if (max <= 0) throw std::out_of_range("stack size must be > 0");

Looking at these two lines in isolation, actually, I briefly wondered "wait, doesn't that always throw? You don't initialize max before that if, so it would have its default value, which is less than zero..." But then I realized that the name max here is overloaded: the max in the if statement is testing the function parameter, not the data member.

To eliminate confusion about name overloading, I strongly recommend that you sigil each of your data members with a trailing underscore: max_, size_, head_.
Then you don't have to write this-> when you access a member:

this->max = max;

can become just

max_ = max;

You don't need the disambiguating this->, because there's no confusion anymore about which max/max_ you mean.

stack(stack const& rhs) :

    head(copyList(rhs.head)),

    size(rhs.size),

    max(rhs.size) {}

Do you see the typo?

Write some unit tests for your code! In particular, now that you've spotted a bug, write a unit test that would have caught this bug and commit it as part of the bugfix. That's called a "regression test."

stack& operator = (stack const& rhs)

{

    stack tmp(rhs);

    swap(tmp);



    return *this;

}

FYI, the copy-and-swap idiom can be written more concisely if you want to:

stack& operator=(stack const& rhs)

{

    stack(rhs).swap(*this);

    return *this;

}

const void pop() {

The const here is useless; remove it. (I wonder if it was a mistake for something similar — void pop() const? constexpr void pop()? but neither of those makes sense either.)

T peek() {

OTOH, this method should be const:

T peek() const {

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

    return std::as_const(head->data);

}

I threw in an as_const just to illustrate complete paranoia. We don't know what type T is, right? So when you construct the return value T, which constructor do you want to call — T(T&) or T(const T&)? Write a unit test for a type T where it makes a difference, and see what happens.

getSize(), isFull(), and isEmpty() should all be const methods as well.

void swap(stack& other) noexcept

Good! You also do the using std::swap; dance correctly — although, since you're not swapping anything but ints and pointers, the dance is unnecessary in this case, but hey it's good practice.

You did forget, though, that if you want the using std::swap; dance to work for anyone else who uses your stack class, you'll need to provide that free ADL function swap. So we add an inline friend:

friend void swap(stack& a, stack& b) noexcept {

    a.swap(b);

}

Now

using std::swap;

swap(redstack, bluestack);

will be as efficient as possible.

Consider adding move semantics to your class — stack(stack&&) noexcept, stack& operator=(stack&&) noexcept, void push(T&&) (or just void push(T) at that point). I assume you left them out on purpose for this simple example.

Your copyList is recursive. This could blow your stack if you're copying a very long list. You successfully eliminated the recursion from your destructor — why not eliminate it here too?

node* copyList(node* l)

Since this member function doesn't need the this pointer for anything, it should be marked static. And it wouldn't hurt to add const to the node you don't intend to modify, just for a tiny bit of self-documentation:

static node *copyList(const node *l)