2
\$\begingroup\$

Why you're here:

Today I bring you a simple Stack Machine and a Lot of questions. I am trying to gain a little bit more understanding of pointers, memory management and templates and thought a Stack implementation would be a fun exercise. As such I would love feedback pertaining to those areas, but I am of course open to any and all feedback.

A brief description:

I've implemented a LIFO (Last in First Out) data structure that publicly exposes the following methods

  1. Push (adds a new item to the top of the stack)
  2. Pop (removes the top item from the stack (and returns the data))
  3. Size (returns the size of the stack)
  4. IsEmpty (returns a Boolean whether the Stack contains any Items)

Stack.h

#pragma once
#include <stdexcept>

template <typename T>
struct Node
{
    T data;
    Node<T>* prev{ nullptr };
};

template <typename T>
class Stack
{
public:
    Stack();
    ~Stack();

    void push(const T& rhs);

    T& pop();

    unsigned size() const noexcept;

    bool isEmpty() const noexcept;
private:
    static const unsigned max_size = 1000u;
    unsigned numElements;
    Node<T>* top;
    T returnT;
};

template<typename T>
inline Stack<T>::Stack() :
    numElements(0),
    top(nullptr) {}

template<typename T>
inline Stack<T>::~Stack()
{
    while (!isEmpty())
    {
        pop();
    }
}

template<typename T>
inline void Stack<T>::push(const T& rhs)
{
    if (numElements == 0)
    {
        top = new Node<T>;
        top->data = rhs;
        numElements++;
    }
    else if (numElements < max_size)
    {
        Node<T>* tempNode = new Node<T>;
        tempNode->data = rhs;
        tempNode->prev = top;
        top = tempNode;
        numElements++;
    }
    else
    {
        throw std::overflow_error("Stack Overflow");
    }
}

template<typename T>
inline T & Stack<T>::pop()
{
    if (numElements > 1)
    {
        returnT = top->data;
        Node<T>* tempT = top;
        top = top->prev;
        delete tempT;
        numElements--;
        return returnT;
    }
    else if (numElements > 0)
    {
        returnT = top->data;
        Node<T>* tempT = top;
        top = nullptr;
        delete tempT;
        numElements--;
        return returnT;
    }
    else
    {
        // TODO: what do I do here?
    }
}

template<typename T>
inline unsigned Stack<T>::size() const noexcept
{
    return numElements;
}

template<typename T>
inline bool Stack<T>::isEmpty() const noexcept
{
    return numElements < 1;
}

Tests

#include "Stack.h"

#include <iostream>
#include <string>

int main()
{
    Stack<int> IntStack;
    Stack<std::string> StringStack;

    IntStack.push(6);
    IntStack.push(-600);
    for (unsigned i = 0; i < 10; ++i)
    {
        IntStack.push(i);
    }

    StringStack.push("First Element");
    StringStack.push("Second Element");

    std::cout << IntStack.size() << "\n";
    std::cout << StringStack.size() << "\n";

    while (!IntStack.isEmpty())
    {
        int value = IntStack.pop();
        std::cout << value << "\n";
    }

    while (!StringStack.isEmpty())
    {
        std::string value = StringStack.pop();
        std::cout << value << "\n";
    }

    char delay;
    std::cin >> delay;
}

Output

12 2 9 8 7 6 5 4 3 2 1 0 -600 6 Second Element First Element


A few additional Questions:

  • Is this enough functionality for a Stack? Or should I implement more functions?
  • When I pop from an empty Stack I simply return nothing. Is there something else I should do?
  • My IDE added inline. Is this actually an appropriate use?
\$\endgroup\$
3
\$\begingroup\$
#pragma once

If you plan on writing portable code, prefer #include guards over #pragma once. While most compilers provide support for #pragma once, there is no guarantee every implementation behaves the same. Be aware of the pitfalls of #pragma once if you decide to use them.


    ~Stack();

