CODEWITHSUNDEEP
c++pointerstreesegmentation-fault
Eric Bush
Eric Bush

Reputation: 197

Memory allocation error when attempting to print contents of a tree in C++

My problem probably has a simple solution that is staring me in the face, but so far I have been unable to find it. I am pretty new to C languages and this is the first program I have written in C++.

I have a function create_complete_tree(int nr_child_nodes, int tree_depth) that makes a tree of depth int tree_depth in which each node (except for the last row) has int nr_child_nodes number of child nodes. create_complete_tree(2,4) makes a tree that starts out like this:

                      1
                     / \
                    /   \
                   2     9
                  / \   / \
                 3   6 10 13
                /\   /\/\ /\
                     ...

I am trying to make a function print(std::ostream& str) that, when called on the root node of the tree above, prints the tree contents in this format:

node_1
   node_2
      node_3
         node_4
         node_5
      node_6
         node_7
         node_8
   node_9
      node_10
         node_11
         node_12
      node_13
         node_14
         node_15

I will worry about adding the indents later, but right now I'm just focused on printing the nodes out in the correct order. This is what I have so far:

void node::print(std::ostream& str) {
    str << this->get_name() << std::endl;

    for (int i = 0; i < this->get_nr_children(); i++) {
        node child = (*this->get_child(i));
        child.print(str);
    }
}

This function prints nodes 1-8 out, but then I get a Segmentation fault: 11 error. I know this error is a result of attempting to access memory that is somehow unavailable/off-limits, but I'm struggling to understand what that really means in my case. My create_complete_tree method looks like this:

void node::create_complete_tree(int nr_child_nodes, int tree_depth) {
    if (tree_depth == 1) {
        return;
    } else {
        while (this->get_nr_children() < nr_child_nodes) {
            node* new_child = new node();
            this->add_child(new_child);
            (*new_child).create_complete_tree(nr_child_nodes, tree_depth - 1);
        }
    }
}

The child node pointers for each node are stored in a vector called child_nodes. Thanks for taking the time to read this. I'd be grateful for any responses that help me find a solution and better understand memory allocation.

Upvotes: 1

Views: 57

Answers (1)

Christophe
Christophe

Reputation: 73376

Problem

This code very probably infringes the rule of 3. The following statement: 

    node child = (*this->get_child(i));

creates a clone of the node. If you didn't provide for the rule of 3, but implemented the destructor, the clone will use the same pointers to the same children than the original node. Unfortunately, when you then leave the print() function, the clone gets destroyed and the destructor will destroy the children. All subsequent access to these children will then access an object which no longer exist, which is UB.

Segfault is a possible symptom of UB. I cannot confirm for sure without seing the constructor, copy constructor, assignment and destructor implementation of node. But seing this code, and many similar questions here, I would be surprised that it'd be another issue ;-)

Potential solutions

The correct solution would anyhow be to implement what's missing for the trule of 3. Because you will experience similar problems in many situations if you don't.

Another solution (which is not mutually exclusive) would be to use pointer without cloning: 

void node::print(std::ostream& str) {
  str << this->get_name() << std::endl;

  for (int i = 0; i < get_nr_children(); i++) { // this-> is not needed
    node *child = this->get_child(i);         // pointer assignment without cloning
    child->print(str);                        // member invokation for a pointer
  }
}

Upvotes: 1

Related Questions