How to delete a dynamic array of objects with pointers to other objects (C++)

Question

Long story short, I have to code a hashtable using linear hashing in C++ for university. The hashtable works, but the ressources are not being freed which is an issue, especially that the unit test tests the table with 100k+ values and the garbage left behind is huge. Basically when I'm creating the new hashtable I am doing the following:

hashTable = new Bucket[this->tableSize];
        for (size_t i = 0; i < tableSize; i++) {
            hashTable[i] = * new Bucket();
        }

Each Bucket can contain a pointer to another overflow bucket, which may or may not be set.

    class Bucket {
    private:
        size_t bucketSize;                                                                   
        size_t elementsInBucket;                                                              
        E v[N];   // int v[N];                                                              
        bool hasOverflow;                                                                     
        Bucket * nextBucket = nullptr; 

My question is, how can I delete the whole hashtable including the buckets with their potential overflow buckets as the following only frees half of the occupied memory.

delete[] hashTable;
hashTable = nullptr;

Thanks!

Answer 1

Unless I'm mistaken, the following line of code is a memory leak:

hashTable[i] = * new Bucket();

What you are doing here is allocating a new Bucket object on the heap, then immediately copying it by value into your array. The pointer you created with new falls out of scope, and the original Bucket on the heap is leaked. What you have remaining is a copy of what you just allocated in the heap and leaked.

Instead, you should store the pointers in your array as such:

hashTable = new *Bucket[this->tableSize];
for (size_t i = 0; i < tableSize; i++) {
    hashTable[i] = new Bucket();
}

and delete it as such:

for (size_t i = 0; i < tableSize; i++) {
    delete hashTable[i];
    hashTable[i] = nullptr;
}
delete[] hashTable;
hashTable = nullptr;

You should also make sure your destructor deletes the member pointer so that when you call delete on each Bucket pointer the nested memory is deallocated:

~Bucket() { 
    delete nextBucket;
    nextBucket = nullptr; 
}

Last, you will need to change any code that does this:

hashTable[i].something

to this:

hashTable[i]->something

This seems to me to be the proper way to handle dynamic arrays.