Generic Stack Data Structure Using Linked Lists Follow Up

Question

I made a post that follows from this here. I made most of changes that I could understand from the following link, and here is now an update to that original post. I just want to see if there is any major changes that I need to consider making and perhaps to gain some more insight into how to achieve making those changes.

Here is the header file:

#ifndef Stack_h
#define Stack_h

template <class T>
class Stack {
private:
    struct Node {
        T data;
        Node* next;
    };
    Node* _top;

    // Used for destructor to delete elements
    void do_unchecked_pop();

    // Use for debugging purposes and for overloading the << operator
    void show(std::ostream &str) const;


public:
    // Rule of 5
    Stack() : _top(nullptr){}                                                 // empty constructor
    Stack<T>(Stack<T> const& value);                                          // copy constructor
    Stack<T>(Stack<T>&& move) noexcept;                                       // move constuctor
    Stack<T>& operator=(Stack&& move) noexcept;                               // move assignment operator
    ~Stack();                                                                 // destructor

    // Overload operators
    Stack& operator=(Stack const& rhs);
    friend std::ostream& operator<<(std::ostream& str, Stack<T> const& data) {
        data.show(str);
        return str;
    }

    // Member functions
    void swap(Stack& other) noexcept;
    bool empty() const;
    int size() const;
    void push(const T& theData);
    void push(T&& theData);
    T& top() const;
    void pop();

};

template <class T>
Stack<T>::Stack(Stack<T> const& value) : _top(nullptr) {
    for(Node* loop = value._top; loop != nullptr; loop = loop->next) {
        push(loop->data);
    }
}

template <class T>
Stack<T>::Stack(Stack<T>&& move) noexcept : _top(nullptr) {
    move.swap(*this);
}

template <class T>
Stack<T>& Stack<T>::operator=(Stack<T> &&move) noexcept {
    move.swap(*this);
    return *this;
}

template <class T>
Stack<T>::~Stack() {
    while(_top != nullptr) {
        do_unchecked_pop();
    }
}

template <class T>
Stack<T>& Stack<T>::operator=(Stack const& rhs) {
    Stack copy(rhs);
    swap(copy);
    return *this;
}


template <class T>
void Stack<T>::swap(Stack<T> &other) noexcept {
    using std::swap;
    swap(_top,other.top);
}

template <class T>
bool Stack<T>::empty() const {
    return _top == nullptr;
}

template <class T>
int Stack<T>::size() const {
    int size = 0;
    Node* current = _top;
    while(current != nullptr) {
        size++;
        current = current->next;
    }
    return size;
}

template <class T>
void Stack<T>::push(const T &theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    newNode->next = nullptr;

    if(_top != nullptr) {
        newNode->next = _top;
    }
    _top = newNode;
}

template <class T>
void Stack<T>::push(T&& theData) {
    Node* newNode = new Node;
    newNode->data = std::move(theData);
    newNode->next = nullptr;

    if(_top != nullptr) {
        newNode->next = _top;
    }
    _top = newNode;
}

template <class T>
T& Stack<T>::top() const {
    return _top->data;
}

template <class T>
void Stack<T>::do_unchecked_pop() {
    Node* tmp = _top->next;
    delete _top;
    _top = tmp;
}

template <class T>
void Stack<T>::pop() {
    if(_top == nullptr) {
        throw std::invalid_argument("the Stack is empty!");
    }
    do_unchecked_pop();
}

template <class T>
void Stack<T>::show(std::ostream &str) const {
    for(Node* loop = _top; loop != nullptr; loop = loop->next) {
        str << loop->data << "\t";
    }
    str << "\n";
}


#endif /* Stack_h */

Here is the main.cpp file that tests the latter:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <ostream>
#include "Stack.h"

