Stack Interview Code methods made from class Node and Smart Pointers

Question

Mainly looking for feedback on my use of smart pointers to implement a standard stack. For interview level production code I have also include a namespace and asserts to test my class, let me know if that would be appropriate for an interview. I'd like feedback on my pointer management to avoid memory leaks, like how I have the option to use the classic SomeObjectNameHere* pointer to swap data in my swap function or the unique_ptr swap method.

Other than that I have taken feedback from all my previous posts to properly. Let me know what you think

#include <cassert>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>

namespace sonsprl
{
    class Stack
    {
        private:
            class Node
            {   private:
                    int m_data;
                    std::unique_ptr<Node> m_previous;
                public:
                    Node(int data, std::unique_ptr<Node>& previous) {
                        m_data = data;
                        m_previous = std::move(previous);
                    }
                    ~Node() { m_previous.reset(); }
                    const int data() { return m_data; }
                    std::unique_ptr<Node>& previous() { return m_previous; }
            };
            int m_size{0};
            std::unique_ptr<Node> m_top;
        public:
            ~Stack() { m_top.reset(); }
            void push_back(int data) {
                m_top = std::unique_ptr<Node>(new Node(data, m_top));
                ++m_size;
            }
            void pop_back() {
                if(!m_top) {
                    throw std::out_of_range("ERROR: Can not pop. Stack empty.");
                }
                else {
                    m_top = std::move(m_top->previous());
                    --m_size;
                }
            }
            int top() {
                return m_top.get()->data();
            }
            int size() {
                return m_size;
            }
            bool empty() {
                return (m_size == 0) ? true : false;
            }
            void swap(Stack& other_stack) {
                m_top.swap(other_stack.m_top);
                // Node* other_top = other_stack.m_top.release();
                // other_stack.m_top = std::move(m_top);
                // m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
            }
            friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
                std::string stack_string = "";
                Node* current = stack.m_top.get();
                for(; current; current = current->previous().get()) {
                    stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + '\n';
                }
                os << stack_string;
                os << "---\n";
                return os;
            }
    };
}

int main()
{
    sonsprl::Stack stack;
    try {
        stack.pop_back();
    } catch(const std::out_of_range& e) {
        std::cout << e.what() << '\n';
    }
    assert(stack.empty());

    stack.push_back(1);
    stack.push_back(2);
    stack.push_back(3);
    assert(stack.size() == 3);
    assert(stack.top() == 3);

    stack.pop_back();
    stack.pop_back();
    assert(stack.size() == 1);

    std::cout << stack << '\n';

    stack.push_back(4);
    stack.push_back(4);

    assert(stack.empty() == false);

    sonsprl::Stack swap_stack;
    swap_stack.push_back(5);
    swap_stack.push_back(6);
    swap_stack.push_back(7);
    swap_stack.push_back(8);
    assert(swap_stack.top() == 8);

    std::cout << "pre swap\n";
    std::cout << stack << '\n';
    std::cout << swap_stack << '\n';
    swap_stack.swap(stack);
    std::cout << "post swap\n";
    std::cout << stack << '\n';
    std::cout << swap_stack << '\n';

    assert(stack.top() == 8);
    assert(swap_stack.top() == 4);

    std::cout << "passed all stack tests :) \n";

    return 0;
}

Answer 1

Overall

Not sure I agree with the use of std::unique_ptr inside of Node. BUT I can't really argue against it. So I am not going to push the point.

You need to concentrate on your const correctness.

Design

Using a linked list for a stack seems very inefficient way of doing this. Each object that you save required an additional pointer. In this case were your data is a int you are basically doubling the space requirements (that's not including any overhead for memory management imposed by the system libraries).

The standard provides a std::stack class. This uses the std::deque underneath the hood (default) to store the data.

You should think about what it would take to templatize your Stack class. Storing int is good as a test; but there is no reason you could not store any object. Once you have done that there are a couple of extra functions that would be nice:

 void push_back(T const& data);       // insert by copy.
 void push_back(T&& data);            // insert by move
 template<typename... Args>
 void emplace_back(Args&& p...);      // construct in place at the back

Code Review

I assume this has some meaning to you?

namespace sonsprl

---

Passing a std::unqiue_ptr by non-cost referece is a bit strange. I would normally expect that to be passed by r-value reference. When I was reading the Stack class below it confused me that you were passing a std::unique_ptr as a parameter without the std::move.

                    Node(int data, std::unique_ptr<Node>& previous) {

You are affectively hiding the transfer of ownership that the C++ community has tried very hard to make explicit and visible.

---

Both your destructors are us-less:

                    ~Node() { m_previous.reset(); }
            ~Stack() { m_top.reset(); }

I would remove both.

---

You could mark this function as const. I would not bother marking the int const (but it does not hurt). When you convert this into a template you should return by const reference. T const&.

                    const int data() { return m_data; }

                    // I would have written like this:
                    T const& data() const { return m_data; }
                    //^^^^^^        ^^^^^

---

As mentioned above. I don't like the passing of m_top as a parameter (and it being changed inside the Node constructor).

            void push_back(int data) {
                m_top = std::unique_ptr<Node>(new Node(data, m_top));
                ++m_size;
            }

I would have written it like this:

            void push_back(int data) {
                m_top = std::unique_ptr<Node>(new Node(data, std::move(m_top)));
                ++m_size;
            }

This way I can explicitly show that I am transferring ownership of m_top into the Node and that the newly created object is taking the place as the new value of m_top.

---

There is an empty() function that allows users to check if the stack is empty before calling pop_back(). So also checking inside is a waste of time. If you really want to check then you should provide a checked and an unchecked version of pop.

            void pop_back() {
                if(!m_top) {
                    throw std::out_of_range("ERROR: Can not pop. Stack empty.");
                }
                else {
                    m_top = std::move(m_top->previous());
                    --m_size;
                }
            }

Note: the main use case is going to be something like this:

    while(!stack.empty()) {
        stack.pop_back();     // I just checked its empty
    }                         // are you going to check again?

If you look at functions in the standard library they tend not to throw (even if this would cause the object to be invalid). Instead the writters provide mechanisms to validate the pre-conditions of method so the user can do the check manually. Sometimes they also provide checked alternatives. That way a user of the functionality does not need to pay an extra cost (for the check) if they have already validate the pre-conditions.

An example of this is:

std::vector::operator[]std::size_t index)    // unchecked access into the container.
std::vector::afstd::size_t index)            // un-unchecked access into the container.