Follow the rule of five. If you define, =default or =delete any of the special member functions, you should consider if the behavior of the other special member functions are appropriate. In C++11, the special member functions are the destructor, copy constructor, move constructor, copy assignment operator, and move assignment operator.

    ~Stack();
    Stack(Stack const&);
    Stack(Stack &&);
    Stack& operator=(Stack const&);
    Stack& operator=(Stack &&);

You already realize that you need a destructor to clean up the Nodes on destruction. Do you need a user-defined copy constructor? The copy ctor value copies your data members. So, copying top only copies the pointer, not the pointed to Node<T>. Copying a populated Stack<T> results in two stacks, both with pointers pointing at the same data. You'll get undefined behavior when you double delete this list.

{
  Stack<int> s1;
  s1.push(1);
  s2.push(2);
  {
    Stack<int> s2(s1);   // Copy-construct. Fine!
    s2.pop();            // Fine!
    //auto v = s1.pop(); // double free/delete = undefined behavior, Fire everywhere
  }                      // or go out of scope with s2, destroying all data
}                        // then s1 goes out of scope... UB happens again.

The general advice is to avoid defining any of the special member functions if you can (rule of zero). If you need to define any of the special member functions, then =default, =delete, or provide a user definition for them all (rule of five).


template<typename T>
inline Stack<T>::Stack() :
    numElements(0),
    top(nullptr) {}

When you have constant initializers, prefer the in-class initializers.

struct Stack {
    // Stack() = default;

private:
    unsigned numElements {0};
    Node<T>* top {nullptr};
};

In this context, all of your data is set to constant initializers, so you can just use the compiler generated default constructor. You can explicitly default it (uncomment above) or implicitly default it (delete the commented line). Note - The default constructor is only implicitly auto-generated if there is no other user-declared constructor.


template<typename T>
inline Stack<T>::~Stack()
{
    while (!isEmpty())
    {
        pop();
    }
}

In your pop(), you do a lot of work. pop() has its own boundary check (on top of the destructor boundary check), an element copy, a delete, a pointer copy, and a decrement on each call. ~Stack() just needs the delete and pointer copy. Consider factoring out that portion that removes the top node and have both ~Stack and pop() call that.

template <typename T>
inline void Stack<T>::unchecked_pop() {
    Node<T>* temp = top;
    top = temp-> prev;
    delete temp;
}

template<typename T>
inline Stack<T>::~Stack()
{
    while (!isEmpty())
    {
        unchecked_pop();
    }
}

template <typename T>
inline T& Stack<T>::pop() {
    if (numElements > 1) {
        returnT = top->data;
        unchecked_pop();
        num_elements--;
        return returnT;
    }
    // ...
}

Avoid calling new and delete explicitly. In your code, you'll notice a pattern of creating a new Node<T> followed by copying some T (which could throw).

        Node<T>* tempNode = new Node<T>;
        tempNode->data = rhs;             // if this throws
        top = tempNode;                   // then this is never reached, memory leaks
                                          // and not cleaned up until OS reclaims

If you need to take ownership of a pointer, use std::unique_ptr/std::make_unique. C++14 adds std::make_unique, but you can use it C++11. Note - Don't add make_unique to std like shown in the linked answer.

