smart pointers for modelling a general tree struct

问题:

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?

回答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.

回答2:

For parent pointer: You have to ensure it always points to the actual parent in the setters for the children in parent, so adding an unset to the Treenode destructor is comparably simple. In which case dumb pointer will do.

For last child pointer: It's even more work to keep it up-to-date and if you do that work, you'll find out that you covered all cases and don't need smart pointers for any other. So dumb pointer will do here as well.

You can use weak_ptr for a little bit of extra safety, though you should really just assert they are not expired, because that means you forgot to unset them and that likely means you don't manage them correctly.

Iterators: Should use smart pointer.

• If they use shared_ptr, they will keep the subtree alive even when you modify the tree and disconnect it.
• If they use weak_ptr, the will invalidate themselves when the pointed node is deleted (you will have to check that the pointer is still valid in many places).

The choice depends on which semantics you want.