Speicherleck in Hashtable/Doppelt verkettete Liste

Question

Ich arbeite für meine CS-Klasse und wir entwickeln unsere eigene einfache Hashtabellen-Implementierung. Zu diesem Zweck habe ich mehrere Klassen:

• Liste (Dies ist eine doppelt verknüpfte Liste)
• Hashtable (Dies ist eine einfache Hash-Tabelle mit einer flexiblen Anzahl von Schlitzen)
• Tester (Dies ist eine Testklasse die die Schlüsselvergleiche zählt und für eine Reihe von Fällen in eine CSV-Datei druckt)

Der Tester generiert für jeden Lauf eine neue Hashtabelle. Wenn ich zum Beispiel einen Test von 100 Läufen für jeden Lauf durchführe, wird eine neue Hashtabelle erstellt, nachdem die alte gelöscht wurde. Dies wird benötigt, da sich normalerweise die Anzahl der Steckplätze für die Tests ändert.

In jedem Slot der Hashtabelle befindet sich ein Zeiger auf eine doppelt verknüpfte Liste, die im Konstruktor der Hashtabelle erstellt wird. Die Liste bietet Methoden zum Einfügen von Werten, zum Suchen nach Werten, zum Abrufen der Schlüsselvergleiche für die letzte Suche und zum Löschen aller Elemente. Der Destruktor ruft die Methode zum Löschen aller Elemente in der doppelt verknüpften Liste auf. Der Destruktor wird am Ende eines Laufs aufgerufen, ich habe ihn mit einer Debug-Nachricht überprüft. Ich habe auch versucht zu überprüfen, ob die gleiche Anzahl von Elementen aus dem Speicher gelöscht werden, die ich zuvor erstellt habe, aber die Referenzzahl passt immer.

Mein Problem ist, dass nach jedem Durchlauf des Testers mehr Speicher zugewiesen wird. Wenn Sie viele Runs oder Läufe mit einer hohen Anzahl von Elementen in der Hashtabelle ausführen, ist dies ein echtes Problem, da es Mega- oder Gigabyte Speicher benötigt.

Meine IDE ist die neueste Version von Xcode auf OS X. Ich habe Instrumente (Profiling-Tool) verwendet, um nach dem Code zu suchen, aber es schlägt nur vor, meine Add-Methode zu betrachten.

void Liste::add(int key, int wert) 
    { 
     Element *createdElement = new Element(); 
     this->referenceCount++; 

     createdElement->wert = wert; 
     createdElement->key = key; 

     if(this->head == NULL && this->tail == NULL) 
     { 
      this->head = createdElement; 
      this->tail = createdElement; 
     } 
     else 
     { 
      tail->next = createdElement; 
      createdElement->prev = this->tail; 
      this->tail = createdElement; 
     } 

     this->size++; 
    } 

Natürlich ist dies der Ort, an dem der Speicher zugeordnet ist, aber meine klar Methode später sollte all diese Elemente später im Spiel löschen, wenn es durch den destructor abgefeuert wird:

void Liste::clear() 
    { 
     cout << "Liste::clear() is fired." << endl; 
     Element *cursor = this->head; 

     while (cursor != NULL) 
     { 
      if(cursor->prev != NULL) 
      { 
       delete cursor->prev; 
       cursor->prev = NULL; 
       this->referenceCount--; 
      } 

      cursor = cursor->next; 
     } 

     delete cursor; 
     this->referenceCount--; 

     this->head = NULL; 
     this->tail = NULL; 
     this->size = 0; 
    } 

Nach Welches Instrument sagt mir die Add-Methode ist der einzige Ort Speicher zugewiesen ist, die nicht freigegeben wird nach der Verwendung, so dass ich hoffe, Sie können mir mit diesem Speicherverlust helfen. Ich habe einige Erfahrung mit mehreren Programmiersprachen, aber ich hatte nie so viel Probleme mit der Speicherverwaltung, bis ich in C++ programmieren musste.

Answer 1

Es sieht so aus, als ob Sie niemals den letzten Cursor löschen, da der vorherige leer ist. If (cursor-> prev! = Null) ... Sonst Cursor löschen; Unterbrechung;

Sie benötigen den anderen Aufruf des Löschcursors auch nicht, da dieser immer null ist.