C++ Dynamic array based stack

Question 1

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: 105stack.top() is now 15TestFED

Question 2

This is worth a read.lokiastari.com/blog/2016/02/27/vector There are four articles in the series (see the panel on the right).

Question 3

This is worth reading for you resize factor.lokiastari.com/blog/2016/03/25/resizemaths Apparently 1.5 is better than 2.

Question 4

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 ofT. This means thatT must be default constructible (i.e. have a zero parameter constructor). Also ifT 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 inincrease_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 MyStacktemplate <typename... Args>void MyStack<T>::emplace(Args&&... data);// Build data into MyStack

Assume the user knows the pre-conditions

You can check thepop() 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 forempty() in each iteration. Then your check becomes redundant extra work (becauseempty() 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 atstd::vector. Providesoperator[](std::size_t index) for unchecked access to the data. But also providesat(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

Question 5

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.

Question 6

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.

Question 7

@JerryCoffin: both clang (libc++) ang gcc use 2 on my machine (macbook).

Question 8

what about the limitation that T must be default constructable?

Question 9

@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.

Question 10

First things first: why deal with raw pointers when there isstd::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.Yourincrease_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 areempty andsize.Also yourtop 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 likestd::unique_ptr<T>, that are movable but not copyable.Your stack should support these types as well.

Sizes

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

init

Yourinit function is partially redundant, as all constructors already setm_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++) // badfor (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.

Question 11

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.

Question 12

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.

Question 13

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.

Question 14

@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?

Question 15

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.

Question 16

@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)

Question 17

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.

Loki Astari 97.7k5 gold badges126 silver badges341 bronze badges · Accepted Answer · 2016-05-26 14:39:32Z

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 ofT. This means thatT must be default constructible (i.e. have a zero parameter constructor). Also ifT 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 inincrease_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 MyStacktemplate <typename... Args>void MyStack<T>::emplace(Args&&... data);// Build data into MyStack

Assume the user knows the pre-conditions

You can check thepop() 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 forempty() in each iteration. Then your check becomes redundant extra work (becauseempty() 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 atstd::vector. Providesoperator[](std::size_t index) for unchecked access to the data. But also providesat(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

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.
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.
@JerryCoffin: both clang (libc++) ang gcc use 2 on my machine (macbook).
what about the limitation that T must be default constructable?
@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.

Movatterモバイル変換

Stack Exchange Network

C++ Dynamic array based stack

3 Answers3

Overall

Resizing.

Copy and Swap Idiom

Pre-Allocation

Potential Leak.

Potential Invalid object.

Provide Move Semantics.

Assume the user knows the pre-conditions

Un-needed work.

Potential Leak.

You mustlog in to answer this question.

Linked

Related

Hot Network Questions

Subscribe to RSS