Destructor of an object containing a vector of the said object

Question

I have a little trouble with a destructor. In its current state, it create a segfault. Please note that the destructor is only implemented and never explicitly called anywhere. The segfault appear no matter where the breakpoints are.

Here is the destructor :

Graph::~Graph() {

    while(!children.empty()) {

        for(vector<Graph*>::iterator itr = children.begin(); itr != children.end(); ++itr) {
            delete *itr;
        }
        children.clear();
        delete parent;
        delete tab;
    }
}

I also did a variation like this, without better results :

Graph::~Graph() {

    while(!children.empty()) {

        for(unsigned i = 0; i < children.size(); i++)
        {
            delete children.at(i);
        }
        children.clear();
        delete parent;
        delete tab;
    }
}

Here is the class declarations :

class Graph
{
    private :
            Graph*                      parent;
            vector<Graph*>              children;
            Board*                      tab;

    public :
                                    Graph(Board);
                                    Graph(Board, Graph*);
                                    ~Graph();
                void                AddNode(Board&);

          //      Graph&            BFS(Graph&); 
                Graph&              operator=(Graph source);
                vector<Graph*>&     getchildren();
                Graph*              getparent();
                Board*              gettab();
    };



class Board {

private :
            int**           tab;
            int             nbline;
            int             nbcolumn;
            Position        emptyspot;

public  :
                            Board();
                            Board(int, int, Play&);
                            Board(int, int);
                            Board(const Board&);
                            Board(int, int, ifstream&);
                            ~Board();
            void            setValue(Position&, int);
            void            setNbline(int m);
            void            setNbcolumn(int n);
            int             getValue(Position&);
            int             getNbline();
            int             getNbcolumn();
            int             getEmptyline();
            int             getEmptycolumn();
            void            setEmptySpot(Position&);
            Position&       getEmptySpot();

            Board&          operator=(Board& source);

        };


Board::~Board()
{
    for(int i = 0; i < this->nbline; i++)
    {
        delete tab[i];
    }
    delete tab;
}

I'm not really comfortable and very inexperienced with debugger so i don't really know how to use it properly. The call stack point at this line is stl_vector.h :

  /**
   *  Returns a read-only (constant) iterator that points one past
   *  the last element in the %vector.  Iteration is done in
   *  ordinary element order.
   */
  const_iterator
  end() const _GLIBCXX_NOEXCEPT
  { return const_iterator(this->_M_impl._M_finish); }

I don't know what these lines mean to be honest.

The call stack also show the while loop line in the debugger, with the note : Graph::~Graph(this=0x90909090, __in_chrg=optimized out). I also point 3 times the line delete *itr (with the same note).

So my question is, how can i destruct my Graph object ? :'(

EDIT : after further experimentations, the segfault disappear when i delete the only linein code that add things in the vector. Here is the method. I'll add that the values in the vector are always the sames (shouldn't be).

void    Graph::AddNode(Board& tablo)
{
        Graph tmp(tablo, this);
        Graph* newChild = &tmp;
        children.push_back(newChild);  // if i commend this, no segfault
}

