VPF::Удаление памяти после работы со структурой

rudvil

Дата 1.11.2010, 23:05 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 20.11.2009
Где: Latvia/Riga

Репутация: 1
Всего: 3

Есть структура бинарного дерева

Код


  struct tree_t {

    tree_t() : left_(0), right_(0) { }

    ...

    ~tree_t() {
      if (this->left_ != 0) {
        this->delete_node(*this->left_);
        delete this->left_;
      }
      if (this->right_ != 0) {
        this->delete_node(*this->right_);
        delete this->right_;
      }
    }

    void delete_node(tree_t & tree) {
      if (tree.left_ != 0) {
        this->delete_node(*tree.left_);
        delete this->left_;
      }
      if (tree.right_ != 0) {
        this->delete_node(*tree.right_);
        delete this->right_;
      }
    }

    type_t type_;
    string_type value_;
    tree_t* left_;
    tree_t* right_;
  };

Думаю подробно объяснять что да как не нужно, создали дерево, поработали с ним и при вызове деструктора подчищаем все за собой.
Правильно ли я выполнил чистку в деструкторе?
Спасибо!

--------------------

xor

icecrashldr

Дата 2.11.2010, 11:20 (ссылка)

(нет голосов)

Загрузка ...

Developer

Профиль
Группа: Участник
Сообщений: 122
Регистрация: 5.7.2010

Репутация: нет
Всего: нет

Если про очистку памяти, то вроде бы как правильно, а вот если вы про рекурсию, то не правильно ..

Код


void delete_node(tree_t & tree) {
      if (tree.left_ != 0) {
        this->delete_node(*tree.left_);
        delete this->left_;
      }
      if (tree.right_ != 0) {
        this->delete_node(*tree.right_);
        delete this->right_;
      }
    }

В этом месте может произойти очень большая рекурсия.
К примеру у вас было в дереве несколько 2 тысячи записей.
То при очистки будет 2000 вызовов что может привести к переполнению стека.

Вам в деструкторе нужно делать цикл, при чем который может идти в одну сторону(left или right) - это и быстрее будет и переполнения стека не будет( ну хотя бы на этом уровне )

xvr

Дата 2.11.2010, 11:56 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

Цитата(rudvil @ 1.11.2010, 23:05

)

Правильно ли я выполнил чистку в деструкторе?

Будьте проще, и люди к вам потянутся! smile

Код


 struct tree_t {
    tree_t() : left_(0), right_(0) { }
    ...
    ~tree_t() {
      delete left_;
      delete right_;
   }
};

Этого вполне достаточно

Леопольд

Дата 2.11.2010, 12:39 (ссылка)

(голосов:1)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 3
Всего: 13

Цитата(icecrashldr @ 2.11.2010, 11:20

)

К примеру у вас было в дереве несколько 2 тысячи записей.
То при очистки будет 2000 вызовов что может привести к переполнению стека.

Глуина рекурсии соответсвует глубине дерева, а не количеству элементов.

--------------------

вопросов больше чем ответов

rudvil

Дата 2.11.2010, 16:34 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 20.11.2009
Где: Latvia/Riga

Репутация: 1
Всего: 3

Цитата

Вам в деструкторе нужно делать цикл, при чем который может идти в одну сторону(left или right) - это и быстрее будет и переполнения стека не будет( ну хотя бы на этом уровне )

цикл? зачем? у меня указатель на 1 элемент, а не на массив.

Цитата

Этого вполне достаточно

Действительно, а я тут намутил... спасибо!
А вообще что-то я туплю последнее время, ведь есть boost::scoped_ptr... всем спасибо за помощь.

Это сообщение отредактировал(а) rudvil - 2.11.2010, 16:35

--------------------

xor

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »