Stack Implementation in C++ with Exceptions

Question

Appreciate your thoughts and feedback...

Stack.h

//  Stack implementation
//  Push/Pop - Last In First Out
//

#pragma once

#include <memory>

template<class T>
class CStack
{

public:
    enum { DEFAULT_SIZE = 5 };

    CStack();
    CStack(const CStack& rhs);
    CStack(CStack&& rhs);
    CStack& operator=(const CStack& rhs);
    CStack& operator=(CStack&& rhs);
    ~CStack();  
    
    bool Empty() const;

    void Pop();
    bool Push(const T& t);
    const T& Top() const;
    T& Top();

private:
    bool Grow();

private:
    std::allocator<T> m_Allocator;
    T* m_pBase;
    int m_iCapacity;
    int m_iSize;
};

template<class T>
CStack<T>::CStack()
    : m_iCapacity(DEFAULT_SIZE)
    , m_iSize(0)
    , m_pBase(nullptr)
{
    //  allocate some memory for out stack
    try {
        m_pBase = m_Allocator.allocate(DEFAULT_SIZE);
    } catch (const std::bad_alloc& e) {
        //  do some error logging
        std::cerr << "Allocation Failed: " << e.what() << std::endl;
        //  rethrow exeception so client of this class can also handle it in whatever way they choose
        throw;
    }
}

template<class T>
CStack<T>::CStack(const CStack& rhs)
{
    try {
        //  allocate enough memory to hold stack
        m_pBase = m_Allocator.allocate(rhs.m_iCapacity);
    } catch (const std::bad_alloc& e) {
        //  do some error logging
        std::cerr << "Allocation Failed: " << e.what() << std::endl;
        //  rethrow exeception so client of this class can also handle it in whatever way they choose
        throw;
    }

    //  copy across the stack
    //  this performs a deep copy
    for (int i = 0; i < rhs.m_iSize; ++i) {
        //  copy across the T that is in the corresponding place
        m_Allocator.construct(m_pBase + i, *(rhs.m_pBase + i));
    }

    //  copy across size and capacity
    m_iCapacity = rhs.m_iCapacity;
    m_iSize = rhs.m_iSize;
}

template<class T>
CStack<T>::CStack(CStack&& rhs)
    : m_pBase(std::move(rhs.m_pBase))
    , m_iCapacity(rhs.m_iCapacity)
    , m_iSize(rhs.m_iSize)
{
    rhs.m_iCapacity = 0;
    rhs.m_iSize = 0;
    rhs.m_pBase = nullptr;
}

template<class T>
CStack<T>& CStack<T>::operator=(const CStack& rhs)
{
    //  check for self-assignment
    if (this == &rhs) {
        return *this;
    }

    //  perform copy-swap idiom
    //  create deep copy
    CStack<T> copy(rhs);

    //  swap 
    std::swap(m_pBase, copy.m_pBase);
    std::swap(m_iCapacity, copy.m_iCapacity);
    std::swap(m_iSize, copy.m_iSize);

    //  copy will be destructed when this function exits
    return *this;
}


template<class T>
CStack<T>& CStack<T>::operator=(CStack&& rhs)
{
    //  check for self move
    if (this == &rhs) {
        return *this;
    }

    //  take ownership of lhs memory
    T* pOldBase = m_pBase;
    int m_iOldCapacity = m_iCapacity;
    int iOldSize = m_iSize;

    //  move across ownership of rhs memory to lhs
    m_pBase = std::move(rhs.m_pBase);
    m_iCapacity = rhs.m_iCapacity;
    m_iSize = rhs.m_iSize;

    //  make sure rhs points to null
    rhs.m_pBase = nullptr;
    rhs.m_iCapacity = 0;
    rhs.m_iSize = 0;

    //  now that lhs points to rhs
    //  destruct old lhs
    for (int i = 0; i < iOldSize; ++i) {
        m_Allocator.destroy(pOldBase + i);
    }
    
    m_Allocator.deallocate(pOldBase, m_iOldCapacity);
    
    return *this;
}

template<class T>
CStack<T>::~CStack()
{
    //  check for valid pointer
    //  stack could have been moved-from
    //  and so the pointer will be null
    if (m_pBase) {
        //  destory any objects on the stack
        for (int i = 0; i < m_iSize; ++i) {
            m_Allocator.destroy(m_pBase + i);
        }

        //  deallocate any memory
        m_Allocator.deallocate(m_pBase, m_iCapacity);
    }
}

//  no op on an empty stack
//  use Empty() to check if stack is empty
template<class T>
void CStack<T>::Pop()
{
    //  destroy the top element
    m_Allocator.destroy(m_pBase + (m_iSize - 1));

    //  reduce the size of the stack
    --m_iSize;
}

