带有智能指针的 N 叉树设计

Question

我正在尝试用 C++ 设计一个树类，但在节点破坏方面遇到了一些麻烦。

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

但是我在这里遇到了另一个问题：向节点添加子节点。 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

将采用类似的参数或成为模板......）

Answer 2

您可能想研究一下

enable_shared_from_this

，它允许您直接从对象获取

shared_ptr

。它仍然要求该对象由

shared_ptr

管理，但您不需要 找到 谁持有它。

Answer 3

我认为你需要考虑的是需要有一棵共享节点的树。我认为这种事情会很疯狂，但如果你想让它变得简单一些，请考虑这个：

1. 使用地图或向量来实际保存节点并管理它们的生命周期。你有一个shared_ptrs的地图，你就可以开始了。

2. 对于树，将子节点与其指向的项目分开。这个想法是，您在每个树节点本身上使用shared_ptr甚至唯一的指针。这样，当您释放一个节点时，它会很好地处理所有子节点，但是，您不会释放可能重复的项目。

3. 在树节点中使用弱指针来指向有效负载。

类似这样的：

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;
};

类似这样的事情。如果 P 不是多态的，则在某些情况下可以实现一些效率。但是，您得到的是一个类存储，它会自动释放所有数据结构以创建该存储，即项目、树、索引，并且如果您从数据中删除节点并将其破坏，则在该节点上调用 lock()指向它的弱指针会让你做一些事情。