I don't know if this is two different problems or the push_back is the cause of the destructor malfunction. I think it's non-related, i expected the segfault to disappear (of course destructor don't have trouble to destruct the tree if the tree only got one node).

EDIT2 : This code doesn't create any segfault, but it doesn't truly destruct all the vectors in the vectors, right ? I think it doesn't because erase will just destroy pointers and not the objets themselves.

while(!children.empty()) {
        children.erase(children.begin(),children.end());
        delete parent;
        delete tab;
    }

Moreover, with this, sometimes the program seem to execute well but don't stop at the end of execution. Debbuger doesn't seem to find anything

EDIT : as ask, the copy constructor of Graph :

Graph::Graph(const Graph& source) {*this = source;}

Graph& Graph::operator=(Graph source)
{
     if(this!=source)
    {
        this->parent = source.parent;
        this->tab = source.tab;
//    this->seen = source.seen;


      while(!source.children.empty()) {

        for(unsigned i = 0; i<source.children.size(); i++) {
            this->children.at(i) = source.children.at(i);
            }
      }
    }

    return *this;
}

Answer 1

The problem is:

delete parent;

Your loop is enforcing the semantics that a Graph owns its children. But by adding that line, you are additionally adding the semantic that a Graph owns its parent. You can't have it both ways. This way, your child is going to delete your parent while it's deleting the child. Removing that delete should solve your issue.

Even better would be to simply express ownership explicitly in terms of member variables:

struct Graph {
    std::vector<std::unique_ptr<Graph>> children;
};

That way, everything will get deleted correctly without you even having to write a destructor! See Rule of Zero

Answer 2

I agree with @Barry that the line

delete parent;

shouldn't be there in the destructor.

In addition, the destructor can be cleaned up a little bit.

You have the call

delete tab;

inside the while loop. The call should be there regardless of whether there are any children or not. Shouldn't it?

You can also remove the while loop altogether.

Graph::~Graph() {

   // Just loop over the children and delete them.
   // If there are no children, the loop is a no op.
   for(vector<Graph*>::iterator itr = children.begin(); itr != children.end(); ++itr) {
      delete *itr;
   }

   // No need for this.
   // The vector will be deleted anyway.
   // children.clear();


   // Delete tab regardless of the number of children.
   delete tab;
}

Answer 3

The AddNode function seems wrong. The tmp object will be destroyed when the function completes and then the pointer in the vector gets invalid and causes the problem when you call delete later on.

Use new instead. Maybe like this:

void    Graph::AddNode(Board& tablo)
{
    Graph* newChild = new Graph(tablo, this);
    children.push_back(newChild);
}

Answer 4

I'll sum up the modifications i did and their consequences.

I changed the destructor as @R Sahu and Barry said.

Graph::~Graph() {

     for(vector<Graph*>::iterator itr = children.begin(); itr != children.end(); ++itr) {
      delete *itr;
   }
   delete tab;
}

I changed the addNodes as nielsen adviced (so does Dieter Lücking) :

void    Graph::AddNode(Board& tablo)
{
        Graph tmp(tablo, this);
         Graph* newChild = new Graph(tablo, this);
        children.push_back(newChild);
}

And, as Paul McKenzie asked, here are my operator= and copy constructor for Graph.

Graph::Graph(const Graph& source) : parent(source.parent), tab(source.tab) {

      while(!source.children.empty()) {

      for(unsigned i = 0; i<source.children.size(); i++) {
                this->children.at(i) = source.children.at(i);
                }
      }
}

Graph& Graph::operator=(Graph source)
{
    this->parent = source.parent;
    this->tab = source.tab;
//    this->seen = source.seen;

    return *this;
}

It makes me figured out that operator= doesn't copy the vector :'(

Now, how is execution. The Segfault is still here, but the callstack changed a lot. I got only 2 lines in call stack, instead of 5/6. The callstack told me there is a problem in

Board*           Graph::gettab(){return this->tab;}

When i do this, in order to see what is in the graph.children vector :

  for(vector<Graph*>::iterator itr = children.begin(); itr != children.end(); ++itr)
            {
              tmp = (*itr)->gettab();
              Board& test = *tmp;  // it's print(Board&) so i just create this. I'll create print(int**) later

              print(test);
 }

If i put these lines in comments, the segfault is still here. The callstack quote me 3 lines in stl_iterator.h (you need those ?) and both the for loop and the delete *itr lines in the destructor.

EDIT :

@nielsen You asked for my main.

int main()
{
            int             lines, columns;
            Play            game;
            Play&           jeu = game;
            srand(time(NULL));

            cout << "+++++++++++++++++++++++++++++" << endl;
            cout << "+++     SOLVER            +++" << endl;
            cout << "+++++++++++++++++++++++++++++" << endl;
            cout << endl;
            cout << endl;


            cout << "Random Board \nLignes : ";
            cin >> lines;
            cout << "\n Colonnes : ";
            cin >> columns;

            Board           randomTab(lines, columns, jeu);

            print(randomTab);
            trace(randomTab);
            cout << "________________" << endl;

            Graph           tree(randomTab);  /// Call stack point to this !
            Board           temporary(randomTab);
            Board&          temp = temporary;
            Board*          tmp = NULL;
            bool            controls = false;

            vector<int> directions {72,75,77,80};

            for(vector<int>::iterator itr = directions.begin(); itr != directions.end(); ++itr)
            {
                temp = randomTab;
                controls = jeu.moves(temp,*itr);

                if(controls)
                {
                     cout << *itr << endl;
                     tree.AddNode(temp);
                     print(temp);
            //         trace(temp);
                     controls = false;
                }
            }

            cout << "__________________" << endl;
            vector<Graph*> children = tree.getchildren();

       /*     for(vector<Graph*>::iterator itr = children.begin(); itr != children.end(); ++itr)
            {
              tmp = (*itr)->gettab();
              Board& test = *tmp;

              print(test);
              cout << "test";
              trace(temporary);
            }*/


return 0;
}


Graph::Graph(Board source) : parent(NULL), tab(&source) {}  // constructeur pour racine

Graph::Graph(Board source, Graph* grap) : parent(grap), tab(&source) {} // constructeur pour nouvelle feuille


Graph::Graph(const Graph& source) : parent(source.parent), tab(source.tab) {  // constructeur par copie

      while(!source.children.empty()) {

      for(unsigned i = 0; i<source.children.size(); i++) {
                this->children.at(i) = source.children.at(i);
                }
      }
}

Answer 5

Someone asked me how Board is created. In this current use case :

Board::Board(int m, int n, Play& jeu) : tab(new int*[m]), nbline(m), nbcolumn(n), emptyspot(n-1,m-1){

           int              x(1);

           for (int i = 0; i < m; ++i){
                tab[i] = new int[n];

                for(int j = 0; j < n; ++j) {
                    tab[i][j] = x; x++;}}

           tab[n-1][m-1]=0;
           x=0;

           while (x!=1000)
           {
            int numbers[] = { UP, DOWN, LEFT, RIGHT };
            int length = sizeof(numbers) / sizeof(int);
            int randomNumber = numbers[rand() % length];

            jeu.moves(*this, randomNumber);
            x++;
           }
        }

/// copy constructor
 Board::Board(const Board& origin): tab(NULL), nbline(origin.nbline), nbcolumn(origin.nbcolumn), emptyspot(origin.emptyspot)
        {
            this->tab = new int*[this->nbline];
            for (int i = 0; i < this->nbline; ++i)
            {
                this->tab[i] = new int[this->nbcolumn];
                for (int j = 0; j < this->nbline; ++j)
                {
                    this->tab[i][j] = origin.tab[i][j];
                }
            }
        }



Board::~Board()
{
    for(int i = 0; i < this->nbline; i++)
    {
        delete tab[i];
    }
    delete tab;
}



Board&              Board::operator=(Board& source)
{

    if (this != &source)
    {
            Position        pos(0,0);
            Position&       p=pos;

            this->setNbline(source.getNbline());
            this->setNbcolumn(source.getNbcolumn());
            this->setEmptySpot(source.getEmptySpot());

            for (int i =0; i < source.getNbline(); i++)
            {
                for(int j=0; j < source.getNbcolumn(); j++)
                {
                    p.setposition(i,j);
                    setValue(p,source.getValue(p));
                }
            }

    }