template<class T>
bool CStack<T>::Push(const T& t)
{
    if (!m_pBase) return false;

    //  does the stack need to grow
    if ((m_iSize + 1) > m_iCapacity) {
        //  increase the size of the stack
        if (!Grow()) {
            return false;
        }
    }

    //  increase the size to include new element
    ++m_iSize;

    //  construct the pushed object in the allocated memory
    m_Allocator.construct(m_pBase + (m_iSize - 1), t);

    return true;
}

//  returns a const reference to the top element in the stack
//  it is up to the caller to make sure stack is non-empty using Empty() function
template<class T>
const T& CStack<T>::Top() const
{
    return *(m_pBase + (m_iSize - 1));
}

//  returns a const reference to the top element in the stack
//  it is up to the caller to make sure stack is non-empty using Empty() function
template<class T>
T& CStack<T>::Top()
{
    return *(m_pBase + (m_iSize - 1));
}

//  checks size of stack and returns true (if empty) or false 
template<class T>
bool CStack<T>::Empty() const
{
    return m_iSize <= 0;
}

//  increases the size of the stack by allocating a larger block of memory
//  and copying the stacks elements to it.
template<class T>
bool CStack<T>::Grow()
{
    //  not that stack should ever grow this big but just incase
    //  avoid overflow
    if (m_iCapacity >= (std::numeric_limits<int>::max() / 3)) {
        return false;
    }

    //  create a new stack twice the size
    int iNewCapacity = m_iCapacity * 2;
    
    T* pTempBase = nullptr;
    try {
        //  allocate some unintialised memory
        pTempBase = m_Allocator.allocate(iNewCapacity);
    } catch (const std::bad_alloc& e) {
        //  do some error logging
        std::cerr << "Allocation Failed: " << e.what() << std::endl;
        //  rethrow exeception so client of this class can also handle it in whatever way they choose
        throw;
    }

    for (int i = 0; i < m_iSize; ++i) {
        //  construct a copy in place in new allocation block
        m_Allocator.construct(pTempBase + i, *(m_pBase + i));
    }

    //  now that we have a exact copy of the stack
    //  swap pointers
    std::swap(m_pBase, pTempBase);

    //  deconstruct each object in the original stack
    for (int i = 0; i < m_iSize; ++i) {
        //  construct a copy in place in new allocation
        m_Allocator.destroy(pTempBase + i);
    }

    //  deallocate memory
    m_Allocator.deallocate(pTempBase, m_iCapacity);

    //  set the new capcity
    m_iCapacity = iNewCapacity;

    return true;
}

Code can be found on Github

Updated version with code review input added here New Github

Some of my own notes to help you understand my choices..

I left it up to the user of my stack to check if a stack is empty before trying to pop an item. This is how STL does it. Interested to hear your thoughts. Maybe throwing an exception is better when a pop on an empty stack is attempted?

Pop() does not return anything. You use Top() and Pop() to remove an item of the stack. Again STL style.

I am using an allocator to avoid unnecessary calls to constructors in empty stack slots. Couldn't work out any other way to achieve this. Consider an empty stack of 5 items. Without allocating a block of uninitialised memory, the constructor for type T would be called 5 times.

I am rethrowing any exceptions my stack produces. Better to just log a message to cerr and consume the exception (not rethrow)?

A public Resize function taking a size is better than Grow()? Someone might want to reduce the memory footprint of their stack manually.

Answer 1

I would make methods names start with a lower case letter to distinguish them from user defined types. But that's me.

A couple of small things:

template<class T>
CStack<T>& CStack<T>::operator=(const CStack& rhs)
{
    //  check for self-assignment
    if (this == &rhs) {
        return *this;
    }

You are using the copy-and-swap idiom. This works for self-assignment.

I would not do the check for self-assignment, as that is pessimizing the standard use case in an attempt to optimize for a very non-standard use case.

Though the potential for self-assignment exists (and your operator should work for self-assignment), in real life self-assignment is exceedingly rare. Thus your pessimization in the above code is run billions upon billions of times when it is not needed, compared to the one time it would help (of course check if my assumption is true in your code base). But the standard containers don't perform the check.

Your move operators look okay - though you should probably mark them noexcept.

But both the move operators can be easily implemented via the swap operation.

The easy way to write these three operators is:

template<class T>
CStack<T>::CStack(CStack&& rhs) noexcept
    : m_pBase(nulllptr)
    , m_iCapacity(0)
    , m_iSize(0)
{
    swap(rhs);
}
template<class T>
CStack<T>& CStack<T>::operator=(CStack const& rhs)
{
    CStack<T>  copy(rhs);
    swap(copy);
    return *this;
}
template<class T>
CStack<T>& CStack<T>::operator=(CStack&& rhs) noexcept
{
    swap(rhs);
    return *this;
}
template<class T>
void CStack<T>::swap(CStack<T>& other) noexcept
{
    using std::swap;
    swap(m_pBase, other.m_pBase);
    swap(m_iCapacity, other.m_iCapacity);
    swap(m_iSize, other.m_iSize);
}

Now if we look at the assignment operators. We can optimize them together into a single assignment that works for both move and copy.

template<class T>
CStack<T>::CStack(CStack&& rhs) noexcept
    : m_pBase(nulllptr)
    , m_iCapacity(0)
    , m_iSize(0)
{
    swap(rhs);
}
template<class T>
CStack<T>& CStack<T>::operator=(CStack rhs) noexcept
{
    // Notice the parameter is a value
    // If called with a r-value the parameter is move constructed (if it has one).
    // If called with a value or reference (or has no move constructor) the parameter is copy constructed


    // The original copy assignment had an internal copy but that
    // is taken care of by the parameter above.

    // Both copy/move assignment are identical for the last part.
    swap(rhs);
    return *this;
}
template<class T>
void CStack<T>::swap(CStack<T>& other) noexcept
{
    using std::swap;
    swap(m_pBase, other.m_pBase);
    swap(m_iCapacity, other.m_iCapacity);
    swap(m_iSize, other.m_iSize);
}

Just spotted one more thing :-)

