2
\$\begingroup\$

I implemented a Stack in C++ using a dynamic C-style array. I tried sticking to the most important functions a Stack has to have to be usable. This is meant to only be for integers. I appreciate any suggestions on how to improve this. Here is my code:

Stack.h

#ifndef STACK_H
#define STACK_H
#include <cstdint>
#include <algorithm>

class Stack
{
public:
    Stack(int32_t u_size = 10) : m_current_ind{ -1 }, m_size{ 0 }, m_capacity{ u_size }{  // constructor
        m_stack_arr = new int32_t[u_size];
    };
    ~Stack() {                                                                     // destructor
        delete[] m_stack_arr;
    };
    Stack(const Stack& other) : m_current_ind{ -1 }, m_size{ 0 }, m_capacity{ 0 }{        // copy constructor
        for (int32_t i = 0; i < other.size(); i++)
        {
            push(other.m_stack_arr[i]);
        }
    }
    Stack(Stack&& other) : m_current_ind{ -1 }, m_size{ 0 }, m_capacity{ 0 }{             // move constructor
        m_stack_arr = std::exchange(other.m_stack_arr, nullptr);
    }
    Stack& operator=(const Stack& other) {                                         // copy assignment operator
        if (this != &other)
        {
            clear();
            for (int32_t i = 0; i < other.size(); i++)
            {
                push(other.m_stack_arr[i]);
            }
        }
        return *this;
    }
    Stack& operator=(Stack&& other) {                                              // move assignment operator
        if (this != &other)
        {
            m_stack_arr = std::exchange(other.m_stack_arr, nullptr);
            m_size = other.m_size;
            m_capacity = other.m_capacity;
            m_current_ind = other.m_current_ind;
        }
        return *this;
    }
    void clear(int32_t new_capacity = 10); // clear stack and initialise new empty array
    bool is_empty() const; // check if stack is empty
    int32_t pop(); // delete value on top and return it
    int32_t peek() const; // return value on top of the stack
    void push(int32_t u_value); // add value to stack
    int32_t size() const; // return size

private:
    void extend(); // double capacity

    int32_t m_current_ind;
    int32_t m_size;
    int32_t m_capacity;
    int32_t* m_stack_arr;
};

#endif

Stack.cpp

#include "Stack.h"
#include <stdexcept>

void Stack::clear(int32_t new_capacity)
{
    delete[] m_stack_arr;
    m_stack_arr = new int32_t[new_capacity];
    m_capacity = new_capacity;
    m_current_ind = -1;
    m_size = 0;
}

bool Stack::is_empty() const
{
    return !m_size;
}

int32_t Stack::pop()
{
    if (!is_empty())
    {
        m_size--;
        return m_stack_arr[m_current_ind--];
    }
    throw std::out_of_range("Stack is already empty.");
}

int32_t Stack::peek() const
{
    if (!is_empty())
    {
        return m_stack_arr[m_current_ind];
    }
    throw std::out_of_range("Stack is empty.");
}

void Stack::push(int32_t u_value)
{
    m_size++;
    m_current_ind++;
    if (m_size > m_capacity)
    {
        extend();
    }
    m_stack_arr[m_current_ind] = u_value;
}

int32_t Stack::size() const
{
    return m_size;
}

void Stack::extend()
{
    int32_t* temp = new int32_t[m_capacity * 2];
    m_capacity *= 2;
    std::copy(m_stack_arr, m_stack_arr + m_size, temp);
    delete[] m_stack_arr;
    m_stack_arr = temp;
}
```
\$\endgroup\$
1
  • \$\begingroup\$ The copy constructor is broken, because the first push will call extend, doubling the capacity. But since the capacity was set to 0 you don't get any usable storage space. \$\endgroup\$ – 1201ProgramAlarm Dec 9 '20 at 1:49
2
\$\begingroup\$

Prefer std::vector to dynamic allocation

I understand this project was meant for practice, I have done a similar project, who wouldn't want to mess around with memory allocation, but doing so leads to errors when the programmer is not careful or chooses to ignore certain things. Using std::vector gives you the following for free

  1. Copy constructor
  2. Copy assignment
  3. Move constructor
  4. Move assignment

This enables you to focus more on the business logic of the problem.

Stack class does not cater for default constructed objects

Right now, your class assumes that users do not have default constructible objects. This is okay because you are holding Integral values, but you might change it in the future. The following

int *p = new int{}

allocates and construct an int in memory, this is okay for int because it has a default constructor. Your class might hold objects that are very expensive to construct and as such, users might need to just have a stack that can hold their default constructible objects and construct them when they are needed. This give rise to placement new, see more about placement new here

CODE REVIEW

  1. In Stack constructor, you declared the following
Stack(int32_t u_size = 10)

This is okay, you want a default stack to have 10 elements, A better approach is to declare a default stack to hold 0 elements, this is the behavior of std::vector. The stack can grow when necessary. If the user wants to explicitly request for space, declare a reserve method that allocates space. You might also consider a shrink_to_fit method, well am going overboard for a simple stack class.

  1. You forgot to allocate memory in your copy constructor. This is dangerous, you are reading into memory that was never allocated. The result is undefined, it might work today and crash tomorrow. A correct approach is this
 Stack(const Stack& other) : m_current_ind{ -1 }, m_size{ 0 }, m_capacity{ other.m_capacity } {        // copy constructor
    m_stack_arr = new int32_t[other.m_size];
    for (int32_t i = 0; i < other.size(); i++)
    {
        push(other.m_stack_arr[i]);
    }
}

Now this is better, we explicitly created m_stack_arr.

  1. Move constructor does not work. On testing your move constructor, I resulted to a segmentation fault. m_size was not given the appropriate size, the same case with m_capacity. using a swap method, your move constructor can be defined as follow
void swap(Stack& lhs, Stack& rhs)
{
    using std::swap;
    swap(lhs.m_current_ind, rhs.m_current_ind);
    swap(lhs.m_size, rhs.m_size);
    swap(lhs.m_capacity, rhs.m_capacity);
    swap(lhs.m_stack_arr, rhs.m_stack_arr);
}

This method just swap the internal representation of objects. Using this method, move constructor and move assignment becomes easy

Stack(Stack&& other) noexcept {             // move constructor
    swap(*this, other);
    other.m_stack_arr = nullptr;
}

We set the value of other.m_stack_arr to a nullptr to make it a cheap resource for the compiler to destroy.

Move assigment is also similar, a self move is not bad and no need for a check here.

Stack& operator=(Stack&& other) noexcept { 
    swap(*this, other);
    other.m_current_ind = -1;
    other.m_size = 0;
    other.m_stack_arr = nullptr;
    return *this;
}

Both methods are marked noexcept because we are guaranteed that move assignment and move constructor would not throw an exception, this gives room for compiler to optimize some certain things.

  1. In clear method, you delete m_stack_arr before allocating a new one, what if new throws an exception, you have lost m_stack_arr.
void Stack::clear(int32_t new_capacity)
{
    int32_t* temp_arr; = new int32_t[new_capacity];
    delete[] m_stack_arr;
    std::copy(m_stack_arr, m_stack_arr + m_size, temp_arr);
    
    //.. Your code goes in here
}

Here we created our memory and store it temp_arr, if that doesn't throw, we delete our old array and copy the new one. A more optimized version would be to use memcpy to copy the bytes from memory, but that is a different topic entirely.

\$\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.