Resize into dynamic pointer turns dimension into garbage

Question

I was responding to an implementation problem of Std::stack. It was easy, but I couldn’t use my first idea: Std::vector (replaced dynamic pointers forever). My code is:

template <class T> class stack
{
    T* data;
    unsigned size_;

    public:
    stack() : size_(0){}
    stack(T initializer, unsigned times)
    {
        size_ = times;
        data = new T[times];
        for(int i = 0; i < times; i++) data[i] = initializer;
    }

    void push(T data_)
    {
        size_++;
        data = new T[size_];
        data[size_-1] = data_;
    }
    void pop()
    {
        size_--;
        data = new T[size_];
    }
    T top() const
    {
        return data[size_-1];
    }
    void clear()
    {
        for(unsigned i = 0; i < size_; i++)
        {
            data[i] = 0;
        }
    }
    bool empty() const
    {
        bool ret = true;
        for(unsigned i = 0; i < size_; i++)
        {
            if(data[i] != 0)
            {
                ret = false;
                break;
            }
        }
        return ret;
    }
    unsigned size() const
    {
        return size_;
    }
    void resize(unsigned newsize)
    {
        size_ = newsize;
        data = new T[size_];
    }
};

I decided to test with an integer; and it worked. However, I did a size 2 and decided to test the pop method.

int main()
{
    stack<unsigned> A;
    A.push(10);
    A.push(2);
    std::cout << A.top() << "\n";
    A.pop();
    std::cout << A.top();
}

Then the top method returns trash. What I’m doing wrong?

Answer 1

The first point we can improve is your memory allocation. Allocating and dislocating every operation works, but is not efficient. A good solution is to allocate a larger block than needed initially, and make new allocations only when it is full, just as it is done in std::vector. For this we need to add a field capacidade stacked:

T *m_data;
std::size_t m_size;
std::size_t m_capacity;

Initialize everything with null and zeros. The push and the pop can look like this then:

void push(const T &value) {
  if (m_capacity == 0) {
    m_capacity = 1; //Capacidade mínima
    m_data = new T[1];
  }
  else if (m_size == m_capacity) {
    T *old = m_data; //Guarda ponteiro
    m_capacity *= 2; //Dobra capacidade
    m_data = new T[m_capacity]; //Aloca novo array
    std::copy(old, old+m_size_, m_data); //Copia dados
    delete[] old; //Libera array antigo
  }
  m_data[m_size] = value; //Guarda novo valor
  ++ m_size; //Incrementa tamanho
}

void pop() {
  --m_size; //Basta decrementar o tamanho
}

No need to dislocate in the pop, 'cause when there’s a new push it will take advantage of the old array. But you can create a function trim to eliminate unnecessary space.

void trim(const T &value) {
  if (m_capacity == m_size) {
    return;
  }
  T *old = m_data; //Guarda ponteiro
  if (m_size == 0) {
    m_data = NULL; //Para tamanho zero o array é nulo
  }
  else {
    m_data = new T[m_size]; //Aloca novo array
    std::copy(old, old+m_size_, m_data); //Copia dados
  }
  m_capacity = m_size; //Guarda novo valor de capacidade
  delete[] old; //Libera array antigo
}

You should obviously not forget to delete the array in the destructor. A copy constructor and assignment operator are also required, and if you are already with c++11 you can make the drive assignment constructor and operator also.

The other point is your duties clear and empty. They put the value zero on the stack, and check the amount of that value. This way you can’t tell the difference between an empty stack and a full of zeros. No clearyou should just reset the m_size and in the empty just make sure he’s zero.

void clear() {
  m_size = 0;
}

bool empty() {
  return m_size == 0;
}

Now it would only be enough to add functions to access the elements by index that would practically have a reimplementation of std::vector for simple types. To be complete it would be necessary to allocate raw array memory and build and destroy objects manually (constructor placement and explicitly called the destructor) so that objects are not created before the time nor continue to exist after the necessary.

Answer 2

With the help of @C.E.Gesser, I tidied up (forgot how to resize correctly), I tidied up the code. It looked like the following:

#include <iostream>
#include <algorithm>
template <class T> class stack
{
    T* data;
    unsigned size_;

    public:
    stack() : size_(0){}
    stack(T initializer, unsigned times)
    {
        size_ = times;
        data = new T[times];
        for(int i = 0; i < times; i++) data[i] = initializer;
    }

    void push(T data_)
    {
        T* temp = new T[size_ + 1];
        std::copy(data, data+size_, temp);
        size_++;
        data = new T[size_];
        std::copy(temp, temp+size_, data);
        data[size_-1] = data_;
    }
    void pop()
    {
        T* temp = new T[size_-1];
        std::copy(data, data+(size_-1), temp);
        size_--;
        data = new T[size_];
        std::copy(temp, temp+size_, data);
    }
    T top() const
    {
        return data[size_-1];
    }
    void clear()
    {
        for(unsigned i = 0; i < size_; i++)
        {
            data[i] = 0;
        }
    }
    bool empty() const
    {
        bool ret = true;
        for(unsigned i = 0; i < size_; i++)
        {
            if(data[i] != 0)
            {
                ret = false;
                break;
            }
        }
        return ret;
    }
    unsigned size() const
    {
        return size_;
    }
    void resize(unsigned newsize)
    {
        size_ = newsize;
        data = new T[size_];
    }
};

int main()
{
    stack<unsigned> A;
    A.push(10);
    A.push(2);
    std::cout << A.top() << "\n";
    A.pop();
    std::cout << A.top();
}