---

The top() function should be const. Your return value is inconsistent with the return type from data() (which returns a const). Consistency is king in programming.

Talking about consistency. The pop_back() function checks the state of the container (and throws if it is not valid). To be consistent the top() method should perform a similar check (or both of them should not perform a check).

            int top() {
                return m_top.get()->data();
            }

Do you need to call get() above?

---

Another couple of function that should be marked const

            int size() {
            bool empty() {

---

Swap should be marked noexcept:

            void swap(Stack& other_stack) {
                m_top.swap(other_stack.m_top);
                // Node* other_top = other_stack.m_top.release();
                // other_stack.m_top = std::move(m_top);
                // m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
            }

I don't see you swapping the size!!!!!!
Every part of the swapped object should be exchanged.

The normal pattern for this is to use swap() on each member.

     void swap(Stack& other) noexcept {
         using std::swap;
         swap(m_top,  other.m_top);
         swap(m_size, other.m_size);
     }

It's also nice to add a friend function so others can do the swap naturally as well.

     friend void swap(Stack& lhs, Stack& rhs) {
         lhs.swap(rhs);
     }

---

When printing. The value being printed is normally marked const (because printing it should not change it).

            friend std::ostream& operator<<(std::ostream& os, Stack const& stack) { 
                                                                    ^^^^

Why are you building a string to output?

                std::string stack_string = "";
                // STUFF
                os << stack_string;

Just print each value directly to the stream.

            Node* current = stack.m_top.get();
            for(; current; current = current->previous().get()) {
                os <<  '|' << current->data() << "|\n";
            }

---

One late entry:

 return (m_size == 0) ? true : false;

You are using a bool test to decide which bool to return. Simpler to simply return the result of the test.

 return m_size == 0;

---

How I would have written it (apart from keeping the std::unique_ptr in Node).

namespace ThorsAnvil
{
    namespace Container
    {
        template<typename T>
        class Stack
        {
                struct Node;
                using Chain = std::unique_ptr<Node>;
                struct Node
                {
                        T       data;
                        Chain   prev;
                        Node(Chain&& prev, T const& data)
                            : data(data)
                            , prev(std::move(prev))
                        {}
                        Node(Chain&& prev, T&& data)
                            : data(std::move(data))
                            , prev(std::move(prev))
                        {}
                        template<typename... Args>
                        Node(Chain&& prev, Args&&... p)
                            : data(std::forward<Args>(p)...)
                            , prev(std::move(prev))
                        {}
                };
                int                     m_size{0};
                std::unique_ptr<Node>   m_top;
            public:
                void push_back(T const& data) {
                    m_top = std::make_unique<Node>(std::move(m_top), data);
                    ++m_size;
                }
                void push_back(T&& data) {
                    m_top = std::make_unique<Node>(std::move(m_top), std::move(data));
                    ++m_size;
                }
                template<typename... Args>
                void push_back(Args&&... p) {
                    m_top = std::make_unique<Node>(std::move(m_top), std::forward<Args>(p)...);
                    ++m_size;
                }
                void pop_back() {
                    m_top = std::move(m_top->prev);
                    --m_size;
                }
                T const& top()  const {return m_top->data;}
                int size()      const {return m_size;}
                bool empty()    const {return m_size == 0;}
                void swap(Stack& other) noexcept {
                    using std::swap;
                    swap(m_top,  other.m_top);
                    swap(m_size, other.m_size);
                }
                friend void swap(Stack& lhs, Stack& rhs) {
                    lhs.swap(rhs);
                }
                friend std::ostream& operator<<(std::ostream& os, Stack const& stack) {
                    Node* current = stack.m_top.get();
                    for(; current; current = current->prev.get()) {
                        os << "|" << current->data << "|\n";
                    }
                    return os << "---\n";
                }
        };
    }
}

Answer 2

• swap does not swap sizes.

• If pop_back throws on empty stack, top shall also throw.

• I see no reason for an operator<< to build a string.

      os << '|' << std::to_string(current->data()) << '|\n';
  

  in a loop achieves the same result.

  I would also consider letting Node to output itself with Node::operator<<.

Answer 3

class Node {
  private:
    int m_data;
    std::unique_ptr<Node> m_previous;
  public:
    Node(int data, std::unique_ptr<Node>& previous) {
         m_data = data;
         m_previous = std::move(previous);
    }

Since Node is an implementation detail of Stack, you don't need to hide Nodes members data and previous from Stack. Consider using aggregate initialization so that members can be directly manipulated.

    ~Node() { m_previous.reset(); }

Since the destructor isn't doing anything after std::unique_ptr<T>::reset(), it's equivalent to letting the class call the destructor of your std::unique_ptr<Node> member.

    ~Node() { }

Now, you have chained your pointers such that the current node is the owner of the previous node which owns the previous node and so on. When we call the destructor, this is essentially what is happening

m_previous.reset() calls 
🡒 m_previous->~Node()
🡒 m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->~Node()
🡒 m_previous->m_previous->m_previous->m_previous->m_previous->~Node()
🡒 and so on

And it's correct in that each node gets cleaned up and all the cleanup happens automatically. Unfortunately, it's also recursive which means its bounded by the stack (memory) depth. To fix this, you'll need to iteratively remove elements.

Whenever you define any of the special member functions (destructor, copy/move constructor, copy/move assignment), you should consider whether your class needs the others. This is commonly known as the rule of five. By providing the destructor, the move operations are not declared. Normally, the copy operations are defaulted, but std::unique_ptr as a data member results in those being implicitly deleted. You'll need to implement the copy and move operations if your stack is to have those value semantics. The general guideline is that if you explicitly declare any of the special member functions, then explicitly declare all of the special member functions and explicitly =default (opt into the implicit behavior), =delete (opt out of the implicit behavior), or user-define each of them.

    const int data() { return m_data; }

const as a qualifier on the return type is ignored here.

---

class Stack {
  ...
  public:
    ~Stack() { m_top.reset(); }

Same issues as node, from recursive destruction to missing copy/move operations.

    void push_back(int data) {
        m_top = std::unique_ptr<Node>(new Node(data, m_top));
        ++m_size;
    }

Avoid new and prefer std::make_unique to make std::unique_ptrs. It cuts down on the duplication and enforces consistency when you need safety in more complex initialization sequences.

    void pop_back() {
        if(!m_top) {
            throw std::out_of_range("ERROR: Can not pop. Stack empty.");
        }
        else {
            m_top = std::move(m_top->previous());
            --m_size;
        }
    }

Don't use else after language constructs that interrupts control flow (return, break, continue, goto).

    int top() {
        return m_top.get()->data();
    }

Be consistent with the naming. If directionality matters to you, then back() would be consistent with push_back() and pop_back(). top() would go better with functions like push(), and pop().

Be consistent with your exception handling. If you throw on an empty stack pop_back(), then you should throw on an empty stack top().

In order to modify the top value, the user has to pop (deallocate) and push (allocate). Consider allowing the user to access the top element by reference and modify the element in place.

    bool empty() {
        return (m_size == 0) ? true : false;
    }

m_size == 0 will return a boolean that maps to the same exact values in your ternary. The compiler knows that and optimizes it for you, but you could help readers and just do it yourself.

    void swap(Stack& other_stack) {
        m_top.swap(other_stack.m_top);
        // Node* other_top = other_stack.m_top.release();
        // other_stack.m_top = std::move(m_top);
        // m_top = std::unique_ptr<Node>(new Node(other_top->data(), other_top->previous()));
    }

You forgot to swap the size.

    friend std::ostream& operator<<(std::ostream& os, Stack& stack) {
        std::string stack_string = "";
        Node* current = stack.m_top.get();
        for(; current; current = current->previous().get()) {
            stack_string = stack_string + '|' + std::to_string(current->data()) + '|' + '\n';
        }
        os << stack_string;
        os << "---\n";
        return os;
    }

stack is passed in as a reference. operator<< doesn't modify the contents of stack and can be qualified with const.

You don't have to convert data (int) to a std::string to stream into a std::ostream. There is already an overload that does this for you.

Do you even need operator<<()? A stack is a last in-first out container. Inspection only exists on the latest element pushed on the stack that hasn't been popped. This function also requires the inclusion of <iostream>. A static constructor is transparently injected into every translation unit that includes this header, whether IOStreams are used or not in the user application.

---

Overall, you should read up on const-correctness and noexcept specification. As for the design of your stack, I would consider splitting the management of the nodes (forward_list?) from the interface of stack, which could be adapted over an existing sequence interface.