DRY (don't repeat yourself) up your push and pop. The two statement bodies for each function essentially does the same work. In push, you trade away a pointer copy for a branch.

template <typename T>
inline void Stack<T>::push(const T& rhs) {
    if (numElements == max_size) {
        throw std::overflow_error("Stack Overflow");
    }

    auto temp = std::make_unique<Node<int>>();
    tempNode->data = rhs;
    tempNode->prev = top;
    top = temp.release(); // pass ownership of the new top to Stack
    numElements++;
}

In pop(), a single-element stack has a Node whose prev points to nullptr. You don't need the special case for 1 element.

template <typename T>
inline T & Stack<T>::pop() {
    if (empty()) {
        // TODO: what do I do here?
    }

    returnT = top->data;
    unchecked_pop();
    numElements--;
    return returnT;
}

You don't provide any other access to top. Perhaps you should just return by value?


Is this enough functionality for a Stack? Or should I implement more functions?

Does it meet your needs? At the very least, I would expect C++11 and beyond containers to support move operations (move construct, move assign, data emplacement, swap by move), comparisons, and perhaps even allocators. I would start by looking at std::stack.


When I pop from an empty Stack I simply return nothing. Is there something else I should do?

If you tell others "I'm returning T& from pop, it better return a T&. Consider the following:

Stack<int> s;
auto top = s.pop(); // BOOM!

You could return an optional from pop(). C++11 versions exist in Boost, Abseil, and Mnmlstc.

Or you could do it the standard way and not return anything. This was adopted from SGI and annotated in their documentation:

[3] One might wonder why pop() returns void, instead of value_type. That is, why must one use top() and pop() to examine and remove the top element, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use top() to inspect the value at the top of the stack.


My IDE added inline. Is this actually an appropriate use?

Yes.


General design notes - Utilize the adapter pattern.

I brought up the rule of zero earlier (If you can avoid defining the default operations, do). How could we accomplish that with a Stack? Well, a Stack is an abstract data type (an interface) over a collection of data that provides operations on a single end. The standard library provides us a bunch of collection types. We have sequence types that have front operations (std::deque, std::list, std::forward_list). We have sequence types that have back operations (std::deque, std::list, std::vector).

For the interface, it's very simple. We adapt the stack interface to the interface of a container that supports modifying operations on its back.

template <typename T, typename Container = std::deque<T>>
struct Stack {
public:
    void push(T const& value) { data.push_back(value); }
    void pop()                { data.pop_back(); }

    T & top();                { return data.back(); }
    T const& top() const;     { return data.back(); }

    bool empty() const        { return data.empty(); }
    std::size_t size() const  { return data.size(); }

    // etc...
private:
    Container data;
};

Note - Each member function should instead call a non-member free-standing function, but this review is getting pretty long and I'm trying to keep this example simple.

By using a container type to automatically manage the memory, I don't have to provide a destructor, copy operations, or move operations. The compiler-generated special member functions all work correct by construction. Think about how you would implement a queue using the adapter pattern.


Follow-up:

If you didn't remove the destructor would you = delete the copy constructor?

Do you want your Stack to be copyable? If not, they go ahead and =delete it. I'm going to assume you do want a copyable Stack. Since you are manually managing memory, you need to provide your own copy constructor.

Stack(Stack&) = default; 

is essentially

Stack(Stack const& other) :
  numElements{other.numElements},
  top{other.top}, // Simple pointer copy, both stacks own same Node<T>
  returnT{other.returnT}
{}

Your provided copy constructor needs to deep copy every Node by traversing the linked list.

Stack(Stack const& other) :
  numElements{other.numElements},
  returnT{other.returnT}
{
    // Actually deep copy other's linked list
}

If I take the return out of pop() and put it in top() I still need to deal with an empty stack. Return nothing?

It depends. Some believe in programming-by-contract, which would require the user to ensure that the container is not empty on pop() and top()

T& top() const {
    return top->data; // UB if empty. User's fault for not checking size.
}

I would use exceptions or Expects() from the GSL.

T& top() const {
    Expects(!empty()); // if empty, either throw or fail fast
    return top->data;
}

You have to decide what tradeoffs you are willing to make for defined behavior and safety.

Would a shared_ptr be needed here since Node->prev and top point to the same thing, albeit for 1 LoC?

Internally, std::unique_ptr would be better to represent the ownership semantics. Stack is the only owner of top. top is the only owner of the previous Node<T>. And so on. Smart pointers are great for conveying ownership, but their behavior with the special members in the rule of five isn't helpful. std::unique_ptr implementations still need a user-defined destructor (stack overflow from recursive destruction) and copy ops (not copyable). std::shared_ptr is similar, but performs a shallow copy like the raw pointer. I recommend Herb Sutter's talk on "Leak-Freedom in C++... By Default".

I also wish to say I was intentionally avoiding the STL. After all why use an underlying data structure that provides more functionality than I do when I could also just use std::stack

That's fine. I was just pointing out how to use the adaptor pattern. In my example, I could use any container with push_back, pop_back, etc (like plf::list).

Stack<int, plf::list<int>> stk;

In your Stack, it would be better to move all of the linked list management into its own container and have Stack use that container. That way, when you move to the next common abstract data type, a queue, you'll have a linked list container that can be reused.

\$\endgroup\$
  • 1
    \$\begingroup\$ Since you had a few questions, I added clarifications to the bottom of the review. \$\endgroup\$ – Snowhawk Apr 20 '18 at 20:27
5
\$\begingroup\$
  • The if (numElements > 1) and else if (numElements > 0) differ in a single line:

        top = top->prev;
    

    in the former vs

        top = nullptr;
    

    in the latter. Try to convince yourself that the bottom element's prev is nullptr (what happens when you push an element to the empty stack?). Therefore, these two clauses shall be combined.

    The else, i.e. size < 0 indicates the problem beyond your control, e.g. a badly corrupted heap, and shall throw an exception. Simply returning nothing is wrong, because it violates the declaration of the method. I wonder why you didn't get the warning.

  • Similarly, there is no reason to special case of pushing into empty stack. The code from else if clause works verbatim.

  • There is a popular school of thought claiming that pop() must return nothing (i.e just pop an element), and an access to a value must be done via a separate method (like front() or peek()). There are pros and cons to this point of view; keep in mind that STL uses this style.

  • Since you limit the stack size to max_size, I see no reason for the overhead caused by the prev pointer, and dynamical allocations. A fixed size std::vector<T>, or std::array<T>, or even a plain old T data[max_size] array would serve the purpose in a cleaner way.

\$\endgroup\$
  • \$\begingroup\$ @bruglesco There are reasons to avoid naked C arrays. Once wrapped into a class, thus fully under your control, there is nothing wrong with it. Re: having max size, it is a valid design decision. Just try to avoid overhead. \$\endgroup\$ – vnp Apr 19 '18 at 20:03
  • \$\begingroup\$ @bruglescoDepends on what you call an advantage. A limited stack and unlimited stack are two different beasts, both living in their respective realms. E.g. I would never deploy an unlimited stack in the embedded system. Likely, I can happily use one in a desktop program. \$\endgroup\$ – vnp Apr 19 '18 at 20:13
  • \$\begingroup\$ Maybe you could have peek that returns the item and pop that removes the item and returns it. pop's return value could just be ignored if it's not needed. \$\endgroup\$ – Solomon Ucko Apr 19 '18 at 22:00
3
\$\begingroup\$

vnp has already covered most of the big stuff, and I wholeheartedly agree with each point.

I do have a few details that I thought worth mentioning:

The inline and noexcept qualifiers seem entirely appropriate and helpful. The const qualifier on size() and isEmpty() is also correct, and it's good practice to think about when methods can be marked const. (Although it only becomes relevant with immutable objects, and the notion of an immutable stack is a very weird one to imagine!)

You can define the behaviour of class methods within the class definition. Since you're using templates and the implementation needs to go in the header anyway, it would probably be more readable to do so for at least the short methods.

#pragma once is widely supported but non-standard. If you want to write portable code, it's generally considered better to use include guards.

You seem to have an excessive fondness for inequalities. When you have narrowed it down to just one possible satisfying option, it is generally clearer to check equality. For example else if (numElements == 1) instead of else if (numElements > 0).

Your T returnT object should not be a stack member variable. Just declare it in the pop method. In general, declaring temporary variables as local to their use as possible helps avoid bugs when they get changed, and also helps the compiler with its optimisations so you get faster code.

The memory management all looks correct to me. Everything that is manually allocated is manually deleted, and nothing is used after deletion. As already mentioned, preallocated contiguous memory generally makes for much more efficient code. Even if you wanted to get rid of the size restriction, allocating bigger chunks at a go would improve the performance. For comparison, the STL stack uses a deque rather than a list as its default underlying container.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.