实现树结构最安全的方法是什么？

Question

我想在我的程序中创建一个树结构.现在我有类似于以下内容:

class tree_node
{
    public:
        tree_node (tree_node* parent) : parent_(parent)
        {
            parent_.add_child(this);
        }

    private:
        std::vector<tree_node*> children_;
        tree_node* parent_;
}

我对这个设计的主要关注是tree_node该类可以删除它的任何子节点和父节点.我想改变设计以禁止这种情况.所以:

• 我可以以某种方式更改设计以使用引用而不是指针吗？(引用的向量不起作用).
• 如果我使用引用,我如何处理根节点(没有父节点)的特殊情况？
• 我可以禁止在tree_node课堂上删除孩子/父母吗？

欢迎任何其他实现我的目标的想法.

Answer 1

一个安全的解决方案是将子项存储为boost :: shared_ptr并将父项存储为原始指针.然后根节点将其父节点设置为null.

回答你的问题:

• 我可以以某种方式更改设计以使用引用而不是指针吗？(引用的向量不起作用).

在这种情况下你必须使用指针.参考文献根本不起作用.

• 我可以禁止tree_node类删除子/父吗？

在设计树时,最常识的所有权模型将是节点拥有其子节点的所有权,反之亦然.

你是说你想禁止一个班级为自己做点什么.这有什么意义？如果您不希望您的班级删除自己的孩子,那么就不要这样做.

Answer 2

编辑:回答标题中提到但不在文本中提出的问题:最安全的方法是不重新实现树.使用标准库关联容器或可能提升BGL.

您可以在容器中使用引用包装器类(boost::optional如果需要,还可以使用父引用的包装器),但我不确定这是否是您的基础问题的解决方案.该tree_node所以没有删除的特定风险类并没有做任何的内存管理.

接下来,你真的需要一棵N树吗？你可以逃避std::map或其他一个关联容器,并避免编写一堆错误？

显然,你的树的公共API不应该提供对节点类的直接访问(检查map和使用迭代器),所以只要树正确管理内存,你对指针管理的担忧应该是最小的,因为你完全控制所有管理节点.