What's the correct way to free the memory here? The pointer-array contains duplicates!
class HashTable
{
Bucket<E>** index = new Bucket<E>*[indexSize];
...
}
~ExtHash( )
{
for (size_t i = 0; i < indexSize; ++i)
delete index[i];
delete[] index;
}
I would think hard about whether you want this container to be responsible for deleting the objects; it would be simpler to store them elsewhere, and just use this container to refer to them, not to manage their lifetimes.
Alternatively, you could use std::shared_ptr to manage the objects; then they will be deleted automatically when you've discarded all of them.
If you really want to do it this way, you'll need to remove the duplicates after deleting each one; something like
for (size_t i = 0; i < indexSize; ++i) {
Bucket<E> * victim = index[i];
indexSize = std::remove(index+i+1, index+indexSize, victim) - index;
delete victim;
}
[NOTE: this code may well be wrong; I certainly made a couple of mistakes writing it. If you really want to manage dynamic objects the hard way, then you'll need to test it thoroughly]
Sort index, remove adjacent duplicates with std::unique. O(N log N) and that's as good as it gets.
Use a set to remove duplicates:
std::set<Bucket*> uniqueBuckets(index, index + indexSize);
for(Bucket* bucket: uniqueBuckets)
delete bucket;
In your situation it's dangerous to store raw pointers in such way. Better use std::shared_ptr and just reset shared pointers. And after all pointers will be reseted they will be safely freed.
Perhaps like this:
~ExtHash( )
{
std::sort(index, index + indexSize);
size_t new_end = std::unique(index, index + indexSize) - index;
for (size_t i = 0; i < new_end; ++i)
delete index[i];
delete[] index;
}
Each time you create a pointer, push_back it into a vector. That vector will hold all your created pointers, and will hold each one of them only once.
Later, iterate that vector and delete the pointers.
It's like writing your own simple garbage collector.
new and delete at all; the list will automatically destroy them for you.