Smart pointers and trees

I have Node:
1
2
3
4
int level
string name
Node* parent
std::vector<std::unique_ptr<Node>> childs;


I create Node with level and depend on level, link to last node or its ancestor:
1
2
3
4
5
6
7
std::unique_ptr<Node> root(new Node), lastNode;
lastNode = move(root);
while ....
 //read lines from file
   std::unique_ptr<Node> child(new Node(line));
   child->link(lastNode.get());
   lastNode = move(child);


where link is:
1
2
3
4
5
6
void Node::link(Node* node) {
    Node* ancestor = node;
    while (ancestor && ancestor->level>=level) ancestor = ancestor->parent;
    parent = ancestor;
    ancestor->childs.push_back(std::unique_ptr<Node>(this));
}

It causes double freeing,
Better would be shared ptr? But how do it on trees?
Last edited on
with shared ptr you can have 2 children point to the same parent.
only one parent points to a child, though, in an normal tree. so node* (line 3 of node block) should be shared, and the children can be as-is (unique)

I do not see where you have a double free here. maybe on root? root move to lastnode seems odd, not sure what you are doing there. Maybe line 1 of the node block also should be shared, so you can keep root and lastnode both?
Last edited on
With this,
1
2
3
4
int level
string name
Node* parent
std::vector<std::unique_ptr<Node>> childs;

it appears that the node owns its child nodes and the pointer to the parent is a non-owning pointer.
In that case, why can't the child nodes be held by value ie. in std::list<Node> children?

If unique pointers are to be used, have one and only one active smart pointer to an object owned by a unique pointer. This is a recipe for a guaranteed disaster:
so node* (line 3 of node block) should be shared, and the children can be as-is (unique)
Last edited on
In the 2nd code snippet, lastNode is move-assigned from root. Therefore root after is left in a valid but unspecified state (probably empty) and shouldn't be used again without having a value assigned.

Also L7. After child is also in a valid but unspecified state (again probably empty).

In this context, std::move() is effectively moving memory ownership which is what I don't think you want. Shouldn't lastNode just be a normal pointer?

You also seem to be allocating memory twice - L5 in the second code snippet and L5 in link() - or am I reading the code wrong as I've just glanced over it?????
Last edited on
Perhaps something like (NOT tried);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <memory>
#include <string>
#include <vector>

struct Node;

using Node_up = std::unique_ptr<Node>;

struct Node {
	int level {};
	std::string name;
	Node* parent {};
	std::vector<Node_up> childs;

	Node* get_Parent(Node* ancest) {
		while (ancest && ancest->parent && ancest->level >= level)
			ancest = ancest->parent;

		return ancest;
	}

	void link(Node* node) {
		parent = get_Parent(node);
		parent->childs.push_back(std::move(Node_up(node)));
	}
};

int main()
{
	const Node_up root {new Node};
	auto lastNode {root.get()};

	while (true) {
		//read line from file
		const auto child {new Node};  // (line);

		child->link(lastNode);
		lastNode = child;
	}
}


Memory is only allocated once for each child which is automatically deleted when the tree goes out of scope. Ordinary pointers are just that - pointers - and are not owning and for memory management can be ignored.

Topic archived. No new replies allowed.