Утечка памяти класса бинарного дерева поиска в C++

Вопрос новичка. Я пытаюсь запрограммировать двоичное дерево поиска, но даже простая вставка имеет утечку памяти.

Файл Node.h

template<typename X> struct Node {
   X value;
   Node* left;
   Node* right;

   Node(X x) {
      this->value = x;
      this->left = nullptr;
      this->right = nullptr;
   }
};

Файл BST.h

template <typename X> class BST {
   public:
      BST() { root = nullptr; }

      bool Insert(const X& x) { return InsertAt(root, x); }

   private:

      bool InsertAt(Node<X>*& node, const X& x)
      {
         if (node == nullptr) {
            node = new Node<X>(x);
            return true;
         }

         if (node->value == x)
            return false;

         if (*(node->value) > *x)
            return InsertAt(node->left, x);

         return InsertAt(node->right, x);
      }

//----

      Node<X>* root;
};

Основная программа

#include "Node.h"
#include "BST.h"

int main(int argc, char **argv)
{
   BST<int*> bst;
   bst.Insert(new int(8));
}

Вывод g ++ -g -fsanitize = address -fno-omit-frame-pointer -std = C++ 11 B.cpp == 10646 == ОШИБКА: LeakSanitizer: обнаружены утечки памяти

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x7fb5e7f45532 in operator new(unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99532)
    #1 0x400eb7 in BST<int*>::InsertAt(Node<int*>*&, int* const&) /home/gc/BST.h:12
    #2 0x400e68 in BST<int*>::Insert(int* const&) /home/gc/BST.h:5
    #3 0x400d09 in main /home/gc/B.cpp:22
    #4 0x7fb5e778082f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

Indirect leak of 4 byte(s) in 1 object(s) allocated from:
    #0 0x7fb5e7f45532 in operator new(unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99532)
    #1 0x400caf in main /home/gc/B.cpp:22
    #2 0x7fb5e778082f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

SUMMARY: AddressSanitizer: 28 byte(s) leaked in 2 allocation(s).

Во-первых, почему у меня утечка памяти? Во-вторых, почему я получаю сообщение о новых (беззнаковых длинных), когда в моей программе нет ничего неподписанных длинных? Спасибо.

Вы можете сказать мне использовать умные указатели, но сейчас я просто пытаюсь узнаю, что такое указатели, и пытаюсь понять, почему это не работает.

Ты не примешь мой ответ? :(

hegel5000 17.04.2018 19:27
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
1
650
1

Ответы 1

Если вы не собираетесь использовать интеллектуальные указатели, вам необходимо соединить каждый new с delete. Поскольку ваши вызовы new происходят в конструкторе каждого класса, вы можете использовать delete в деструкторе.

В любом случае, в BST деструктор должен быть

~BST() { delete root; }

А в Node это

~Node() { delete left; delete right; }

Это будет рекурсивно работать вниз по дереву. Ваш рекурсивный случай - это когда указатель на узел не равен нулю. В отличие от free, который дает сбой при нулевом значении, delete просто ничего не делает, делая nullptr вашим базовым случаем.

Проверить http://en.cppreference.com/w/cpp/language/destructor

И да, я обязательно посоветую вам просто использовать std::unique_ptr<Node<X>> вместо того, чтобы беспокоиться о new и delete. Это экономит строки кода, делает ваши намерения очевидными, а затем возникает проблема «безопасности исключений».

hegel5000 11.04.2018 01:12

Кроме того, я только что обнаружил, что, поскольку в этом случае значение является указателем, мне также нужен delete value в ~Node().

granite chimp 11.04.2018 01:43

Другие вопросы по теме