Implementation of a generic Stack in C++ [closed]

Question

I've implemented a generic Stack in C++. I would like a code review in regards to my code, especially on whether or not my implementation satisfy the following 4 points:

1. My Stack class guarantees Strong Exception Safety, using the copy and swap idiom
2. The container still works if T passed in is not default constructible
3. Correctness of the implementation of the Rule of Five
4. General implementation correctness and efficiency (i.e: No memory leaks, dangling pointers ... ...)

Additionally, I have also added 4 questions in the code as comments as my concerns in the correctness of my code's implementation/style. I would greatly appreciate if those questions are addressed in the review as well.

#pragma once
template <typename T>

class Stack
{
    public:
        Stack();
        Stack(const Stack& other);
        Stack(Stack&& other)                                noexcept;
        ~Stack();

        Stack<T>& operator =(const Stack<T>& other);
        Stack<T>& operator =(Stack<T>&& other)              noexcept;

        void swap(Stack<T>& other)                          noexcept;                   

        friend void swap(Stack<T>& A, Stack<T>& B)
        {
            A.swap(B);
        }

        void pop();
        T& top();
        void push(T item);              //Pass T by value? What if T is big and expensive?

    private:
        struct Node
        {
            Node* next;
            T data;                     //Should data be stored as a reference instead? (i.e: T& data)
        };                              //Should I be adding constructors/destructors and such in this struct?

        Node* head;
        void reverse(Node** head);      //reverse method is not specific to *this stack, should I make it inline or something?
};

template <typename T>
Stack<T>::Stack()
    :head(nullptr)
{}

template <typename T>
Stack<T>::Stack(const Stack& other)
    :Stack()
{
    Node* curr = other.head;

    while(curr != nullptr)
    {
        push(curr->data);
        curr = curr->next;
    }

    reverse(&head);
}

template <typename T>
Stack<T>::Stack(Stack&& other)          noexcept
    :head(nullptr)
{
    swap(*this, other);
}

template <typename T>
Stack<T>::~Stack()
{
    Node* curr = head;

    while(curr != nullptr)
    {
        Node* tmp = curr;
        curr = curr->next;
        delete tmp;
    }

    delete head;
}

template <typename T>
Stack<T>& Stack<T>::operator =(const Stack<T> &other)
{
    Stack tmp(other);
    swap(*this, tmp);
    return *this;
}

template <typename T>
Stack<T>& Stack<T>::operator =(Stack<T>&& other)    noexcept
{
    swap(*this, tmp);
    return *this;
}

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

template <typename T>
void Stack<T>::pop()
{
    if(head == nullptr)
        throw std::runtime_error("No item found in stack");

    Node* curr = head;
    head = head->next;
    delete curr;
}

template <typename T>
void Stack<T>::push(T item)
{
    Node* tmp = new Node;
    tmp->next = head;
    tmp->data = std::move(item);

    head = tmp;
}

template <typename T>
T& Stack<T>::top()
{
    if(head == nullptr)
        throw std::runtime_error("No item found in stack");

    return head->data;
}

template <typename T>
void Stack<T>::reverse(Node **head)
{
    if(head == nullptr || *head == nullptr)
        throw std::runtime_error("head is null or no head to reverse");

    Node *prev = nullptr;
    Node *next = *head->next;

    while(*head != nullptr)
    {
        *head->next = prev;
         prev = *head;
        *head = next;

        if(next != nullptr)
            next = next->next;
    }

    *head = prev;
}

Answer 1

Answers to your questions:

Should push take a value parameter?

Probably not.

As-is, the caller will make a temporary (on the stack), invoke the copy constructor on the temporary, and then push will allocate Node which includes a T, call the default constructor on it, and finally use the move-assignment to fill in Node.data. That means you allocate/construct T twice (once on the stack and once in Node) and reason over the members again in the move-assignment operator. If you're sure the type is small and easily copy-constructed, this is not worth worrying about and allows for more compact code (and a simpler interface). Similarly, if you trust the compiler's optimizer, maybe this isn't worth worrying about.

The simple alternative would be to provide both const T& and T&& versions of push and pass that on to a constructor for Node which takes the same type. A more elegant solution would be to take templatized arguments and std::forward to T's constructor (when it's made in Node). But, maybe then it should be called emplace.

Should Node.data be T& rather than T?

No. This has lifetime and aliasing implications which would violate a reasonably assumed contract for Stack<T>. If the calling code wants references, it can specify Stack<T&>.

Should Stack<T>::Node have constructors and destructors?

Since the struct is private, you should only add those members if the containing code needs it. I think the default destructor will meet your needs, but, for several reasons, you'll want to construct T.data and thus you'll need some constructor for T.

Stack<T>::reverse is independent of this*, how to decorate?

As I'll get to later, I'd recommend eliminating the method entirely, but the direct answer to your question is to use static.

Bugs:

head is deleted twice in destructor

Imagine if you have a single element Stack; you'll assign curr to that node, notice it's not nullptr, set tmp to that node, advance curr to nullptr, delete the node, exit the loop, and then try to delete head.

Stack<T>::push is not exception safe

If something throws an exception between the new Node and the head = tmp (especially T& operator::T(T&& other)), then you'll leak the Node. You should either wrap the logic in try/catch/delete/throw or use a smart pointer (e.g., std::unique_ptr) to guarantee cleanup.

Node* tmp = nullptr;
try
{
    tmp = new Node;
    // init tmp
}
catch (...)
{
    ::delete tmp;
    throw;
}

or

std::unique_ptr<Node> tmp(std::make_unique<Node>());
// init tmp
head = tmp.release();

You did not meet your goal #2 regarding no default constructor for T

When Node is constructed, it implicitly constructs a T with the default constructor.

Efficiency issues:

Your copy constructor does more work than it needs to.

Just have a Node** which lets you append to the linked list; you don't need to make two passes over the data.

Node** dst = &head;
for (Node* src = other.head; src != nullptr; src = src->next)
{
    std::unique_ptr<Node> tmp(std::make_unique<Node>());
    // init tmp

    *dst = tmp.release();
    dst = &(*dst)->next;
}

Of course, there is some shared code with push; I'll leave it to you to common factor it or, more likely, move the initialization for tmp into the constructor.

Give thought to object-creation overhead.

This was touched on regarding the question about push taking a ref.

Style issues:

std::unique_ptr<T> is a safer alternative than T* in most cases

The object referenced by Stack<T>.head is "owned" by the Stack<T> (it has sole control of lifetime). The same is true for Stack<T>::Node.next. Using this and swap, you can get a lot more confidence in execption correctness.

However, you'll have a de-facto implementation for your destructor which will be correct but might not be the implementation you'd choose. (The optimizer might do the right thing with respect to tail recursion; having confidence in this across compilers and versions requires more validation than I'd personally want to do when I could write an explicit loop to free stuff.)

use for for loops when appropriate.

Your copy constructor looks like an obfuscated for loop to me.

Share code between pop and your destructor.

while (head != nullptr) pop();

Your move constructor could use the default constructor.

This is a nit-pick, but logicially speaking, you're starting with an empty Stack<T> and swapping it with the temporary Stack<T>&&.