4
\$\begingroup\$

I have implemented a dynamic array based stack. Can someone point out any pitfalls or things that can be done better?

MyStack.h

#ifndef MYSTACK_H
#define MYSTACK_H

#include <iostream>
#include <stdexcept>

template<class T>
class MyStack
{

private:

    T* m_array;

    int m_count;

    int m_max_size;

    static const int m_growth_factor = 2;

    static const int m_initial_max_size = 10;

public:

    MyStack();

    inline MyStack(const MyStack<T> &rhs) { *this = rhs; }

    void operator=(const MyStack<T> &rhs);

    MyStack(int initial_max_size);

    ~MyStack();

    void push(T data);

    void pop();

    void clear();

    inline bool empty() { return m_count == 0; }

    inline T& top() { return m_array[m_count - 1]; }

    inline int size() { return m_count; }

private:

    void init();

    void increase_array_size();
};

template <class T>
MyStack<T>::MyStack() : m_count(0), m_max_size(m_initial_max_size) 
{
    init();
}

template <class T>
MyStack<T>::MyStack(int initial_max_size) : m_count(0), m_max_size(initial_max_size)
{
    init();
}

template <class T>
MyStack<T>::~MyStack()
{
    delete [] m_array;
}

template <class T>
void MyStack<T>::init()
{
    m_array = new T[m_max_size];
    m_count = 0;
}

template <class T>
void MyStack<T>::increase_array_size()
{
    m_max_size = m_growth_factor * m_max_size;
    T* tmp = new T[m_max_size];

    for(int i = 0; i < m_count; i++)
        tmp[i] = m_array[i];

    delete [] m_array;

    m_array = tmp;
}

template <class T>
void MyStack<T>::push(T data)
{
    if(m_count == m_max_size)
        increase_array_size();
    m_array[m_count++] = data;
}

template <class T>
void MyStack<T>::pop()
{
    if(m_count == 0)
        throw std::underflow_error("Underflow Exception!!!");
    m_count--;

}

template <class T>
void MyStack<T>::clear()
{
    delete [] m_array;
    m_max_size = m_initial_max_size;
    init();
}

template <class T>
void MyStack<T>::operator=(const MyStack<T> &rhs)
{
    if(this != &rhs)
    {
        delete [] m_array;
        init();
        for(int i = 0; i < rhs.m_count;i++)
        {
            this->push(rhs.m_array[i]);
        }

    }
}
#endif // MYSTACK_H

main.cpp

#include <iostream>
#include "MyStack.h"

using namespace std;

int main(int argc, char* argv[])
{

    MyStack<int> stack;
    int sum = 0;

    for(int i = 0; i < 15; i++)
        stack.push(i);

    while(!(stack.empty()))
    {
        sum += stack.top();
        stack.pop();
    }

    cout << "sum: " << sum << endl;

    stack.push(10);
    stack.push(20);

    stack.top() -= 5;

    cout << "stack.top() is now " << stack.top() << endl;

    MyStack<char> stack2;

    stack2.push('t');
    stack2.push('s');
    stack2.push('e');
    stack2.push('T');

    while(!(stack2.empty()))
    {
        cout << stack2.top();
        stack2.pop();
    }
    cout << endl;

    stack2.push('A');
    stack2.push('B');
    stack2.push('C');

    stack2.clear();

    stack2.push('D');
    stack2.push('E');
    stack2.push('F');

    while(!(stack2.empty()))
    {
        cout << stack2.top();
        stack2.pop();
    }
    cout << endl;

}

Output:

sum: 105
stack.top() is now 15
Test
FED
\$\endgroup\$
5
\$\begingroup\$

Overall

Not bad.

Resizing.

The maths is in favor of using a refactoring size of less than 1.63 as it potentially allows for memory to be reused after several allocations.

    static const int m_growth_factor = 2;

But on the other hand all the standard libraries do use 2.

Copy and Swap Idiom

    inline MyStack(const MyStack<T> &rhs) { *this = rhs; }

You are defining the copy constructor in terms of the assignment operator. The idiomatic way to do this is the other way around and define the assignment operator in terms of the copy constructor. Its called the copy and swap idiom. It provides the strong exception guarantee (ie the assignment works or the object is unchanged). Your assignment operator does not provide this.

Pre-Allocation

template <class T>
void MyStack<T>::init()
{
    m_array = new T[m_max_size];
    m_count = 0;
}

