CODEWITHSUNDEEP
c++data-structuresshared-ptrtr1
Gabriel Isenberg
Gabriel Isenberg

Reputation: 26341

Are data structures an appropriate place for shared_ptr?

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?

Upvotes: 5

Views: 1448

Answers (7)

John Morrison
John Morrison

Reputation: 517

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.

Upvotes: 1

MSalters
MSalters

Reputation: 179991

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

Upvotes: 0

Harper Shelby
Harper Shelby

Reputation: 16583

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.

Upvotes: 8

Loki Astari
Loki Astari

Reputation: 264621

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<>

Upvotes: 3

Daniel Earwicker
Daniel Earwicker

Reputation: 116714

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.)

Upvotes: 2

Mark Ransom
Mark Ransom

Reputation: 308432

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.

Upvotes: 0

David Norman
David Norman

Reputation: 19889

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.

Upvotes: 2

Related Questions