我通过为每个节点创建一个类来建模一个通用的树结构,该类包含指向父、第一个子和第一个兄弟的指针,以及一个指向最后一个兄弟的指针(不需要,但很有用)。为此,我添加了一些额外的数据 atd。我目前的实现是:

class TreeNode {
    typedef boost::shared_ptr<TreeNode> Ptr;
    typedef boost::weak_ptr<TreeNode> WPtr;

    WPtr p2parent;     ///< pointer to the parent node (NULL in the root)
    Ptr p2sibling;     ///< pointer to the first sibling (or NULL)
    Ptr p2child;       ///< pointer to the first child (or NULL)
    WPtr p2lastChild;  ///< pointer to the last child (not strictly needed)
};

如您所见,我使用 shared_ptr 作为兄弟和 child ,因此可以通过删除其根来删除整个树。对于指向父级的指针,我知道我不应该使用 shared_ptr,因为这会产生循环,所以我必须在 weak_ptr 和原始指针 (TreeNode *) 之间进行选择 - 有什么想法吗?

对于指向最后一个 child 的(可选)指针,选择是在weak_ptr、shared_ptr 和原始指针之间 - 使整个类在内部保持一致的最佳选择是什么?

最后,我在结构上有几个迭代器,例如深度优先迭代器 atd。迭代器内部应该使用哪些指针:原始指针、weak_ptr 或 shared_ptr?这三种方法的优点是什么?

最佳答案

shared_ptr 完全是矫枉过正:它是一棵树,因此没有节点的共享所有权。每个节点都有一个所有者:它的父节点。

如果您使用的实现支持它,您应该将 std::unique_ptr 用于两个子指针和指向根节点的指针。如果您的实现不支持 std::unique_ptr ,您可以使用 std::auto_ptr 但您需要明确地使节点类不可复制。在任何一种情况下,您都可以使用原始指针作为返回父级的指针。

(请注意,无论您使用哪种类型的指针,您都需要为树类编写复制构造函数和复制赋值运算符:隐式声明的指针没有正确的语义。)

迭代器只需要一个指向它指向的元素的原始指针。

关于c++ - 用于建模一般树结构及其迭代器的智能指针,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/6679482/

10-11 22:42
查看更多