call me Steve call me Steve - 3 months ago 7
C++ Question

My tree-node has a missing link

I was going through the question Tree Nodes Getting Lost and thought it woudl be a good exercise to do in c++11.

I came with the code below. But the Root element is not connecting to the rest of the nodes and I can't find why.

Edit: you can find the code here: https://ideone.com/NCyRsx I use visual studio but I obtain the same results.

#include <iostream>
#include <vector>
#include <array>

struct Node
{
int key;
std::vector<Node> children;
Node(int k)
{
key = k;
}

void Add(Node n)
{
children.push_back(n);
}

void display()
{
std::cout << "My value is " << key << std::endl;
std::cout << "My " << children.size() << " kid(s) are : " << std::endl;
for( auto n : children)
{
n.display();
}
}

};

int main()
{
constexpr int numNode = 5; // for
std::array<int, numNode> numbers = { 4, -1, 4, 1, 1 };
std::vector<Node> nodesStorage;

for (int i = 0 ; i < numNode ; i++)
{
nodesStorage.push_back(Node(i));
}
nodesStorage.push_back(Node(-1));

for (int i = 0 ; i< numNode ; i++)
{
if(numbers[i] == -1) // the root
{
nodesStorage[numNode].Add(nodesStorage[i]);
}
else
{
nodesStorage[numbers[i]].Add(nodesStorage[i]);
}
}

nodesStorage[1].display();
nodesStorage[numNode].display();

return 0;

}

Answer

The Node::Add calls in main updates Nodes in nodesStorage but not Node::children (and vice versa) because Nodes are passed by value (i.e. copied). As pointed out in the comments, you have to use pointers instead of values.

Replace

std::vector<Node> nodesStorage;

by

std::vector<std::shared_ptr<Node>> nodesStorage;

and fix everywhere else your compiler complains about. Oh, and make sure you #include <memory>.

Since you are doing this as an exercise, I'm leaving out detailed fixes for now. Here are references for std::shared_ptr and std::make_shared.

In C++11 (or rather C++14) we rarely handle raw pointers, new or delete operators. Instead we use std::shared_ptr or std::unique_ptr depending on needs. std::shared_ptr calls delete in its destructor when no other std::shared_ptr refers the same object. This ensures a resource is automatically disposed when it is no longer needed (RAII idiom).

Comments