用于建模一般树结构及其迭代器的智能指针

Question

我正在通过为每个节点提供一个类来建模一个通用树结构，该类带有指向父级、第一个子级和第一个同级的指针，以及指向最后一个同级的指针(不需要，但很有用(。为此，我添加了一些额外的数据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，因此只需删除其根即可删除整个树。对于指向父级的指针，我知道我不应该使用 shared_ptr，因为这会产生循环，所以我必须在 weak_ptr 和原始指针 (TreeNode *( 之间进行选择 - 有什么想法吗？

对于指向最后一个子项的(可选(指针，选择在 weak_ptr、shared_ptr 和原始指针之间 - 使整个类内部一致的最佳选择是什么？

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

Answer 1

shared_ptr完全是矫枉过正：它是一棵树，所以没有节点的共享所有权。 每个节点都有一个所有者：其父节点。

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

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

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

Answer 2

对于父指针：您必须确保它始终指向父级中子级的 setter 中的实际父级，因此向 Treenode 析构函数添加 unset 相对简单。在这种情况下，哑指针就可以了。

对于最后一个子指针：保持最新状态需要做更多的工作，如果你做这项工作，你会发现你涵盖了所有情况，不需要任何其他情况的智能指针。所以哑指针在这里也可以。

您可以使用weak_ptr来获得一点额外的安全性，尽管您实际上应该断言它们没有过期，因为这意味着您忘记取消设置它们，这可能意味着您没有正确管理它们。

迭代器：应使用智能指针。

• 如果他们使用 shared_ptr ，即使您修改树并断开它，它们也会保持子树的活动状态。
• 如果他们使用 weak_ptr ，则在删除指向的节点时，它们将使自己失效(您必须检查指针在许多地方是否仍然有效(。

选择取决于所需的语义。