Are data structures an appropriate place for shared_ptr?

Question

I'm in the process of implementing a binary tree in C++. Traditionally, I'd have a pointer to left and a pointer to right, but manual memory management typically ends in tears. Which leads me to my question...

Are data structures an appropriate place to use shared_ptr?

Answer 1

I think it depends on where you'd be using them. I'm assuming that what you're thinking of doing is something like this:

template <class T>
class BinaryTreeNode 
{
    //public interface ignored for this example
    private:
        shared_ptr<BinaryTreeNode<T> > left;
        shared_ptr<BinaryTreeNode<T> > right;
        T data;
}

This would make perfect sense if you're expecting your data structure to handle dynamically created nodes. However, since that's not the normal design, I think it's inappropriate.

My answer would be that no, it's not an appropriate place to use shared_ptr, as the use of shared_ptr implies that the object is actually shared - however, a node in a binary tree is not ever shared. However, as Martin York pointed out, why reinvent the wheel - there's already a smart pointer type that does what we're trying to do - auto_ptr. So go with something like this:

template <class T>
class BinaryTreeNode 
{
    //public interface ignored for this example
    private:
        auto_ptr<BinaryTreeNode<T> > left;
        auto_ptr<BinaryTreeNode<T> > right;
        T data;
}

If anyone asks why data isn't a shared_ptr, the answer is simple - if copies of the data are good for the client of the library, they pass in the data item, and the tree node makes a copy. If the client decides that copies are a bad idea, then the client code can pass in a shared_ptr, which the tree node can safely copy.

Answer 2

Because left and right are not shared boost::shared_ptr<> is probably not the correct smart pointer.

This would be a good place to try std::auto_ptr<>

Answer 3

Yes, absolutely.

But be careful if you have a circular data structure. If you have two objects, both with a shared ptr to each other, then they will never be freed without manually clearing the shared ptr. The weak ptr can be used in this case. This, of course, isn't a worry with a binary tree.

Answer 4

Writing memory management manually is not so difficult on those happy occasions where each object has a single owner, which can therefore delete what it owns in its destructor.

Given that a tree by definition consists of nodes which each have a single parent, and therefore an obvious candidate for their single owner, this is just such a happy occasion. Congratulations!

I think it would be well worth* developing such a solution in your case, AND also trying the shared_ptr approach, hiding the differences entirely behind an identical interface, so you switch between the two and compare the difference in performance with some realistic experiments. That's the only sure way to know whether shared_ptr is suitable for your application.

(* for us, if you tell us how it goes.)

Answer 5

Never use shared_ptr for the the nodes of a data structure. It can cause the destruction of the node to be suspended or delayed if at any point the ownership was shared. This can cause destructors to be called in the wrong sequence. It is a good practice in data structures for the constructors of nodes to contain any code that couples with other nodes and the destructors to contain code that de-couples from other nodes. Destructors called in the wrong sequence can break this design.

Answer 6

There is a bit of extra overhead with a shared_ptr, notably in space requirements, but if your elements are individually allocated then shared_ptr would be perfect.

Answer 7

Do you even need pointers? It seems you could use boost::optional<BinaryTreeNode<T> > left, right.