int main(int argc, const char * argv[]) {



    ///////////////////////////////////////////////////////////////////////////////////
    ///////////////////////////// Stack Using Linked List //////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////////

    Stack<int> obj;
    obj.push(2);
    obj.push(4);
    obj.push(6);
    obj.push(8);
    obj.push(10);
    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Displaying Stack Contents---------------";
    std::cout<<"\n--------------------------------------------------\n";
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Pop Stack Element -------------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.pop();
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Get the size of stack -------------------";
    std::cout<<"\n--------------------------------------------------\n";
    std::cout << obj.size() << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Re-Add Poped Element---------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.push(10);
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Print top element --------------------";
    std::cout<<"\n--------------------------------------------------\n";
    std::cout << obj.top() << std::endl;

    return 0;
}

Answer 1

((Note: the code changed while I was writing this review, so it might not match exactly.))

Pretty decent code! There are only a few trouble spots.

I'd start by suggesting that you add the necessary includes to the header file. For example, the class needs std::ostream for the insertion operator, so you should #include <iosfwd>. And so on for all the other standard library stuff you need. (Your code only works for now because main.cpp includes headers that satisfy all the requirements before including Stack.h.)

struct Node {
    T data;
    Node* next;
};
Node* _top;

You should take advantage of in-class initializers - it will simplify the code, and make it safer. In this case, both next and _top could have = nullptr.

I see comments suggesting you add a constructor to Node, but you don't need one. I wouldn't bother with it.

Stack() : _top(nullptr){}

You should always prefer to use = default rather than {} when defining things that can be implicitly generated, and the implicitly generated versions do the right thing. If you also use an in-class initializer to define Node* _top = nullptr;, then this becomes:

Stack() = default;

And you can even add constexpr and noexcept.

Speaking of noexcept, there are a couple of other places it might be applicable - at the very least empty() and size() seem like no-fail functions. You can probably make a fair bit of it constexpr, too, but that's less important because Stack doesn't seem like a compile-time type.

Stack<T>(Stack<T> const& value);

You don't really need the <T>s inside the class body. And you shouldn't include them, because it may cause headaches if you change the template parameters.

template <class T>
Stack<T>::Stack(Stack<T> const& value) : _top(nullptr) {
    for(Node* loop = value._top; loop != nullptr; loop = loop->next) {
        push(loop->data);
    }
}

This function will leak memory if it fails. Imagine what would happen if you were copying a 100 element stack, and push() failed on element 99. All those other nodes would never be deallocated.

If you're not going to use smart pointers (which makes sense in this context), then you'll need to use an explicit try-catch, maybe something like this:

template <class T>
Stack<T>::Stack(Stack<T> const& value) {
    try {
        for(auto loop = value._top; loop != nullptr; loop = loop->next)
            push(loop->data);
    }
    catch (...) {
        while(_top != nullptr)
            do_unchecked_pop();
        throw;
    }
}

Moving on down:

template <class T>
void Stack<T>::swap(Stack<T> &other) noexcept {
    using std::swap;
    swap(_top,other.top);
}

There appears to be a typo here - it should probably be other._top. If you're going to define a swap() member function, you might as well define a free swap() function as well.

template <class T>
int Stack<T>::size() const {
    int size = 0;
    Node* current = _top;
    while(current != nullptr) {
        size++;
        current = current->next;
    }
    return size;
}

You can simplify this quite a bit with a for loop:

template <class T>
int Stack<T>::size() const {
    int size = 0;
    for (auto curent = _top; current != nullptr; current = current->next)
        size++;
    return size;
}

On to the push() functions:

template <class T>
void Stack<T>::push(const T &theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    newNode->next = nullptr;

    if(_top != nullptr) {
        newNode->next = _top;
    }
    _top = newNode;
}

In this function, you create a Node with data default constructed, and then copy theData. That is inefficient, and may even not work for types that don't have a default constructor. Instead you should do:

template <class T>
void Stack<T>::push(const T &theData) {
    auto newNode = new Node{theData};

    if(_top != nullptr) {
        newNode->next = _top;
    }
    _top = newNode;
}

If you aren't going to use an in-class initializer for Node::next, then you'll need to write: auto newNode = new Node{theData, nullptr};.

Same idea for push(T&&).

template <class T>
T& Stack<T>::top() const {
    return _top->data;
}