Watch out for a fail during construction. If this happens the destructor is not called.

// Say you manage to create the first 4 of 8 copies.
// Then the 5th copy fails and throws.

for (int i = 0; i < rhs.m_iSize; ++i) {
    //  copy across the T that is in the corresponding place
    m_Allocator.construct(m_pBase + i, *(rhs.m_pBase + i));
}

// In this situation you leak 4 objects and m_pBase pointer.
// You should probably do this construction inside a try block
// and make sure you undo any objects on failure.

I cover a lot of this in my article on vectors.

https://lokiastari.com/posts/Vector-ResourceManagementAllocation

Answer 2

std::allocator_traits is a better way to interact with an allocator. It provides defaults for construct and destroy if the allocator doesn't do it itself.

using alloc_traits = std::allocator_traits<std::allocator<T>>;

If you want to be fully allocator-aware you should also prepare to deal with any fancy pointer that the allocator may use.

using pointer = alloc_traits::pointer;
using ptr_traits = std::pointer_traits<pointer>;

You must also be prepared to propagate the allocator as needed on copy and move.

Prefer std::size_t and std::ptrdiff_t when dealing with sizes and offsets.

When copying for grow you should do moves instead:

for (int i = 0; i < m_iSize; ++i) {
    //  construct a copy in place in new allocation block
    alloc_traits::construct(m_Allocator, pTempBase + i, std::move(*(m_pBase + i)));
}

Provide a move variant for push.

template<class T>
bool CStack<T>::Push(T&& t)
{
    if (!m_pBase) return false;

    //  does the stack need to grow
    if ((m_iSize + 1) > m_iCapacity) {
        //  increase the size of the stack
        if (!Grow()) {
            return false;
        }
    }

    //  increase the size to include new element
    ++m_iSize;

    //  construct the pushed object in the allocated memory
    alloc_traits::construct(m_Allocator, m_pBase + (m_iSize - 1), std::move(t));

    return true;
}

With all the times you copy pasted comments around there are bound to be mistakes in them when you forgot to update them (for example the non-const Top()). To avoid this prefer to keep comments to a minimum unless you need to explain the algorithm used.

Answer 3

Well, there's lots to improve:

1. You are ignoring the conventions of the standard-library. That makes (re-)use, especially using templates, near impossible, and means everyone has to learn that interface too.

2. Someone using your code cannot do anything useful with DEFAULT_SIZE, thus that implementation-detail should not be exposed.

3. Your class cannot be statically constructed, and the default-ctor can throw. Change it so the default-ctor need not allocate memory.

4. Related to the previous point, moving from an instance will leave the moved-from instance in a zombie-state only achievable that way. I'm not sure that quite qualifies as "valid but unspecified", but it is the best you can do if any valid state needs dynamically allocated memory and your move-ctor shall not throw, because that would make it nearly useless.

5. Don't you think TryPush() is a more appropriate name considering it can fail without throwing an exception? I kept to your naming-scheme, though it is foreign to C++.

6. Unless you know all your potential element-types won't benefit from move-ing, also provide a move-variant of the above.

7. Consider implementing template <class... ARGS> bool try_emplace(ARGS... args) and make the push-variants delegate to that. That leads to less repetition and more efficiency.

8. Don't store a std::allocator<T>-member. That needlessly bloats your class, you can simply construct an instance on demand for no cost where you need it.

9. Input and output should only ever be done when the programmer requests it. Doing it yourself, be it in the error-case or whatever, unless explicitly requested, severely diminishes reusability.

10. You really should implement friend void swap(CStack&, CStack&) noexcept and use that where appropriate (for example using copy-and-swap for move-ctor and move-assignment). Relying on std::swap() for your users works, but is inefficient, and you write it out in your implementation at least once anyway.

11. You know that you rely on the element-type being easily copied? You should move where allowed for more efficiency, and guard against copying throwing an exception.