Implementing a Stack with Templates and Smart pointers

Question

I'm trying to understand the concepts of smart pointers and templates. To get a better understanding of these, I tried to implement these two concepts on Stack. I have created a Stack which can hold objects of any type. For dynamic memory allocation, I have used smart pointers.

Please suggest how I could improve the code. Am I missing any cases while using smart pointers and templates? Since I'm using smart pointers, can I rest assure that free store (heap) memory will be deleted once the Stack variable goes out of scope?

#include "stdafx.h"
#include<iostream>
#include<string>
#include<memory>
using namespace std;
// Template Node
template <typename T>
struct Node
{
 T data;
 shared_ptr<Node> next;
 Node(T d, shared_ptr<Node> n) : data(d), next(n) {}
};
// Template Stack
// Note: T type is used to set the Node type
template <typename T>
class Stack {
private:
 shared_ptr<Node<T>> head;
public:
 Stack() : head(NULL) {}
 Stack(const Stack<T> &rhs) = delete;
 Stack& operator=(const Stack<T> &rhs) = delete;
 void push(const T&);
 void pop();
 T top() const;
 void print() const;
};
// Notice <T> after the class name, it is the syntax requirement
template <typename T>
void Stack<T>::push(const T &data) {
 shared_ptr<Node<T>> temp = make_shared<Node<T>>(data,nullptr);
 if (head == nullptr) {
 head = temp;
 }
 else {
 temp->next = head;
 head = temp;
 }
}
template <typename T>
void Stack<T>::pop() {
 //shared_ptr<Node<T>> temp = head;
 head = head->next;
}
template <typename T>
T Stack<T>::top() const {
 return head->data;
}
template <typename T>
void Stack<T>::print() const {
 // shared_ptr<Node<T>> temp;
 for (auto temp = head; temp != nullptr; temp = temp->next)
 cout << temp->data << '\n';
}
int main()
{
 cout << "String data" << '\n';
 {
 Stack<string> strStack;
 strStack.push("Test1");
 strStack.push("Test2");
 strStack.push("Test3");
 strStack.print();
 strStack.pop();
 strStack.print();
 }
 cout << "Integer data" << '\n';
 {
 Stack<int> intStack;
 intStack.push(10);
 intStack.push(20);
 intStack.push(30);
 intStack.print();
 intStack.pop();
 intStack.print();
 }
 return 0;
}

Answer 1

Readability

Please put a space after the include and before the <

#include<iostream>
#include<string>
#include<memory>

Don't do this

You can read any other C++ revue on this site.

using namespace std;

See: Why is "using namespace std" considered bad practice?

Don't add useless comments

// Template Node
template <typename T>
struct Node

Thanks but I can read the code I can see it is a template and a class called Node. Useless comments are worse than no comment.

// Template Stack
// Note: T type is used to set the Node type
template <typename T>

Again you are describing what the code does. If you write nice well formatted code it should explain itself (with good method and variable names).

