Pointers vs auto_ptr vs shared_ptr

Question

I was recently introduced to the existence of auto_ptr and shared_ptr and I have a pretty simple/naive question.

I try to implement a data structure and I need to point to the children of a Node which (are more than 1 and its) number may change. Which is the best alternative and why:

class Node
{
    public:
        // ...
        Node *children;

    private:
        //...
}

class Node
{
    public:
        // ...
        share_ptr<Node> children;

    private:
        //...
}

I am not sure, but I think auto_ptr does not work for arrays. I am not, also, sure about whether I should use double pointers. Thanks for any help.

Solution 1

You're right that auto_ptr doesn't work for arrays. When it destroys the object it owns, it uses delete object;, so if you used new objects[whatever];, you'll get undefined behavior. Perhaps a bit more subtly, auto_ptr doesn't fit the requirements of "Copyable" (as the standard defines the term) so you can't create a container (vector, deque, list, etc.) of auto_ptr either.

A shared_ptr is for a single object as well. It's for a situation where you have shared ownership and need to delete the object only when all the owners go out of scope. Unless there's something going on that you haven't told us about, chances are pretty good that it doesn't fit your requirements very well either.

You might want to look at yet another class that may be new to you: Boost ptr_vector. At least based on what you've said, it seems to fit your requirements better than either auto_ptr or shared_ptr would.

Solution 2

I have used std::vector<std::shared_ptr<Node> > children successfully in a similar situation.

The main benefit of using a vector of shared_ptrs rather than an array is that all of the resource management is handled for you. This is especially handy in two situations:
1) When the vector is no longer in scope, it automatically calls delete on all of its contents. In this case, the reference count of the child Node will drop by 1 and if nothing else is referencing it, delete will be called on the object.
2) If you are referencing the Node elsewhere, there is no risk of being left with a dangling pointer to a deleted object. The object will only be deleted when there are no more references to it.

Unless you want behaviour that is substantially more complicated (perhaps there is a reason why an array is necessary), I would suggest this might be a good approach for you.

A simple implementation of the idea:

class Node {
private:
    T contents;
    std::vector<std::shared_ptr<Node> > children;

public:
    Node(T value) : contents(value) {};

    void add_child(T value) { 
        auto p = std::make_shared<Node>(value); 
        children.push_back(p); 
    }

    std::shared_ptr<Node> get_child(size_t index) { 
        // Returning a shared pointer ensures the node isn't deleted
        // while it is still in use.
        return children.at(index);
    }

    void remove_child(size_t index) { 
        // The whole branch will be destroyed automatically.
        // If part of the tree is still needed (eg. for undo), the
        // shared pointer will ensure it is not destroyed.
        children.erase(children.begin() + index); 
    }

};

Solution 3

auto_ptr is deprecated in favor of std::unique_ptr and btw. std::unique_ptr does work for arrays. You just need c++11 support. And there is already lots of resources about smart pointers and move semantics out there. The main difference between auto_ptr and unique_ptr is that auto_ptr does a move when you call the copy constructor and unique_ptr forbids the copy constructor, but allows a move when calling the move constructor. Therefore you need c++11 support with move semantics.

Solution 4

Stroustrup discusses the question of "What is an auto_ptr and why isn't there an auto_array" and concludes that there no need for the latter since the desired functionality can be accomplished with a vector.

http://www.stroustrup.com/bs_faq2.html#auto_ptr

View more solutions

Comments

[Dimitris Leventeas]

Thanks! So I get that I should go with either ptr_vector or Node * children. Could not I use auto_ptr to point to an std::vector of Nodes? Furthermore, is the Node * children right or I should prefer Node ** children? I am a bit confused. Sorry for packing too many questions here.

[Jerry Coffin]

@myle: Without knowing more about what you're doing, it's hard to say for sure. Basically, a Node * will give you one point to an arbitrary number of Nodes, so those nodes will basically be part of their parent, not just linked to it. A Node ** will let you have a dynamic array of pointers to nodes, but you'll have to manage the dynamic array yourself.

[QuesterZen]

Also, note that you can provide your own destructor to a shared_ptr so you could use one to manage an array by calling delete[] instead of plain delete.

[QuesterZen]

The simplest (but slightly ugly) way to add a custom deleter for arrays is to use a lambda function, which is passed into the constructor as an extra argument. Eg.: std::shared_ptr<T> sp(new T[n], [](T *p){ delete[] p; }). For unique_ptrs there is a special version provided for this: 'std::unique_ptr<T[]> up(new T[n])' which calls delete[] instead of delete.