Destruktor für eine List-Klasse in C++

Question

Ich bin neu in C++ also die Frage. Ich habe eine Spielzeug-Implementierung einer Singlelink-Liste in C++.

template<typename T> 
class List { 
    template<typename U> 
    struct Node { 
     U data_; 
     Node<U>* next_; 

     Node() : data_(0), next_(nullptr) {} 
     Node(U data) : data_(data), next_(nullptr) {} 
    }; 

private: 
    Node<T>* head_; 
    std::size_t size_; 

public: 
    List() : head_{nullptr}, size_{0} {} 

    void insert(const T& item) { 
     Node<T>* p(new Node<T>(item)); 
     if (size_ == 0) { 
      head_ = p; 
     } else { 
      p->next_ = head_; 
      head_ = p; 
     } 
     size_++; 
    } 
    std::size_t getSize() { 
     return size_; 
    } 

    ~List(){ 
    while(head_){ 
     Node<T> p = head_; 
     delete(p); 
     head_ = head_->next_; 
    } 
}; 

Dieser Code scheint zu funktionieren. Das Problem besteht jedoch darin, dass die Objekte, die von new zugewiesen werden, trotz des Destruktors ~List() nie bereinigt werden. Kann mir jemand helfen, zu verstehen, wie ich einen Destruktor für diese Klasse schreiben kann, der alle zugewiesenen Knoten aufräumt?

Wichtige Bemerkung: Ich bin mir bewusst, dass dies mit intelligenten Zeigern getan werden kann, aber ich möchte die alte Art der Verwaltung von Heap verstehen.

Answer 1

while(head_){ 
    Node<T> p = head_; <-- change to pointer 
    delete(p); <-- you can't delete this right now 
    head_ = head_->next_; 
} 

p sollte ein Zeiger sein. Sie können nicht sofort löschen. Sie müssen den next Knoten finden und löschen Sie später. Auch delete p; anstelle von delete (p); wie folgt:

~List() { 
    while(head_) { 
     Node<T> *p = head_; 
     head_ = head_->next_; 
     delete p; 
    } 
} 

Wie in den Kommentaren erwähnt, Node braucht keine Vorlage zu sein. Sie können Ihre Klasse vereinfachen. insert kann auch vereinfacht werden, da head_-nullptr initialisiert ist, können Sie sicher p->next_ = head_;

template<typename T> class List { 
    struct Node { 
     T data_; 
     Node* next_; 
     Node() : data_(0), next_(nullptr) {} 
     Node(T data) : data_(data), next_(nullptr) {} 
    }; 
    Node* head_; 
    std::size_t size_; 
public: 
    List() : head_{ nullptr }, size_{ 0 } {} 

    void insert(const T& item) { 
     Node* p = new Node(item); 
     p->next_ = head_; 
     head_ = p; 
     size_++; 
    } 

    std::size_t getSize() { 
     return size_; 
    } 

    ~List() { 
     while(head_) { 
      Node *marked = head_; 
      head_ = head_->next_; 
      delete marked; 
     } 
    } 
}; 

Answer 2

Die allgemeine Idee zuweisen kann, ist, dass Sie herausfinden, wer der Besitzer des Objekts ist zu entscheiden, wer es löschen sollte.

In Bezug auf die Knoten, ist die Liste der Eigentümer. Daher sollten Sie alle Methoden sorgfältig so entwickeln, dass, sobald die Liste das Eigentum an dem Objekt verliert, sichergestellt wird, dass das Objekt gelöscht wird oder das Eigentum übernommen wird.

Offensichtliche Orte, wenn Sie den Speicher freizugeben ist, erste Sie die Liste löschen. Zweitens, wenn Sie ein Element entfernen, zum Beispiel pop.

Lets in beiden Fällen suchen.

Löschen Sie zuerst die Liste. Dafür müssen Sie einen Destruktor schreiben, der über die Liste iteriert und Elemente nacheinander löscht. Dazu beziehe ich mich auf die Antwort von @ barmak-shemiani.

Für den Fall, wenn Sie ein Element Pop Sie folgendes tun:

T pop() { 
    Node<T> *tmp = head_; 
    if (head_ != nullptr) 
     head_ = head_->next_; 
    T data = tmp->data_; 
    delete tmp; 
    return data; 
    }