Вопрос новичка. Я пытаюсь запрограммировать двоичное дерево поиска, но даже простая вставка имеет утечку памяти.
Файл 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).
Во-первых, почему у меня утечка памяти? Во-вторых, почему я получаю сообщение о новых (беззнаковых длинных), когда в моей программе нет ничего неподписанных длинных? Спасибо.
Вы можете сказать мне использовать умные указатели, но сейчас я просто пытаюсь узнаю, что такое указатели, и пытаюсь понять, почему это не работает.





Если вы не собираетесь использовать интеллектуальные указатели, вам необходимо соединить каждый 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. Это экономит строки кода, делает ваши намерения очевидными, а затем возникает проблема «безопасности исключений».
Кроме того, я только что обнаружил, что, поскольку в этом случае значение является указателем, мне также нужен delete value в ~Node().
Ты не примешь мой ответ? :(