smart pointers for modelling a general tree structure & its iterators

Question

I am modelling a general tree structure by having a class for each node with pointers to parent, first child and first sibling, plus a pointer to last sibling (not needed, but useful). To this, I am adding some extra data atd. My current implementation is:

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

As you can see, I am using shared_ptr for sibling and child, so the whole tree can be deleted just by deleting its root. For the pointer to parent, I know I shouldn't use shared_ptr, since this would create cycles, so I have to choose between weak_ptr and a raw pointer (TreeNode *) - any thoughts?

For the (optional) pointer to the last child, the choice is between weak_ptr, shared_ptr and a raw pointer - what is the best choice, to make the whole class internally consistent?

Finally, I have a couple of iterators over the structure, such as a depth-first iterator atd. What pointers should the iterators use internally: raw pointer, weak_ptr, or shared_ptr? What are the advantages of the three approaches?

Answer 1

shared_ptr is total overkill: it's a tree so there is no shared ownership of nodes. Each node has a single owner: its parent.

If the implementation you are using supports it, you should use std::unique_ptr for the two child pointers and for the pointer to the root node. If your implementation doesn't support std::unique_ptr, you can use std::auto_ptr but you'll want to explicitly make the node class noncopyable. In either case, you can use a raw pointer for the pointer back to the parent.

(Note that you'll need to write a copy constructor and copy assignment operator for the tree class regardless of the type of pointer you use: the implicitly declared ones do not have the correct semantics.)

An iterator only needs a raw pointer to the element to which it points.