14
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Have you figured out what the C prefix means for CStack? It appears to be a Microsoft thing that people are using without explanation. Classes don't need to start with 'C'. \$\endgroup\$ – Thomas Matthews Mar 14 '18 at 22:17
  • \$\begingroup\$ That's just a naming convention usually done in C#. Like classes start with 'C', enums with 'E' etc. Other people have other naming conventions, and I kinda like this one. \$\endgroup\$ – Flamefire Mar 15 '18 at 8:03
  • \$\begingroup\$ exactly as @Flamefire said. Just so someone who reads your code can quickly tell what is what. 'T' for typedef, 'm_' for member variable, 'g_' for global, 's_' for static. \$\endgroup\$ – SRG Mar 15 '18 at 14:03
  • \$\begingroup\$ What is the purpose? Is this an exercise, or is there some requirement that this stack meets that std::stack does not? \$\endgroup\$ – Jive Dadson Mar 16 '18 at 23:12
  • 1
    \$\begingroup\$ @JiveDadson I tend to subscribe to this view. Practice. Ask for code review. Learn from your mistakes. Understand the reasons behind each improvement. Repeat. But thats just me. \$\endgroup\$ – SRG Mar 17 '18 at 16:32
10
\$\begingroup\$

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.

http://lokiastari.com/blog/2016/02/27/vector/

\$\endgroup\$
  • \$\begingroup\$ Isnt the move assignment already included in the copy assignment operator as the compiler can determine whether rhs is moveable? I do wonder about the noexcept for that case though \$\endgroup\$ – miscco Mar 14 '18 at 18:12
  • \$\begingroup\$ @miscco I have heard something about that before. But have to had time to research it. If you have something I could read I would be more than willing to update my answer. \$\endgroup\$ – Martin York Mar 14 '18 at 18:21
  • \$\begingroup\$ @misco, the compiler will not do it implicitly. IIRC it breaks some C++03 code, but I cannot recall an example (it is probably very subtle, as usually it should just work). And yeah, if the type doesn't have noexcept copy, then it won't be possible to put correct noexcept specification. \$\endgroup\$ – Incomputable Mar 14 '18 at 19:21
  • \$\begingroup\$ @MartinYork Actually that doesnt even compile: ideone.com/X2L2mP \$\endgroup\$ – miscco Mar 14 '18 at 21:11
  • 1
    \$\begingroup\$ Further improvement: Get rid of the move-assignment and take the argument of the copy-assignment by value. That eliminates the need for the explicit copy and the move-assignment: en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Copy-and-swap \$\endgroup\$ – Flamefire Mar 15 '18 at 8:12
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks you for reviewing my code. There are a few new things for me to consider to implement propogate on copy, move assignment. I am in the process of updating my code on github. I will leave the original here so people have some context. \$\endgroup\$ – SRG Mar 15 '18 at 17:53
  • \$\begingroup\$ Can i really move instead of copying in Grow()? There are two separate blocks of memory. The new block of memory created by Grow() and the old existing block. If i move construct my objects instead of copy construct them to the new memory block wont they take ownership of the old block of memory. Move will takeover the internals of the moved-from object. The internals will be in the old block of memory? \$\endgroup\$ – SRG Mar 15 '18 at 17:58
  • \$\begingroup\$ think for a bit how move semantics work. When you move an object you move the entire object to the new position and leave a moved-from object in its place that still needs to be destructed. The moved-from object is then completely independent of the internals of the new moved object. \$\endgroup\$ – ratchet freak Mar 15 '18 at 18:16
  • \$\begingroup\$ understood. nothing different when dealing with allocators as oppose to allocating a block of memory yourself. \$\endgroup\$ – SRG Mar 15 '18 at 22:59
  • \$\begingroup\$ Thanks again for reviewing my code. I have a revised version of my stack here btw. github.com/aaraia/Stack3. I have removed allocators for now. There is a good talk here about how they are being improved. youtube.com/watch?v=v3dz-AKOVL8 \$\endgroup\$ – SRG Mar 20 '18 at 13:23
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Point 7 you made. Is try_emplace a member function of stack? This would require adding class... ARGS to the stacks template parameters? Can try_emplace have a separate template specification and still be a memeber function? I have a revised version of my stack here btw. github.com/aaraia/Stack3 \$\endgroup\$ – SRG Mar 20 '18 at 13:20
  • \$\begingroup\$ @SRG: Yes, a member-function can be a template independent of whether the containing class-type is a template, and that is necessary for proper template-argument-deduction there. As an aside, I looked at your new code, and you really need to work on exception-safety. As an example, try tracing the values of members in the copy-ctor until the first call which might throw. And why are you so reluctant to use the indexing-operator? \$\endgroup\$ – Deduplicator Mar 20 '18 at 13:58
  • \$\begingroup\$ Hi, thanks again. I added exception checks everywhere i think they should be now, apart from clear(i have left it up to users of clear() to handle the exception). @MartinYork Also added an emplace function. \$\endgroup\$ – SRG Mar 20 '18 at 16:52
  • \$\begingroup\$ @SRG: Please trace the copy-ctor on github: 1. ctor-init-list: Does nothing, everything still uninitialized. 2. Call to safeDeepCopy() throws. 3. Re-throw 4. dtor called because you throw out of the ctor-body, resulting in UB. \$\endgroup\$ – Deduplicator Mar 20 '18 at 17:15
  • \$\begingroup\$ I might have misunderstood but constructors can throw. isocpp.org/wiki/faq/exceptions#ctors-can-throw and stroustrup.com/bs_faq2.html#ctor-exceptions. In my case std::terminate would be called if no try {} catch(){} surrounds the copy construction? if there is try/catch std::terminate would not be called? \$\endgroup\$ – SRG Mar 20 '18 at 17:51

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.