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.

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

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

};