// Notice <T> after the class name, it is the syntax requirement
template <typename T>
void Stack<T>::push(const T &data) {

Don't explain the compiler rules. The compiler does not care nor do I.

Pass parameters by reference

Here you pass the parameters by value.

 Node(T d, shared_ptr<Node> n) : data(d), next(n) {}

This means you are copying the data to the parameters than you are making a second copy of the data into the member variables.

Try this:

 Node(T const& d, shared_ptr<Node>& n) : data(d), next(n) {}

You can even use move semantics. I'll cover that more in the push() below.

 Node(T&& d, shared_ptr<Node>& n) : data(std::move(d)), next(n) {}

Push

You don't need that if block.

void Stack<T>::push(const T &data) {
 shared_ptr<Node<T>> temp = make_shared<Node<T>>(data,nullptr);
 if (head == nullptr) {
 head = temp;
 }
 else {
 temp->next = head;
 head = temp;
 }
}

You always assign temp to head. The value assigned to temp.next is nullptr if the head is nullptr or it is head. In both cases the value of head is assigned to next.

void Stack<T>::push(const T& data) {
 head = make_shared<Node<T>>(data, std::move(head));
}

You pass the data by reference, which is good. Make sure that node also takes the parameter by reference.

In some situations we also want to add move semantics to the class. So it can also be useful to add a push() that takes an r-value reference. This allows for a much more efficient push when T is large (like an vector).

void Stack<T>::push(T&& data) {
 head = make_shared<Node<T>>(std::move(data), std::move(head));
}

Also in the vain of push. Sometimes T is expensive to build and copy but its arguments can easily be passed. In this case it is worth allowing the user to pass the parameters to the constructor of T and then building the T object in place (rather than passing it around).

template<typename... Args>
void Stack<T>::push<Args>(Args...&& args) {
 head = make_shared<Node<T>>(std::move(args));
}
template<typename... Args>
Node<T>::Node<Args...>(Args...&& args)
 : data(args...) // Use the constructor of T
{}

Top

Here you return the result by value. This means a copy is probably generated. This could be expensive so it I would return a reference rather than a value. The user can then decide if they want to copy the reference explicitly into a value.

T Stack<T>::top() const {
 return head->data;
}

Change to

 T const& Stack<T>::top() const {
// ^^^^^^
 return head->data;
 }

Print

Looks fine.

void Stack<T>::print() const {
 // shared_ptr<Node<T>> temp;
 for (auto temp = head; temp != nullptr; temp = temp->next)
 cout << temp->data << '\n';
}

The thing I would change is to pass a stream as a parameter (std::cout is not the only stream you want to print to). It can default to std::cout for backward compatibility.

Also the standard way of printing in C++ is using operator<< so it would be nice to define that in addition.

void Stack<T>::print(std::ostream& str = std::cout) const
{
 for (auto temp = head; temp != nullptr; temp = temp->next)
 str << temp->data << '\n';
}
std::ostream& operator<<(std::ostream& str, Stack<T> const& value)
{
 value.print(str);
 return str;
}

• hoffmale: Also, might want to take a look at your last example on push, there are some issues: it doesn't propagate the old head, you are missing a typename T in the template, and, since Args...&& are being deduced, you should use std::forward instead of std::move (since Args...&&might bind to rvalue and lvalue references).
• Loki Astari: I deliberately left the template<typename T> off (to match my other examples).
• Loki Astari: Can you expand on the forward Vs move I don't understand what you are trying to say.
• hoffmale: basically, if you have a function template like template<typename T> f(T&& arg) {}, where T gets deduced, T&& is a so called forwarding reference (previously universal reference). In this case, arg can bind to rvalues and lvalues, so using std::move might actually turn an lvalue reference into an rvalue reference. std::forward only moves arg if it is a rvalue reference, and passes arg as a lvalue reference otherwise. (You might want to look up perfect forwarding.)
• hoffmale: @incomputable: that should be U& && -> U& so in case T gets deduced as U&, arg is of type U& (it's still an lvalue!)

Answer 2

#include "stdafx.h"

Assuming this is the precompiled header, you should only include it in .cpp files, not in header files. It is only used to speed up compilation.

template <typename T>
struct Node
{
 T data;
 shared_ptr<Node> next;
 Node(T d, shared_ptr<Node> n) : data(d), next(n) {}
};

Nodes are only used in the implementation of Stack; they are not exposed by the interface. So, Node should be a private nested struct of Stack.

You don't actually use shared ownership here. Each Node instance is owned either by another Node instance or by a Stack instance. Therefore using shared_ptr is a premature pessimization here. You should use unique_ptr instead. The same holds for Stack::head.

template <typename T>
class Stack {
 //...
public:
 Stack() : head(NULL) {}
 Stack(const Stack<T> &rhs) = delete;
 Stack& operator=(const Stack<T> &rhs) = delete;
 //...
};

Use nullptr instead of NULL, it provides better type safety. Also, the default constructor of shared_ptr (and unique_ptr) already initialize the pointer to nullptr. So, you don't need to actually implement the default constructor of Stack, but can just define it as default.

Stack() = default;

I don't see any reason why Stack should not be copyable or asignable. Don't be lazy and implement these functions when you write a class is is supposed to be reused. While your at it, throw in the move constructor and move assignment operator too, unless your compiler will automatically generate them appropriately.

Answer 3

Smart pointers can seriously bite you when you try to use them in the implementation of a node-based container like a stack. If your container contains enough elements, then its destructor can easily overflow the call stack by recursively calling the smart pointer destructor to too great a depth of recursion.

Say your container contains 1,000 elements. When it is destroyed, its destructor calls the destructor of its head smart pointer, and that destructor calls the destructor of its next smart pointer, and that destructor calls the destructor of its next smart pointer, and so on, until the depth of function call recursion surpasses the capacity of the call stack and it overflows.

This can be worked around by defining a destructor for your container that repeatedly calls pop until the container is empty. (And a public is_empty member function is also a pretty good idea.)