Является ли рекурсивный деструктор для связанного списка, дерева и т. Д. Плохим? - PullRequest
Новая
       20

Является ли рекурсивный деструктор для связанного списка, дерева и т. Д. Плохим?

8 голосов
/ 06 августа 2011

Для моего текущего учебного упражнения я изучаю связанные списки и деревья. Недавно я увидел предложение рекурсивно уничтожать структуры данных, заставляя каждый узел удалять своих потомков / потомков. Однако почти во всех примерах, которые я обнаружил, деструктор узла пуст, а некоторые управляющие классы обрабатывают уничтожение, используя некоторую форму итерации и удаления. С точки зрения надежности и / или стилистики, есть ли что-то плохое в рекурсивном деструкторе?

Далее следует мое понимание двух подходов.

Рекурсивное уничтожение: 

#include <iostream>
struct Node {
  static int count;
  Node() : num_(count++), p_next_(0) {}
  ~Node() { 
    std::cout << "entering " << num_ << "\n";
    delete p_next_;
    std::cout << " leaving " << num_ << "\n";
  }
  const int num_;
  Node* p_next_;
};
int Node::count = 0;
int main () {
  Node* p_head = new Node();
  p_head->p_next_ = new Node();
  p_head->p_next_->p_next_ = new Node();
  delete p_head;
  return 0;
}

А вот мое мнение об управлении уничтожением класса. Предполагая, что я определил следующий DTOR для узла: 

~Node() {std::cout << "Someone deleted " << num_ << "\n";}

Я бы определил следующий управляющий класс LinkedList и последующий основной 

/* other stuff from above */
class LinkedList {
public:
  LinkedList() : p_head_(new Node()) {
    p_head_->p_next_ = new Node();
    p_head_->p_next_->p_next_ = new Node();
  }
  ~LinkedList() {
    while(Node* p_prev = p_head_) {
      p_head_ = p_head_->p_next_;
      delete p_prev;
    }
  }
private:
  Node* p_head_;
};
int main () {
  LinkedList* p_list = new LinkedList();
  delete p_list;
  return 0;
}

Предполагая, что я правильно читаю свои результаты, мои две реализации делают одно и то же.

Что касается моего примера рекурсивного уничтожения, я думаю, что мне почти всегда будет нужен какой-то класс управления, который содержит копию заголовка, когда я решаю реальную проблему с кодом, но классу управления нужно только удалить заголовок / корневой узел, чтобы обеспечить разрушение всей структуры данных. Это кажется мне более элегантным, но у меня возникли проблемы с кодом, который я считал аккуратным.

Должен ли управляющий класс отвечать за правильное удаление всего? Или для базовой структуры данных лучше знать, как себя очистить? Есть ли ошибки, которые не очевидны?

Спасибо!

- Иордания

править: Мне пришла в голову мысль. Если у меня есть чрезвычайно длинная цепочка узлов, нужно ли беспокоиться о переполнении стека во время уничтожения в первом примере, так как рекурсия находится в игре?

edit2: Полагаю, это должно было быть очевидно. И теперь я чувствую себя немного глупо. На моей машине, если у меня более 64910 узлов, у меня происходит сбой. Таким образом, рекурсия ясно представляет ошибку.

Ответы [ 2 ]

6 голосов
/ 06 августа 2011

Если вы сделаете это для связанных списков, возникнет проблема использования памяти стека.Уничтожение такого связанного списка приведет к рекурсивному d'or вашего Node, тогда как глубина рекурсии будет расти линейно с размером вашего связанного списка.

Просто проведите эксперимент: введите несколько миллионов узлов в свойсписок, а затем уничтожить его.Бьюсь об заклад, вы получите переполнение стека (если вы не настроили свой поток для резервирования огромного размера стека).Особенно в отладочной сборке вы начнете работать вне стека очень рано.

OTOH делать это для деревьев нормально, по крайней мере, с технической точки зрения.В любом случае очистка дерева обычно выполняется рекурсивно, даже тот факт, что указанная выше рекурсивная функция принадлежит дереву или Node, не важен.

Глубина рекурсии уничтожения дерева будет логарифмически увеличиваться с глубиной дереваэто нормально.

4 голосов
/ 06 августа 2011

Подумайте о владельцах связанного элемента.

Имеет ли смысл, что объект Node владеет им следующим родом? Разумеется, имеет смысл, что Узлу принадлежат присоединенные спутниковые данные, поэтому вы должны очистить его, когда Узел уничтожается.

LinkedList владеет своими узлами, поэтому он должен нести ответственность за их правильное уничтожение без каких-либо остатков в памяти.

Объект LinkedList должен иметь возможность добавлять и удалять узлы, поэтому с точки зрения владельца он несет ответственность за их очистку, например, путем удаления каждого узла в списке итеративно.

...