C++ Stack implementation with linked-list

Question

It's proving difficult to find implementations of a Stack with linked list and Im trying to figure out if my implementation is correct/not missing anything obvious.

template <class T>
class Stack {
private:
 struct node {
 T data;
 node* next = nullptr;
 node(T data, node* next) : data(data), next(next) {};
 };
 node* top_ = nullptr;
public:
 Stack() {}
 Stack(T seed[], size_t len) {
 for(size_t i = 0; i < len; ++i) {
 Push(seed[i]);
 }
 }
 void Push(T value) {
 node* ele = new node { value, top_ };
 top_ = ele;
 }
 bool IsEmpty() {
 return top_ == nullptr;
 }
 T Peek() {
 if (IsEmpty())
 throw std::runtime_error("Stack is empty");
 return top_->data;
 }
 T Pop() {
 if (IsEmpty())
 throw std::runtime_error("Stack is empty");
 node* popped = top_;
 T result = popped->data;
 top_ = popped->next;
 delete popped;
 return result;
 }
};

My tests (sample basic ones below) do show working functionality as well, so its really just my code structure/procedures I'm worried about

int seed[3] { 5,4,3 };
Stack<int> stack { seed, 3 };
REQUIRE( stack.Pop() == 3 );
REQUIRE( stack.Pop() == 4 );
REQUIRE( stack.Pop() == 5 );
REQUIRE_THROWS_WITH( stack.Pop(), "Stack is empty" );
REQUIRE_NOTHROW( stack.Push(9) );
REQUIRE_NOTHROW( stack.Push(3) );
REQUIRE( stack.Peek() == 3 );
REQUIRE( stack.Pop() == 3 );

• yuri: Can you post the entire code so people are able to run it?
• J Livengood: This is basically it. I have the class above, and I have the test suite.
• Toby Speight: Is there a good reason you're reimplementing your own linked list? If so, you'll need to follow the Rule of Seven, if you can't follow the Rule of Zero, to manage your memory properly. A Valgrind run will show what I mean!
• Toby Speight: You'll receive better reviews if you show a complete example. For example, I recommend that you edit to show the necessary #include lines, and a main() that shows how to call your function. It can really help reviewers if they are able to compile and run your program.
• Jive Dadson: Linked lists are inefficient. The cache misses they cause can be disastrous. Nevertheless, new versions of C++ have singly linked lists in the standard library, called std::forward_list. If you really need a linked list, use that rather than rolling your own.

Answer 1

This is the archaic form of template declaration:

template <class T>

The more modern form is:

template<typename T>

Technically not difference but class implies user defined type while typename implies any type. Most modern libraries will use the newer version. There is also one obscure corner case template templates were it makes a difference.

You don't need to define a constructor for node.

 struct node {
 T data;
 node* next = nullptr;
 node(T data, node* next) : data(data), next(next) {};
 };

The initializer list contruct will have the same affect.

 struct node {
 T data;
 node* next;
 };
 ...
 new node {data, top};

Also I would use standard naming convention. User defined types start with an upper case letter while variables and methods start with a lower case letter. This helps you distinguish between object creation and function calls very easily.

You have missed the destructor. This means a non empty stack will leak all its members when it goes out of scope. So you should define a destructor to cleanup when the object is destoryed.

Now that you have a destructor:

You don't obey the rule of 3 or 5 (somebody else mentioned the rule of 7 but I don't know what that is, if somebody would like to clarify in the comments?).

Rule of 3: If you define a destructor, copy constructor or copy assignment then you probably need all three.

Rule of 5: Rule of 3 + the 2 move operators. Allows you define move operators for your object so that it is move compatible.

The alternative to using the Rule of 3/5 is to use the Rule of 0. This basically means the node object cleans itself up. This would require using std::unique_ptr. The top in your list and the next in the node would need to use this type.

Personally I don't think this is appropriate for building lists (but it is definitely an option and other people would recommend it).

You are passing by value here:

 void Push(T value)

This is fine for simple types of T. But if T is expensive to copy then you copy it to the Push method. Then you copy it again when you construct the object.

Try pushing by reference and moveable reference.

 void Push(T const& value); // Pass value by reference.
 void Push(T&& value); // Pass by r-value ref allowing a move.

This function does not change the state of the object.

 bool IsEmpty() {
 return top_ == nullptr;
 }

You should probably mark it as const. This allows you to pass the stack by const reference and still check the state of the object.

DRY you code.
The following code is repeated in two places

 if (IsEmpty())
 throw std::runtime_error("Stack is empty");

That means it is a candidate to be put into its own function.

You can not implement Pop() that returns a value in an exception safe manner. As such the standard stack uses two separate methods top() which returns a reference to the top value and pop() that returns void but removes the top item from the stack.

You should probably follow this convention.

These two functions return by value.

 T Peek()
 T Pop()

This means you make a copy of the value. This is fine for simple types like integer but for complex classes this is potentially expensive. Another reason to use top() and void pop(). But here at least Peek() should return a reference to avoid the copy.

• J Livengood: Absolutely great review, thank you so much for taking the time!

Answer 2

I don't know what other code you included to make this work but as it stands now it doesn't compile:

45:45: error: taking address of temporary array
 Stack<int> stack { (int []){ 5,4,3 }, 3 };

Your program also leaks memory. Run it through valgrind to check for leaks.
Manual memory managment via new is almost always a bad idea. Use smart pointers to avoid these problems.
Why do you provide an empty default ctor?

Provide the public part of your interface first.
When people look at your library they don't want to read through all the data members just to see which methods you expose. Method names are also usually kept lowercase.

The way you initalize things also looks strange. You use three different ways (direct, lists and constructor). Rework the code and stick to list initialization.

Formatting could use some work, everything is really glued together making this hard to read.
You should never omit braces {} as it can lead to hard to find errors.

I think the design could be cleaner. Interface and implementation could probably be less coupled but maybe someone else has a better explanation here.

• J Livengood: So I'm really wanted to know where/why its leaking if Im deleting where I believe I need to be. Also style guide adheres just to Google's C++ guide
• yuri: @JLivengood Styleguides are, as the name implies, merely a guideline and not an absolute directive. Regarding the memory leaks, ask yourself: what happens when your stack gets destroyed while it's not empty?
• J Livengood: Did not anticipate that, is it recommended in a destructor to iterate the linked list freeing the nodes?
• yuri: @JLivengood Unless you enjoy memory leaks, yes. The alternative is, as I pointed out, to use smart pointers.
• Loki Astari: @JLivengood You leak because a non empty stack does not destroy the list when it goes out of scope.