Memory leak with destructor in a class which has a nested class as private

Question

I have a Tree class which has a nested private Node class. The constructor of my Tree class creates a Node object and set it to _info which is a pointer to a Node type in my Tree class.
I don't have any errors but when I check my program for memory leaks with valgrind, I see that I have memory leaks.
I know that the problem is with the deconstructor but i don't know how to solve it.
Just before showing the code, I should mention that the second argument of my template (N) is not important here and simply you could ignor it.

Here is my code: tree.hpp


#ifndef TREE_HPP
#define TREE_HPP

#include <iostream>
#include <cstddef> 

template <typename T, char N>
class Tree {
private:
  class Node;
  Node* _info;
public:
  Tree();
  Tree(T, char);
  Tree(const Tree&) = delete;
  Tree& operator= (const Tree&) = delete;
  Tree (Tree&&);
  Tree& operator= (Tree&&);
  ~Tree() {delete _info;} // something is wrong here
  bool ins(char, Tree*);
  Tree* fils(char);
  void print(){
    std::cout << _info->getData() << std::endl;
  }
};

template <typename T, char N>
bool Tree<T, N>::ins(char index, Tree* childTree){
  if (_info){
    _info->getChildren()[index] = childTree;
    return true;
  }
  return false;
}

template <typename T, char N>
Tree<T, N>::Tree() 
  : _info(nullptr) {}

template <typename T, char N>
Tree<T, N>::Tree(T data, char size) {
  Node* node = new Node(data, size); // I think I don't free this
  _info = node;
}

template <typename T, char N>
Tree<T, N>::Tree(Tree&& t) {
  _info = t._info;
  t._info = nullptr;
}

template <typename T, char N>
Tree<T, N>& Tree<T, N>::operator= (Tree&& t) {
  if (&t != this) {delete _info; _info = t._info; t._info = nullptr;}
  return *this;
}

template <typename T, char N>
typename Tree<T,N>::Node* Tree<T, N>::info() { return _info;}

template <typename T, char N>
Tree<T,N>* Tree<T, N>::fils(char index){
  return _info->getChildren()[index];
}

template <typename T, char N>
class Tree<T, N>::Node {
private:
  T _data;
  Tree* _children;
  bool _isWord;
public:
  Node();
  Node(T, char);
  Tree** getChildren() {return &this->_children;}
  T getData(){return this->_data;}
  ~Node() = default;
};

template <typename T, char N>
Tree<T,N>::Node::Node(){
  _data = 0;
  _children = nullptr;
  _isWord = false;
}

template <typename T, char N>
Tree<T,N>::Node::Node(T data, char size){
  _data = data;
  _isWord = false;
  _children = new Tree<T,N>[size]; 
}

#endif

main.cpp

#include <iostream>
#include <cstddef>
#include <exception>
#include "tree.hpp"

#define SIZE 5
int main() {
  Tree<char,SIZE> n1('A',SIZE);
  Tree<char,SIZE> n1_1('B',SIZE);
  Tree<char,SIZE> n1_2('C',10); // ! here the size is always 5
  Tree<char,SIZE> n1_1_1('D',SIZE);
  n1.ins(0,&n1_1);
  n1.ins(1,&n1_2);
  n1_1.ins(0,&n1_1_1);
  n1.fils(0)->print();
  n1.fils(1)->print();  
  n1_1.fils(0)->print();
  return 0;
}

I am also open to any suggestion to improve my code.
Thank you in advanced

