I have the following code:
class Node {
public:
int data;
Node* parent;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
public:
explicit Node(int d) : data(d),
parent(nullptr),
left(nullptr),
right(nullptr) { }
/*
Some functions
*/
};
class dt {
private:
Node* root;
private:
void add_helper(Node* parent, Node* node);
/*
Some helper functions
*/
public:
dt() : root(nullptr) {}
~dt() {
delete root;
}
/*
Some functions
*/
void add(int data);
};
void dt::add(int data) {
if(!root) {
root = new Node(data); // 1: memory leak
return;
}
Node* node = new Node(data); // 2: memory leak
add_helper(root, node);
}
When I scanning this code for memory leaks Dr. Memory shows errors on the lines mentioned in the comments above. But are they really memory leaks? dt has destructor where the root pointer is deleting. When the destructor will start to delete the root node it will go recursively and will delete all his children. Or there is something else that happens?
are these lines really causing of memory leaks?
The memory allocated on line Node* node = new Node(data) is potentially leaked. At least the example doesn't show where the pointer would be deleted. The ownership could potentially be transferred within add_helper, but that has been excluded from the example.
I'm not familiar with Dr. Memory, but I would hypothesise that it reports where the leaked memory was allocated; not where it was leaked.
Furthermore, if you make a copy of a dt instance, the behaviour of the program will be undefined because both the original and the copy will attempt to delete the copied pointer.
To fix both the potential memory leak, and the potential UB, use unique pointer. Just like you used with Node.
I can't use unqiue_ptr for root because there are multiple pointers to the same Node.
By doing delete root; in the destructor, your class is assuming unique ownership of the pointer. If that assumption is correct, then there is no problem with using a unique pointer. If the assumption is incorrect, then the destructor probably leads to undefined behaviour. Using that instead of a unique pointer is not a solution. You may need to use a shared pointer instead.
Lastly, unless your tree is balanced, the implicit recursive destructor has linearly increasing worst case recursion depth, which can easily cause a stack overflow. You should either balance the tree (for example using red-back or AVL augmentations) or use an iterative algorithm to destroy the children.