CODEWITHSUNDEEP
c++arraysmemoryallocation
Django
Django

Reputation: 381

Why does deleting an allocated array cause a memory error?

I implemented an ArrayList class for education purposes but I am running into a memory error when deleting the array in my expand() method.

Here is my class and all important methods:

//create array with default size 2
template<class T>
ArrayList<T>::ArrayList(){
    realSize = 2;
    count = 0;
    data = new T[realSize];
}

//destructor
template<class T>
ArrayList<T>::~ArrayList() {
    delete []data;
}

//adds value to end of list
template<class T>
void ArrayList<T>::add(T val) {
    //if reached end of array, expand array
    if (count >= realSize)
        expand();
    data[count] = val;
    count++;
}

//inserts value at index
template<class T>
void ArrayList<T>::insert(T val, int index) {
    if (!isValid(index)) return;
    //if index is greater than current size, expand
    while (index >= realSize || count >= realSize) {
        expand();
    }
    //shift values before index
    for (int i = count; i >= index; i--) {
        T val = data[i];
        data[i + 1] = data[i];
    }
    data[index] = val;
    count++;
}

//return value at index
template<class T>
T ArrayList<T>::get(int index) {
    if (!isValid(index)) return 0;
    return data[index];
}

template<class T>
int ArrayList<T>::size() {
    return count;
}

template<class T>
void ArrayList<T>::expand() {
    //double array size
    realSize = realSize * 2;
    T* newData = new T[realSize];
    //replace data
    for (int i = 0; i < count; i++) {
        newData[i] = data[i];
    }
    delete[]data; //<--ERROR OCCURS HERE
    data = newData;
}

Here is some code that will cause the bug

    ArrayList<int>* list = new ArrayList<int>();

    list->add(1);
    list->add(5);
    list->insert(2, 1);
    list->insert(3, 2);
    list->insert(4, 3); //<---ERROR OCCURS HERE

The error is a message box that reads

Debug Error!

Program: ...ommunity\Common7\IDE\Extensions\TestPlatorm\testhost.x86.exe

HEAP CORRUPTION DETECTED: after Normal block (#296) at 0x05D69BC0

CRT detected that the application wrote to memory after end of heap buffer.

Why would this cause an error occasionally when calling the expand method? As far as I can tell, the array is in expected order when expand() is called (in my example, it is {1, 2, 3, 5}).

Upvotes: 0

Views: 163

Answers (1)

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

The problem is in the insert method. When you are copying the existing elements up to make space for the new element, you start at element count, and copy data[count] up one slot to data[count + 1]. However, no element has been stored at data[count] and under the correct circumstances the access to data[count + 1] will access past the space allocated for data.

Those circumstances happen with the second insert call. count is 3, realsize is 4, and index is 2, so no expansion happens. Your for loop will then assign data[count + 1] = data[count], which is data[4] = data[3]. Since data only has space for 4 elements, writing to data[4] clobbers data past the end of the allocated space, which is detected on a later memory operation (in this case, when the allocated space is freed via a call to delete).

The solution is to start your loop at int i = count - 1, or decrement it in the condition:

for (int i = count; --i >= index; )

Unrelated, the T val = data[i]; declaration does nothing useful and can be removed.

Upvotes: 2

Related Questions