dynamic array in c++: valgrind leak

Question

I'm trying to implement a dynamic array in c++. once it becomes full, its size is doubled and is copied to the double-sized array. it looks fine but Valgrind says I have a leak. I should say that I'm not allowed to use any of c++ STL structures- that's why I'm using new[] and delete[] operators.

this is my code:

template<class T>
class DynamicArray
{

    int size;
    int numOfElements;
    T* arr;

public:
    DynamicArray(int size) :
            size(size), numOfElements(0)
    {
        arr = new T[size];
    }
    ;

    int getSize()
    {
        return size;
    }

    int getNumberOfElements()
    {
        return numOfElements;
    }

    void insert(T element)
    {
        arr[numOfElements++] = element;
        if (numOfElements == size)
        {
            T* extended_array = new T[size * 2];
            for (int i = 0; i < numOfElements; i++)
            {
                extended_array[i] = arr[i];
            }
            delete[] arr;
            arr = extended_array;
            size = size * 2;
        }
    }

    T& operator[](int i)
    {
        if (!((i >= 0) && (i < size)))
            throw arrayOutOfBoundsException();
        return arr[i];
    }

    ~DynamicArray()
    {
        delete[] arr;
    }

    class arrayOutOfBoundsException: std::exception
    {
    };
};

My main program is:

using std::cout;
using std::endl;

void printIntArray(DynamicArray<int> arr){
    cout << "size: " << arr.getSize() << ";  " << "numOfElemnts: " << arr.getNumberOfElements() << endl;
    cout << "array: ";
    for(int i=0; i<arr.getNumberOfElements(); i++){
        cout << " " << arr[i];
    }
    cout << endl << endl;
}


int main() {

    DynamicArray<int> arr(5);
    printIntArray(arr);



    arr.insert(1);
    arr.insert(2);
    arr.insert(3);
    printIntArray(arr);

    arr.insert(4);
    printIntArray(arr);

    arr.insert(5);
    printIntArray(arr);

    arr.insert(6);
    printIntArray(arr);

    arr.insert(7);
    arr.insert(8);
    arr.insert(9);
    printIntArray(arr);

    arr.insert(16);
    printIntArray(arr);

    arr[9] = 901;
    arr[0] = 101;
    printIntArray(arr);

**valgrind shows me this error- when the destructor is compiled as comment:

==3954== 80 bytes in 1 blocks are definitely lost in loss record 1 of 1
==3954==    at 0x4A07192: operator new[](unsigned long) (vg_replace_malloc.c:363)
==3954==    by 0x40103E: DynamicArray<int>::insert(int) (DynamicArray.h:41)
==3954==    by 0x400DBC: main (main.cpp:44)**

Can anybody tell me what I was doing wrong? am I misusing "delete[]"? or the destructor?

thanks

Answer 1

The behaviour described by the asker is impossible or

when the destructor is compiled as comment:

means the destructor has been commented out and this is causing the leak. This has been confirmed in a comment. Without the destuctor the last allocation will never be put away.

The Asker's real problem is a Rule of Three Violation.

The short version goes something like this:

If a class requires a user defined copy constructor, assignment operator, or destructor it almost always requires all three.

More on that here: What is The Rule of Three?

In this case,

void printIntArray(DynamicArray<int> arr)

accepts arr by value. This means arr is a copy of the value passed in. In the absence of a custom copy constructor the arr inside printIntArray will point to the same allocation as the source. The copy will be destroyed at the end of printIntArray, and the destructor will delete the allocation, leaving the source pointing to invalid memory so...

DynamicArray<int> arr(5); // allocated storage inside arr
printIntArray(arr); // made a copy of arr that points to same storage. 
                    // Storage freed when copy destroyed

arr.insert(1); // invokes undefined behaviour writing into invalid memory
arr.insert(2); // same
arr.insert(3); // same
printIntArray(arr); // copies arr again. This copy is pointing to the same invalid memory
                    // and will try to free the allocation a second time when the 
                    // copy is destroyed

The program will almost certainly crash here, making it impossible to leak from the users code. But because the program crashed, Crom only knows what behind-the-scenes structures the runtime was using were not correctly put away.

Whatever happened, as of

arr.insert(1);

the program was deep in Undefined Behaviour and whatever happens after that is anybody's guess. Memory leaks are the least of your worries.

Fixing: Satisfy the Rule of Three

Implement a copy constructor and an assignment operator (We'll ignore the Rule of Five for now.)

You could change

void printIntArray(DynamicArray<int> arr)

to pass by reference

void printIntArray(DynamicArray<int> & arr)

and then

DynamicArray(const DynamicArray &) = delete;
DynamicArray& operator=(const DynamicArray &) = delete;

and disable all copying, but this seems a bit draconian.

Instead lets use Copy and Swap because it's simple and easy to understand. Note that it can also be inefficient, so it's not always the right tool. Here it fits what we want.

DynamicArray(const DynamicArray & src)  :
        size(src.size), numOfElements(src.numOfElements), arr(new T[size])
{
    for (int i = 0; i < numOfElements; i++)
    {
        arr[i] = src.arr[i];
    }
}


DynamicArray& operator=(const DynamicArray src)
{
    std::swap(size, src.size);
    std::swap(numOfElements, src.numOfElements);
    std::swap(arr, src.arr);
    return *this;
}

And because who wants to copy they don't need to we'll still

void printIntArray(DynamicArray<int> & arr)

as soon as we're done testing that the copy constructor works correctly.