If the stack is empty, this function will cause undefined behaviour (likely just a crash). That's not wrong, but if it is what you intend, you should document it, at the very least with a comment:

template <class T>
// expects !this->empty()
T& Stack<T>::top() const {
    return _top->data;
}

In C++20 you can use contracts:

template <class T>
T& Stack<T>::top() const
    [[ expects: !empty() ]]
{
    return _top->data;
}

But whatever you use, you really should document your code's behaviour and requirements.

template <class T>
void Stack<T>::pop() {
    if(_top == nullptr) {
        throw std::invalid_argument("the Stack is empty!");
    }
    do_unchecked_pop();
}

I'm not sure invalid_argument makes sense here... particularly given that there's no argument. This smells more like a job for out_of_range.

Summary

• Add the necessary includes for the standard library facilities you use.
• Use in-class initializers for members that have sensible defaults. (Like pointers should almost always be set to nullptr.
• Mark all no-fail functions noexcept.
• Handle exceptions in the copy constructor - don't leak memory.
• Don't double-constructor your nodes; don't default construct Node::data then move/copy assign to it. Construct node data in place.
• Use more comments to document your code's intentions.

Answers to questions

Apologies if some of this stuff is obvious to you - it's hard to gauge how much someone already knows. And anyway, even if it's obvious to you, it might help someone else reading this.

Defaulted operations

There are a number of operations that the compiler generates for you implicitly. That includes the default constructor, the destructor, copy/move operations, and so on. Most of the time, you don't need to write anything at all. For example, if you do:

struct Foo {};

Foo f;

Foo will automatically have a default constructor, a destructor, and so on.

But sometimes you do something that suppresses the implicitly generated stuff. For example, any time you add a constructor to a class, it suppresses the default constructor.

struct Foo
{
    Foo(int) {}
};

Foo f; // won't compile, no default constructor

Because Foo has a constructor defined, the default constructor is suppressed.

If you want the default constructor back, you have to specifically request it:

struct Foo
{
    Foo(int) {}
    Foo() = default;
};

Foo f; // will compile

The = default just tells the compiler: "That function that you were going to generate until I did something to suppress it? Generate it anyway."

You could write Foo() {} instead of Foo() = default;, because that's basically what the compiler is going to do anyway. But there's an important difference:

• Foo() {} is NOT an implicitly-generated default constructor... it's a user-defined default constructor that just happens to do the same thing as the implicitly-generated default constructor.
• Foo() = default; IS an implicitly-generated default constructor.

They both do the same thing, but when a default constructor is actually compiler-generated, the compiler can do a lot more optimizing with it. So you (pretty much) always want to use Foo() = default;, and not Foo() {}.

So the question is: Where do you need to use it?

The answer is: Anywhere that an implicitly-generated function works for you, but it's somehow been suppressed.

In Stack, the default constructor works for you (once you use an in-class intiializer for _top to set it to nullptr). But it gets suppressed when you define the copy/move constructors. So you need = default to get it back again.

None of the other implicitly-generated functions work for you in Stack unfortunately, because of the rule of 5. You need a custom destructor and copy/move ops, so you can't just = default them.

Free swap

The reason why you generally want a non-member swap function is because (as you know) the proper way to do a swap in C++ is this:

using std::swap;
swap(a, b);

That uses argument-dependent lookup to dispatch to the correct swap function.

So if I do:

namespace indi {

struct Foo {};
void swap(Foo&, Foo&);

struct Bar {};

} // namespace indi

then:

using std::swap;

int i1, i2;
swap(i1, i2); // calls std::swap

indi::Foo f1, f2;
swap(f1, f2); // calls indi::swap

indi::Bar b1, b2;
swap(b1, b2); // calls std::swap

You can see that std::swap() gets used normally... but when there's a custom swap function, like for Foo, that gets used instead. The custom swap function must be in the same namespace as the class for this to work.

If your class is swappable, and you need a custom swap function, then you should almost always define a free swap function in the same namespace as your class. That allows a more efficient custom swap to be used when swapping is done correctly.

If you don't define a free swap function for Stack, then:

using std::swap;

Stack<int> s1, s2;
swap(s1, s2); // calls std::swap

will "work", because Stack is movable (which is all that std::swap() requires). But it will create a temporary Stack object and do three moves. Bit of a waste of time.

However, if you define:

template <typename T>
void swap(Stack<T>& a, Stack<T>& b) noexcept
{
    a.swap(b);
}

and put it in the same namespace that Stack is in, then:

using std::swap;

Stack<int> s1, s2;
swap(s1, s2); // now calls your custom swap (which does s1.swap(s2))

No temporary Stack objects get created, and the swap gets done as efficiently as possible.

In the case of Stack, you don't need to make the free swap function a friend, because it can just call the swap() member function, which is public:

template <typename T>
class Stack
{
public:
    void swap(Stack& other) noexcept;

    // ...
};

// Member function
template <typename T>
void Stack<T>::swap(Stack<T>& other) noexcept
{
    using std::swap;
    swap(_top, other._top);
}

// Free function
template <typename T>
void swap(Stack<T>& a, Stack<T>& b) noexcept
{
    a.swap(b);
}

That's cool. (Incidentally, as of C++20, both of those functions can also be constexpr! You could make them both constexpr before C++20 if you do the swap manually, without std::swap(). Whether that's worth it is up to you.)