Here you are pre-allocating an array of T. This means that T must be default constructible (i.e. have a zero parameter constructor). Also if T is expensive to create and you don't use the whole array then you may be creating these object unnecessarily at an expensive point in the code.

You can allocate memory without calling the constructor then use placement new during the push to copy the data into the memory pool.

The same problem also appears in increase_array_size()

Potential Leak.

template <class T>
void MyStack<T>::increase_array_size()
{
    // STUFF

    for(int i = 0; i < m_count; i++)
        tmp[i] = m_array[i];           // If this throws an exception.
                                       // then you are leaking `tmp` pointer.

    // STUFF
}

Potential Invalid object.

template <class T>
void MyStack<T>::increase_array_size()
{
    // STUFF

    delete [] m_array;         // If this throws (because a T destructor throws)
                               // then you leave this object in an undefined
                               // state and you leak the `tmp` pointer.

    // STUFF
}

Use the copy and swap idiom to provide strong exception guarantee. This will also solve the problems in the last two points.

Provide Move Semantics.

This interface provides the standard copy semantics.

template <class T>
void MyStack<T>::push(T data)  // Also not passing by value causes a copy here
                               // So prefer to pass by const reference.
{
    if(m_count == m_max_size)
        increase_array_size();
    m_array[m_count++] = data;
}

But in C++11 we introduced move semantics which is potentially faster than copy semantics and Veridic template also allowing you to build the object in place.

template <typename T>
void MyStack<T>::push(T const& data);    // Copy data into MyStack.
template <typename T>
void MyStack<T>::push(T&& data);         // Move data into MyStack
template <typename... Args>
void MyStack<T>::emplace(Args&&... data);// Build data into MyStack

Assume the user knows the pre-conditions

You can check the pop() operation and throw. But if the user has already checked and knows that the stack is not empty you are doing extra work. For example the user is popping all the values from the stack in a for loop check for empty() in each iteration. Then your check becomes redundant extra work (because empty() was already called).

template <class T>
void MyStack<T>::pop()
{
    if(m_count == 0)
        throw std::underflow_error("Underflow Exception!!!");
    m_count--;

}

So in C++ you usually provide unchecked interface (let the user do the checking).

If you want you can also provide a checked interface then that is fine but usually not the default.

For example look at std::vector. Provides operator[](std::size_t index) for unchecked access to the data. But also provides at(std::size_t index) for checked access to the index.

Un-needed work.

Do you really need to call delete here?

template <class T>
void MyStack<T>::clear()
{
    delete [] m_array;
    m_max_size = m_initial_max_size;
    init();
}

You pre-initialized all the values initially. So you are not reallying on constructor/destructor properties. So this function can be simplified to:

template <class T>
void MyStack<T>::clear()
{
    m_count = 0;
}

If you want to release all the resources and re-create the default versions you can manually destroy all the objects.

Potential Leak.

template <class T>
void MyStack<T>::operator=(const MyStack<T> &rhs)
{
    if(this != &rhs)
    {
        delete [] m_array;                  // You should not delete the current
                                            // state until you know the operation
                                            // has succeeded. If the operation fails
                                            // you currently can not recover your state.

        init();
        for(int i = 0; i < rhs.m_count;i++)
        {
            this->push(rhs.m_array[i]);
        }

    }
}
#endif // MYSTACK_H
\$\endgroup\$
  • \$\begingroup\$ As far as I know, gcc is the only compiler that still uses a factor of 2 when expanding a vector. VC++ has used 1.5 for years, and if memory serves Clang (well, libc++) has used 1.5 for a while. Note that there are reasons to prefer a larger factor though--it does reduce the number of times items get copied. The average number of times elements have been copied always tends toward a constant (with exponential growth) but larger growth factor reduces that constant. \$\endgroup\$ – Jerry Coffin May 25 '16 at 22:52
  • \$\begingroup\$ Variadic templates already came with C++11, see emplace_back and std::make_shared. New with C++14 was std::make_unique, because that was somehow forgotten in 11... Also the suggested emplace should make use of "universal references" and utilize std::forward. \$\endgroup\$ – Felix Bytow May 26 '16 at 7:20
  • \$\begingroup\$ @JerryCoffin: both clang (libc++) ang gcc use 2 on my machine (macbook). \$\endgroup\$ – Martin York May 26 '16 at 14:37
  • \$\begingroup\$ what about the limitation that T must be default constructable? \$\endgroup\$ – Alessandro Teruzzi May 26 '16 at 15:08
  • \$\begingroup\$ @AlessandroTeruzzi: Yes that is a limitation that I mentioned. What about it. new T[m_max_size] Here T must be constructible. Since no parameters can be passed via this type of new it must be default constructible. \$\endgroup\$ – Martin York May 26 '16 at 15:10
