Improved stack implementation using a linked list This is a followup to


Simple stack implementation using linked list


Since my original stack implementation has lots of bugs that I did not notice, I thought I would recreate and try to improve it. Please review this version.

Note about pointers: I know using std::unique_ptr is better so we don't need to do manual deletes, but when I tried it here it results in disaster. I think I don't yet know how to really use it. So I did not use it in this code.

template&lt;class T&gt;
struct Node {
    T item;
    Node* next;
    Node(const T&amp; t, Node* link) :item{t}, next{link} { }
};

template&lt;class T&gt;
class Stack {
public:
    Stack() : first{nullptr}, n{0} {}
    int size() const { return n; }
    bool empty() const { return n == 0; }
    Stack(const Stack&amp;);
    Stack(Stack&amp;&amp;);
    Stack&amp; operator=(const Stack&amp;);
    Stack&amp; operator=(Stack&amp;&amp;);
    void push(const T&amp;);
    void pop();
    T peek() const;
    ~Stack() {
        while (!empty()) {
            pop();
        }
    }
private:
    Node&lt;T&gt;* first;
    std::size_t n;
};

template&lt;class T&gt;
Stack&lt;T&gt;::Stack(const Stack&amp; s) :first{nullptr}, n{0}{
    for (auto t = s.first; t != nullptr; t = t-&gt;next) {
        push(t-&gt;item);
    }
}

template&lt;class T&gt;
Stack&lt;T&gt;&amp; Stack&lt;T&gt;::operator=(const Stack&amp; s) {
    for (auto t = s.first; t != nullptr; t = t-&gt;next) {
        push(t-&gt;item);
    }
    return *this;
}

template&lt;class T&gt;
Stack&lt;T&gt;::Stack(Stack&amp;&amp; s) :first{s.first}, n{s.n} {
    s.first = nullptr;
    s.n = 0;
}

template&lt;class T&gt;
Stack&lt;T&gt;&amp; Stack&lt;T&gt;::operator=(Stack&amp;&amp; s) {
    first = s.first;
    n = s.n;
    s.first = nullptr;
    s.n = 0;
    return *this;
}

template&lt;class T&gt;
void Stack&lt;T&gt;::push(const T&amp; t) {
    first = new Node&lt;T&gt;{t,first};
    ++n;
}

template&lt;class T&gt;
void Stack&lt;T&gt;::pop() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    Node&lt;T&gt;* oldfirst = first;
    first = first-&gt;next;
    delete oldfirst;
    --n;
}

template&lt;class T&gt;
T Stack&lt;T&gt;::peek() const {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    return first-&gt;item;
}


How can I make this code better, particularly copy and move?
Don't repeat code:

template&lt;class T&gt;
Stack&lt;T&gt;&amp; Stack&lt;T&gt;::operator=(const Stack&amp; s) {
    for (auto t = s.first; t != nullptr; t = t-&gt;next) {
        push(t-&gt;item);
    }
    return *this;
}


This is not really an assignment but an append. I think most people would not expect that. You should probably release the original list before copying over the source into this object.

An easier way to implement the assignment operator is to use the copy and swap idiom.

// Notice the pass by value creates an implicit copy.
// You then just swap the content of the current object
// with the parameter s.
// When the parameter goes out of scope it deletes the old
// data stack.
Stack&lt;T&gt;&amp; Stack&lt;T&gt;::operator=(Stack s) {
    std::swap(first,   s.first);
    std::swap(n,       s.n);
    return *this;
}


You move assignment leaks:

template&lt;class T&gt;
Stack&lt;T&gt;&amp; Stack&lt;T&gt;::operator=(Stack&amp;&amp; s) {
    first = s.first;
    n = s.n;
    s.first = nullptr;
    s.n = 0;
    return *this;
}


The current value of first is leaked. The best way to do this is to swap the content of this object with the incomming object.

template&lt;class T&gt;
Stack&lt;T&gt;&amp; Stack&lt;T&gt;::operator=(Stack&amp;&amp; s) {
    std::swap(first,   s.first);
    std::swap(n,       s.n);
    return *this;
}


Let the other object do the clean up when it goes out of scope.

You implemented a push by copy:

void push(const T&amp;);


Why not have a push by move:

void push(T&amp;&amp;);


I would make the Node structure a private implementation detail of stack. That way other people can not rely on that detail when they use your code.

template&lt;class T&gt;
class Stack {
     struct Node {....} 
};


Your peak creates a copy of the object.

   T Stack&lt;T&gt;::peek() const {
// ^ Return by value creates a copy.


I would return by reference. I would also rovide two version. One to return by const reference (for const version of the stack), and a normal return by reference so you can look at the top value and potentially alter it without removing it from the stack:

T const&amp; Stack&lt;T&gt;::peek() const { ....
T&amp;       Stack&lt;T&gt;::peek()       { ....


Your destructor checks empty() then calls pop() which checks empty(). This is a bit redundant. You could have a private version of pop that does not check empty.

~Stack() {
    while (!empty()) {
        noneCheckedPop();
    }

void Stack&lt;T&gt;::pop() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    noneCheckedPop();
}

private:
void Stack&lt;T&gt;::noneCheckedPop() {
    Node&lt;T&gt;* oldfirst = first;
    first = first-&gt;next;
    delete oldfirst;
    --n;
}