*I am also open to any suggestion to improve my code.* -- Don't start your variable names with underscores. — PaulMcKenzie, Nov 07 '19 at 16:46
`Node::~Node()` is defaulted and does not delete the pointer(s) owned by `Node` — Richard Critten, Nov 07 '19 at 16:48
I don't know if a default destructor in the Node will correctly delete the the dynamic memory. If you actually implement it, you can guarantee the behavior you want, which is triggering deletes all the way down the tree. — sweenish, Nov 07 '19 at 16:49
@sweenish but if I do `~Node() {delete[] _children;}` in **Node** class, I would have a segmentation fault. — , Nov 07 '19 at 16:57
@RichardCritten If I delete the `_children` by doing `~Node() {delete[] _children;}` I would get a segmentation fault — , Nov 07 '19 at 16:59
Mohammadreza that is unfortunately closer to correct. You'll need to figure out why it faults and fix it. Doing the wrong thing because it doesn't crash is the wrong way to fix a problem. Have you considered using `std::vector`? — user4581301, Nov 07 '19 at 16:59
@Mohammadreza -- The fault is not in the destructor and is simply doing what it's supposed to do -- cleanup. The destructor giving you a segmentation fault means that you are doing something wrong previously. — PaulMcKenzie, Nov 07 '19 at 17:01
@user4581301 I can't use vector because I want to insert a child to a specific index of my _children array — , Nov 07 '19 at 17:07
@PaulMcKenzie unfortunatly, even though I used gdb to debug my program, I was not able to find the problem — , Nov 07 '19 at 17:08
@Mohammadreza -- All I can say is that writing these types of programs where you **must** know as a prerequisite how to handle dynamic memory is going to be difficult for you. You can't guess at these things or just "try things" until it works, let alone how to debug such programs. — PaulMcKenzie, Nov 07 '19 at 17:11
@PaulMcKenzie I am wondering if there is a way to use vector and be able to insert an element to a specific index instead of using push_back() which simply adds the element to the end of the vector — , Nov 07 '19 at 17:18
The [Member Initializer List](https://en.cppreference.com/w/cpp/language/initializer_list) solves that problem. If you replace `Tree* _children;` with `std::vector _children;`, you can place `_children(size)` in the Member initializer List. You can then use `_children [42] = child` to insert `child` into position 42. Using `vector` has the added bonus of making `Node` observe [the Rule of Zero](https://en.cppreference.com/w/cpp/language/rule_of_three) and instantly become a much more stable class. — user4581301, Nov 07 '19 at 18:18
@user4581301 and in that case, is _children going to be a pointer? — , Nov 07 '19 at 18:22
No. `std::vector` is a [RAII-wrapped](https://stackoverflow.com/questions/2321511/what-is-meant-by-resource-acquisition-is-initialization-raii) pointer with some extra book-keeping to keep track of capacity and size. It's pretty much fire-and-forget, taking care of all of the common (and a lot of uncommon) management issues people run into when working with dynamically allocated arrays. — user4581301, Nov 07 '19 at 18:26
You can also `_children.resize(size)` in the constructor's body. I strongly recommend reading [some good documentation for `std::vector`](https://en.cppreference.com/w/cpp/container/vector) so you can see how it can be used and used better. — user4581301, Nov 07 '19 at 18:26

score 1 · Answer 1 · answered Nov 07 '19 at 17:00

1

_children = new Tree<T,N>[size];

There is no delete[] _children; anywhere.

Even more problematic:

Tree** getChildren() {return &this->_children;}

This function returns a pointer to a solitary Tree* object that is not an element of an array.

return _info->getChildren()[index];

Here, you index into that pointer to a solitary object as if it were in an array. Using any other index than 0 has UB.

answered Nov 07 '19 at 17:00

eerorika

232,697
12
197
326

But I don't know how to write this code any other way? I can't use vector and I am stuck with array – Nov 07 '19 at 17:06
@Mohammadreza -- Well, the way you're writing it now has bugs. Any answer you will get will be similar to the one here. So I don't really know what you are expecting us to do. – PaulMcKenzie Nov 07 '19 at 17:08
I want to know if somebody could help me to fix this mistakes that I made coding and improve them to a better code – Nov 07 '19 at 17:12

Memory leak with destructor in a class which has a nested class as private

1 Answers1