Wie lösche ich ein dynamisches Array von Objekten mit Zeigern zu anderen Objekten (C++)

Question

Lange Rede kurzer Sinn, ich muss eine Hashtabelle mit linearem Hashing in C++ für die Universität kodieren. Die Hashtabelle funktioniert, aber die Ressourcen werden nicht freigegeben, was ein Problem darstellt, insbesondere, dass der Komponententest die Tabelle mit 100k + Werten testet und der zurückgelassene Müll riesig ist. Grundsätzlich, wenn ich den neuen Hash-Tabelle bin die Schaffung ich folgendes tue:

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

Jeder Eimer kann einen Zeiger auf einen anderen Überlauf Eimer enthalten, die so eingestellt werden kann oder nicht.

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

Meine Frage ist, wie kann ich die ganze hashtable einschließlich der Eimer mit ihren potentiellen Überlauf Eimer löschen, wie die folgenden nur die Hälfte des belegten Speicher freigibt.

delete[] hashTable; 
hashTable = nullptr; 

Vielen Dank!

Answer 1

Wenn ich mich nicht irre, die folgende Codezeile ein Speicherverlust ist:

hashTable[i] = * new Bucket(); 

Was Sie hier tun, ist ein neues Bucket-Objekt auf dem Heap zuzuweisen und dann sofort nach Wert in Ihr Array zu kopieren. Der mit new erstellte Zeiger fällt nicht in den Geltungsbereich und der ursprüngliche Bucket auf dem Heap wird durchgesickert. Was Sie übrig haben, ist eine Kopie von dem, was Sie gerade im Heap zugeordnet und durchgesickert.

Stattdessen sollten Sie die Zeiger im Array als solche speichern:

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

und löschen Sie es als solche:

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

Sie sollten auch Ihre destructor löscht den Elementzeiger so stellen Sie sicher, dass Wenn Sie bei jedem Bucket-Zeiger delete aufrufen, wird der verschachtelte Speicher freigegeben:

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

L ast, müssen Sie einen Code ändern, das dies tut:

hashTable[i].something 

dazu:

hashTable[i]->something 

Dies scheint mir der richtige Weg zu sein, dynamische Arrays zu handhaben.

Answer 2

Du sofort ein Bucket auf dieser Linie undicht:

hashTable[i] = * new Bucket(); 

Was das bedeutet ist:

1. Vergeben Sie einen neuen Bucket und liefern einen Zeiger auf sie
2. Dereferenziere der zurückgegebene Zeiger und übergeben Sie einen Verweis auf Ihre neue Bucket zu Bucket::operator=
3. Kopieren Sie die leere Bucket in das bereits vorhandene Objekt hashTable[i]
4. Verwerfen Sie den Zeiger auf die neu zugewiesene Bucket, wodurch es

hashTable ist ein Zeiger auf das erste Element aus einer Anordnung von tableSizeBucket s undicht. Diese Objekte sind bereits vorhanden, sodass Sie keine neuen Objekte in Ihrer Schleife zuweisen müssen.

Darüber hinaus haben Sie keinen Destruktor für Bucket angezeigt oder gezeigt, wie Sie Bucket::nextBucket zuweisen. Ich gehe davon aus jeder Bucket sollte seine nextBucket besitzen, so sollten Sie eine destructor haben, die so etwas wie

tut

Bucket::~Bucket() 
{ 
    delete nextBucket; 
}