Deleting arrays, or deallocating memory, C++ bug

Question

Below is a snippet of my code for a stack data structure that I am trying to implement.

For some reason when I delete currentArray, newArray is deleted too, because the code below is giving me a run-time bug where the contents of newArray and currentArray are garbage values.

I'm not sure why this is happening.

Would greatly appreciate any insight as to why I am getting this bug, and if my push() implementation below is on point from a fundamental perspective.

// Destructor
~Stack() 
{
    if ((size > 0) && (currentArray) != NULL && (newArray != NULL))
    {
        delete[] currentArray;
        delete[] newArray;
    }
}

inline void push(T value)
{
    if (isEmpty())
    {
        // Stack size is increased by 1
        size++;

        currentArray = new T[size];
        currentArray[size - 1] = value;
    }
    else
    {
        // Stack size is increased by 1
        size++;

        // Create the new array
        newArray = new T[size];

        // Copy the contents of the old array into the new array
        copy(currentArray, currentArray + size, newArray);

        // Push the new value on to the new array
        newArray[size - 1] = value;

        // Copy the new array into the current
        currentArray = new T[size];
        currentArray = newArray;
    }
}

Answer 1

In your push function, in the else block you do

currentArray = newArray;

So both your currentArray and newArray are pointing to the same thing! (which you are doing yourself).

So, when you do delete [] currentArray you need not delete newArray since that memory has already been deleted. And that is why your program gives a fault that you are trying to delete memory which has already been deleted!!

Moreover in your push function you do ::

currentArray = new T[size];
currentArray = newArray;

I believe in your class, currentArray is a pointer and new also returns the pointer to the newly allocated memory. So, if you want your currentArray to point to the newArray, you simply need to do currentArray = newArray without allocating memory to the currentArray.

Further, you also do ::

 newArray = new T[size];
 copy(currentArray, currentArray + size, newArray);

inside your if block, I believe you are copying the data currentArray to a newArray so, after you have copied the data from currentArray to newArray you need to delete previously allocated memory to the currentArray, otherwise it is a memory-leak (A failure in a program to release discarded memory, causing impaired performance or failure). It is always to good to delete memory which is of no use.

So, I would recommend you add delete [] currentArray statement after this.

So, your final code shall look something like this ::

// Destructor
~Stack() 
{
    /*
     *if ((size > 0) && (currentArray) != NULL) --> 
     *deleting a NULL pointer is completely defined!
     *So, in your constructor if you are initializing 
     *currentArray to NULL you need not have any if condition.
    */
    delete[] currentArray;
}

inline void push(T value)
{
    if (isEmpty())
    {
        size++;

        currentArray = new T[size];
        currentArray[size - 1] = value;
    }
    else
    {
        size++;

        newArray = new T[size];

        copy(currentArray, currentArray + size, newArray);

        delete [] currentArray; //EDIT

        newArray[size - 1] = value;

        //currentArray = new T[size]; --> Deleted Line
        currentArray = newArray;
    }
}

NOTE :: Just in case your compiler is in compliance with C++11, you shall consider using nullptr over NULL, here is why : What are the advantages of using nullptr?

Answer 2

Firstly, you don't need the checks in the destructor.

~Stack() {
    delete [] currentArray;
    delete [] newArray;
}

The push has several problems:

1. You pass value by value, which might be expensive. You should pass by reference.
2. You use size in the copy() after incrementing it, which means you're copying raw memory into the last slot of newArray. This might be benign (T = int + a bit of luck) or disastrous (T = std::string).
3. newArray is only needed inside push(). It should be a local variable, not a member variable.
4. You grow by 1 each time, which results in O(n²) time to populate. You should grow geometrically, which requires an additional capacity member variable.
5. You invoke new T[size] twice. One of them leaks.

Here's a reworked version:

class Stack {
public:
    …
    inline void push(const T& value) {
        if (size_ == capacity_) {
            capacity_ = capacity_ ? capacity_ * 2 : 1;
            T* dest = new T[capacity_];
            copy(data_, data_ + size_, dest);
            delete [] data_;
            data_ = dest;
        }
        data_[size_++] = value;
    }
    …
private:
    T* data_ = nullptr;
    size_t size_ = 0, capacity_ = 0;
};

This is not by any means a solid, industrial-strength piece of code. It doesn't address exception safety, copy-avoidance (requiring, among other things, an additional overload: push(T&& value)), and a range of other subtleties. In fact, I haven't even checked that it compiles! It might do for a toy project, but in the real world you should simply use std::stack.

Answer 3

Maybe I'm missing something, but if the if statement proves true, it deletes both anyhow.

Also, from a basic perspective, why wouldn't you have:

if ((size > 0) && (currentArray != NULL) && (newArray != NULL))

It's not a huge deal, but mismatched parentheticals are the enemy.

Answer 4

@user007 this is my pop() function.

// Remove an element from the stack
inline const T& pop()
{
    if (size > 0)
    {
        T value;

        size--;

        value = data[size];

        T* dest = new T[size];

        // Copy the contents of the old array into the new array
        copy(data, data + (size), dest);

        delete[] data;

        data = dest;

        return value;
    }

    return NULL;
}