CODEWITHSUNDEEP
c++recursionvectortree
Csi
Csi

Reputation: 526

Destructor, graph and recursivity

I have a graph object and i would like to create a destructor for this. However, i'm not really confortable with recursivity and i'm a bit lost in my own data structures. I'll show the classes involved and my beginning of destructor.

class Graph {

private :
        Graph*               parent;
        vector<Graph>        child;
        Board                tab;
        bool                 seen;

public :
        Graph(const Board&);
        Graph(const Board&, Graph*);
        ~Graph();
        ...
};

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();
       ...
};

Position class only got 2 int (line and columns). The Board destructor works : 

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

As you guessed, i would like to destroy a node of my graph, and all the following nodes.

Here is my beggining : 

Graph::~Graph() {        
    while(!child.empty()) {                
        for(vector<Graph>::iterator itr = child.begin; itr != child.end; ++itr) {
            delete child[itr];
        }
    }
}

This way I go into all of my branch, recursively, right? When I find a leaf (vector is null) - if destroy everything, what will happen in the vector of the parent ?

I don't know if the parent will set himself at NULL (i don't think so), and parent vector memory space won't be unallocated so the condition child.empty() won't be fulfilled, right ?

Upvotes: 0

Views: 2158

Answers (1)

Barry
Barry

Reputation: 303297

Your destructor is incorrect for lots of reasons.

  1. Your child member should probably be vector<Graph*> so that you can actually delete them.
  2. Your loop is infinite if your Graph has any children since you are never changing the size of the child vector.
  3. child[itr] is not how you get the Graph* corresponding to the iterator, *itr is.
  4. begin and end are member functions, so they need to be called.
  5. The member should probably be named children, no?

The correct loop would be:

for (vector<Graph*>::iterator itr = children.begin(); itr != children.end(); ++itr) {
    delete *itr; // this will recursively call Graph::~Graph() 
                 // on the children, and then free their memory
}

Or, in C++11, we simply define:

std::vector<std::unique_ptr<Graph>> children;

So that the memory cleanup would be handled for us.

Upvotes: 3

Related Questions