リンクリストの破棄

Question

アルゴリズムの問​​題を解決するためのリンクリストを実装しようとしていました。
それは基本的には機能しましたが、私はあまりにも多くのメモリを使用していました。
次のようなデストラクタデザインの欠陥を指摘していただければ幸いです。

template<typename T> 
struct Node { 
    Node(): item(0),next(0) {} 
    Node(T x): item(x),next(0) {} 
    T item; 
    Node* next; 
}; 

template <typename T> 
struct List { 
    List() : head(0),tail(0) {} 
    Node<T>* head; 
    Node<T>* tail; 
    void insert(T x) { 
     Node<T>* newNode = new Node<T>(x); 
     if(head == NULL) { 
      head = tail = newNode; 
     } else { 
      tail->next = newNode; 
      tail = tail->next; 
     } 
    } 

    void clearRecur(Node<T>* h) { 
     if(h) { 
      clearRecur(h->next); 
      delete h; 
     } 
    } 

    void clear() { 
     if(head) { 
      clearRecur(head); 
     } 
    } 
}; 

Answer 1

リストは反復的または反復的にクリアすることができます。

あなたの（IMHOの正しい）バージョンに代わって、私は若干異なるアプローチを使用します。Node自身を "責任を負って"その尾を削除するようにします。これにより、再帰的な消去も行われます（コードは少なくなります）。

再帰クリア：

template<typename T> 
struct Node { 
    Node(): item(), next(nullptr) {} 
    Node(T x): item(x), next(nullptr) {} 

    ~Node() { delete next; } // <== recursive clearing 

    T item; 
    Node* next; 

    // Using the default copy ctor would corrupt the memory management. 
    // Deleting it lets the compiler check for accidental usage. 
    Node(const Node&) = delete; 
    // Deleting assignment operator as well. 
    Node& operator=(const Node&) = delete; 
}; 

template <typename T> 
struct List { 
    List() : head(nullptr), tail(nullptr) {} 
    ~List() { clear(); } 
    Node<T>* head, tail; 
    void insert(T x) { 
     Node<T>* newNode = new Node<T>(x); 
     if (head == nullptr) head = tail = newNode; 
     else { 
      tail->next = newNode; 
      tail = tail->next; 
     } 
    } 

    void clear() { 
     delete head; 
     head = tail = nullptr; 
    } 

    // Using the default copy ctor would corrupt the memory management. 
    // Deleting it lets the compiler check for accidental usage. 
    List(const List&) = delete; 
    // Delete assignment operator as well. 
    List& operator=(const List&) = delete; 
}; 

これは、私たちの現在のプロジェクトでそれをやった方法です。一見すると、シンプルで機能しているように見えました。私たちのベータテスターが活躍したとき、私は気が変わった。実際のプロジェクトでは、リストの長さが長くなり、再帰的なクリアにスタックメモリが不足していました。 （Yepp – スタックオーバーフロー）私はよく知っていたはずです！

したがって、私は「責任」がNodeからListに戻されるように反復して–をクリアしました。 （API、それは「ボンネットの下に」起こるように、ユーザーがこれを注意しません。）

反復クリア：

template<typename T> 
struct Node { 
    Node(): item(), next(nullptr) {} 
    Node(T x): item(x), next(nullptr) {} 
    T item; 
    Node* next; 
}; 

template <typename T> 
struct List { 
    List() : head(nullptr), tail(nullptr) {} 
    ~List() { clear(); } 
    Node<T>* head, tail; 
    void insert(T x) { 
     Node<T>* newNode = new Node<T>(x); 
     if (head == nullptr) head = tail = newNode; 
     else { 
      tail->next = newNode; 
      tail = tail->next; 
     } 
    } 

    void clear() { 
     while (head) { 
      Node<T> *p = head; head = head->next; 
      delete p; 
     } 
     tail = nullptr; 
    } 

    // Using the default copy ctor would corrupt the memory management. 
    // Deleting it lets the compiler check for accidental usage. 
    List(const List&) = delete; 
    // Delete assignment operator as well. 
    List& operator=(const List&) = delete; 
};