CODEWITHSUNDEEP
c++treesmart-pointers
Publius
Publius

Reputation: 1224

N-Ary Tree Design with Smart Pointers

I'm trying to design a tree class in C++, but I'm running into some trouble with node destruction.

If I destroy a node, I don't want to destroy it's entire sub-tree because there might be something else pointed to it. So the obvious solution is the use reference counting. I'd have a weak pointer to the parent, and a vector of shared pointers to the child nodes. That way if a node is destroyed, it's children are only destroyed if nothing is pointing to them.

But I run into another problem here: adding a child to a node. weak_ptr only works if there's already a shared_ptr pointing to an object. And if I adding a child to a node, I don't know where to find a shared_ptr that's pointing to it. So what do I do here?

Upvotes: 0

Views: 1249

Answers (3)

TJ Bandrowsky
TJ Bandrowsky

Reputation: 882

I think the thing you need to consider is the need to have a tree that shares nodes. I think that sort of thing will be madness, but if you wanted to bring some simplicity to it, consider this:

  1. Use a map or vector to actually hold the nodes and manage their lifetime. You have a map of shared_ptrs and you are good to go.

  2. For the tree, separate a child node from the item that it points to. The idea is that, you use shared_ptrs or even unique pointers on each of the tree nodes themselves. That way, when you free a node, it will do all of the children quite nicely, but, you won't free the potentially duplicate items.

  3. Use a weak pointer in the tree node to point to the payload.

Something like this:

template <class P> class tree_node {
public:

    std::weak_ptr<tree_node<P>> parent;
    std::vector<std::shared_ptr<tree_node<P>> children;
    std::weak_ptr<P> data;
};

template <class P> class store {
public:
     std::vector<std::shared_ptr<P>> data;
     tree_node<P> index;
};

Something like that. Some efficiencies for certain cases can be achieved if P is not polymorphic. But, what you get is a class store, that, automatically frees all of your data structures to make that store, the items, tree, index, and if you delete a node out of data and blow it, calling lock() on the weak pointer to it will let you do something about that.

Upvotes: 0

Kerrek SB
Kerrek SB

Reputation: 477338

To expand on David Rodriguez's idea, a skeleton tree might look like this:

struct node : std::enable_shared_from_this<node>
{
    std::vector<std::shared_ptr<node>> children;
    std::weak_ptr<node> parent;

    void add_child()
    {
        auto n = std::make_shared_node>();
        n->parent = std::weak_ptr<node>(shared_from_this());
        children.emplace_back(n);
    }
}

auto root = std::make_shared<node>();

root.add_child();
root.add_child();
root.add_child();

root.children[0].add_child();

(Of course a real-world node would have a non-trivial constructor with payload values, and add_child would take similar arguments or be a template...)

Upvotes: 4

David Rodr&#237;guez - dribeas
David Rodr&#237;guez - dribeas

Reputation: 208406

You might want to look into enable_shared_from_this that allows you to obtain the shared_ptr directly from the object. It still requires that the object is managed by a shared_ptr, but you don't need to find who is holding it.

Upvotes: 3

Related Questions