However, if you didn't need a swap() member function, and you couldn't do the swap without access to hidden members, then you could make your free swap function a friend. But in Stack's case, it's not necessary.

So the general rule is: If your type has a custom swap operation, define a free swap() function in the same namespace as the type.

(And since you almost always have to make a custom swap operation for any non-trivial type - if only so you can do moves properly, and use copy-and-swap for copying - you should almost always have a free swap() function for a class... even if all it does is call a member swap() function (as in Stack's case).)

Answer 2

Just adding to @indis answer.

Copy constructor

The new, copied stack gets created in reverse. The object of was at the top of the old stack is now at the bottom of the stack of the copy.

Here a detailed look at how the copy gets constructed:

original stack             copy
[ 1, 2, 3, 4, 5 ]          []
  ^

First, the top element of the original stack gets selected and pushed onto the new one.

[ 1, 2, 3, 4, 5 ]          [ 1 ]
     ^

Then, the next one gets selected and pushed onto the new stack.

[ 1, 2, 3, 4, 5 ]          [ 2, 1 ]
        ^

Wait, what happened? push inserted 2 at the front of the new stack. While this is usually the expected behavior of push, this isn't actually wanted here. To create a copy, the elements need be inserted at the back of the linked list, not the front.

So, how to fix this:

template <class T>
Stack<T>::Stack(Stack<T> const& value) : _top(nullptr) {
    // get the address of where the next node will be inserted
    auto insert_pos = &_top;

    for(auto loop = value._top; loop != nullptr; loop = loop->next) {
        // create new node
        auto copy_node = new node(loop->data);
        // insert node
        *insert_pos = copy_node;
        // save the next insertion address
        insert_pos = &copy_node->next;
    }
}

const correctness

top returns a mutable reference while the stack itself is const, i.e. . This allows the modification of the internal state of a const object. Not good!

This can be fixed by removing the const, so the mutable reference only gets returned if the stack itself is mutable.

However, now the top element of a const stack can no longer be accessed. To fix this, we need a new overload of top for a const stack, that returns a const T& (to prevent modification).

So we get the final member function signatures

T& top();
const T& top() const;

Memory management

I'd highly suggest you have a look at std::unique_ptr. While the implementation mostly keeps track of object lifetimes, it still doesn't handle all cases (like the memory leak in the copy constructor in case of an exception).

Using std::unique_ptr would help there, automatically destroying those objects. It would also simplify the pointer managing code a bit.

While smart pointers don't have to be used everywhere, they are a very important tool in the C++ toolbox. Especially if you are new to C++, try them out and add them to your repertoire, since they help to prevent so many bugs.