c++ - 带智能指针的 N​​-Ary 树设计

Question

我正在尝试用 C++ 设计一个树类，但我遇到了节点销毁的问题。

如果我销毁一个节点，我不想销毁它的整个子树，因为可能有其他东西指向它。所以显而易见的解决方案是使用引用计数。我会有一个指向父节点的弱指针，以及一个指向子节点的共享指针 vector 。这样，如果一个节点被销毁，它的子节点只有在没有任何指向它们的情况下才会被销毁。

但是我在这里遇到了另一个问题:向节点添加一个子节点。 weak_ptr 仅在已经有指向对象的 shared_ptr 时才有效。如果我将一个子节点添加到一个节点，我不知道在哪里可以找到指向它的 shared_ptr。那我在这里做什么？

Answer 1

为了扩展 David Rodriguez 的想法，骨架树可能如下所示:

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

(当然，真实世界的 node 会有一个具有有效负载值的非平凡构造函数，而 add_child 会采用类似的参数或者是一个模板...)