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

• vnp: Why are you so opposed to having a Node constructor?
• Snorrlaxxx: @vnp I am not at all, just not understanding why and how I would go about changing my code. More so the why factor, I would of course figure it out in terms of coding.

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).)

• Snorrlaxxx: Thank you for answer, really appreciate that you thought it was decent code. I have been teaching myself C++. I may have a few questions with what you said but I will have to get back to you tomorrow. Do you mind if I ask some questions in regards to your answer tomorrow?
• indi: Not at all, ask any time.
• Snorrlaxxx: Hi, sorry it took so long to comment, been busy with some stuff. My first question is pertaining to "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." Is there any where else I need to use the = default? I never heard of it before.
• Snorrlaxxx: Second, for the free swap() function, where should I include it? In public: somewhere? Also is a free swap function when you cast it as a friend?
• indi: I'll answer these questions by extending the answer above, because some of them take a bit of explaining that won't fit in a comment.

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.

• Snorrlaxxx: Thank you for your answer. I just have two questions. First, for the copy constructor part, do I just need to reverse the for loop so that is starts from the back? Second, using std::unique_ptr would I still need the rule of 5? It seems like I would not since it automatically destroys the objects.
• hoffmale: @Snorrlaxxx Re copy constructor: Going backwards through a singly linked list is not that easy (you'd need to somehow remember what came beforehand). It's easier to just keep track of where you need to insert the next node in the new stack. I'll add an example to the answer. // Re unique_ptr and Rule of 5: You'd still have a custom copy constructor/copy assignment operator, so Rule of 5 would recommend adding the other parts as well (even if it is = default). For a linked list I'd still recommend a manual cleanup in order to prevent stack overflow errors.
• hoffmale: @Snorrlaxxx: Also, I just noticed that you grouped the default constructor under // Rule of 5 instead of the copy assignment operator. Rule of 5 concerns itself with moving, copying and destroying objects.
• Snorrlaxxx: I see, I just said // Rule of 5 to show myself where all the constructors are. I know the rule of 5 concerns just the moving, copying and destroying of objects.
• Snorrlaxxx: Oh wait, I dont have the rule of 5 correct? I thought I did have a custom copy constructor/copy assignment operator.