4
\$\begingroup\$

First things first: why deal with raw pointers when there is std::vector<T>?

Exception safety

There are regions in your code that might leak memory under certain circumstances.

Example: If T is some class type, its assignment operator might throw an exception. Your increase_array_size member allocates new memory, copies all the values and then deletes the old memory. If during the copying one of the assignment operators throws an exception, the stack is still in sane state, as the old memory is still okay, but the newly allocated memory will be lost forever.

Const correctness

Member functions, that are not supposed to change the object's state, should be declared const. Examples are empty and size. Also your top function could have two overloads:

  • One being const and returning a copy of the top value
  • One being non-const and returning a reference to the top value

Move vs. Copy

For performance reasons it is advisable to prefer moving over copying. The stack class itself should also support moving. Also there are classes like std::unique_ptr<T>, that are movable but not copyable. Your stack should support these types as well.

Sizes

The standard library expresses sizes using std::size_t and so should you. There is no need for negative sizes, so there is no point in using a signed type. Also std::size_t grows to a 64 bit unsigned int when compiling for 64 bits. int stays at 32 bit.

init

Your init function is partially redundant, as all constructors already set m_count to 0. Also you could put its functionality completely into the constructor initialization lists.

for loop

Generally prefer pre-increment:

for (int i = 0; i < size; i++) // bad
for (int i = 0; i < size; ++i) // good

Pre-increment is a free optimization as it does not require more characters to type and no design changes at all. So if you don't need the side effect of post-increment, always use pre-increment. It is always at least as fast as post-increment, but it may be faster.

Also if the order of your loop does not matter and you can make it stop at 0, do so.

for (int i = size; i--;) // post-decrement intended, side effect is used

This is because processors usually can compare to 0 faster.

\$\endgroup\$
  • \$\begingroup\$ Note: The standards committee regrets making the size of containers an unsigned value a mistake. But its to late and they are not going to change it now. \$\endgroup\$ – Martin York May 25 '16 at 20:00
0
\$\begingroup\$

Using exceptions on error is a little harsh. Consider using them only when there is absolutely no way of recovery.

You require T to have (and run) a default constructor. This may or may not be by purpose not knowing your requirements. Personally I think using operator new/delete.

For increasing size I would use memcpy instead of assignment.

Count and max_size may never be negative. Use unsigned types.

New cannot make zero memory. Get some error handling over there. Same goes for deleting unallocated memory. Actually, there are just too many cases of possible errors from (foolish) use for explicitly mentioning all, such as closing without matching init.

\$\endgroup\$
  • \$\begingroup\$ You don't want to use memcpy for templated containers. You may have an optimized specialization for trivially copyable element types that can make use of memcpy. But everything else would be broken. \$\endgroup\$ – Felix Bytow May 26 '16 at 7:22
  • \$\begingroup\$ @FelixBytow Thank you for your comment. Care to elaborate how it would be broken? My point was resize being a memory domain operation and should thus not have type dependent behavior. If allowing specialized copy, the container may contain something else after resize which is never what you want. Right? \$\endgroup\$ – Andreas May 26 '16 at 9:43
  • \$\begingroup\$ Lets say you habe a vector<string> and that would use memcpy instead of the assignment operator. Now the old and the new strings would both contain the same pointers. When deleting the old strings, the new ones will be left with dangling pointers. When these are deleted, your application most likely crashes. \$\endgroup\$ – Felix Bytow May 26 '16 at 13:09
  • \$\begingroup\$ @FelixBytow True if you call constructors/destructors, which you don't if using ::operator new/delete. I should have been more clear on that being important... Sorry. If constructor/destructor of T is omitted on resize, do you agree memcpy is a valid course of action? (Albeit maybe not what you personally may prefer) \$\endgroup\$ – Andreas May 26 '16 at 13:21
  • \$\begingroup\$ Sure, if you implement it bug free, then yes, it is a valid course of action. Still that does not mean one should do that. IMHO this looks like premature optimization. \$\endgroup\$ – Felix Bytow May 26 '16 at 13:39

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.