我通过为每个节点创建一个类来建模一个通用的树结构,该类包含指向父、第一个子和第一个兄弟的指针,以及一个指向最后一个兄弟的指针(不需要,但很有用)。为此,我添加了一些额外的数据 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/