Tree Node class - deallocation in the destructor

Is my destructor correct? Does it properly deallocate the subtrees?

#ifndef HEADER_GUARD__TREE
#define HEADER_GUARD__TREE

#include 

namespace Sandbox {
    class Node {
    public:
        Node();
        Node( Node* parent );
        virtual ~Node();

        Node* GetFirstChild();
        Node* GetChild( int index );
        Node* GetLastChild();

        void AppendChild( Node* child );
        void AddChild( Node* child ,int index );
        void RemoveChild( int index );

        int  GetIndex() { return _index; }
        void SetIndex( unsigned int index ) { _index = index; };
    protected:

    private:
        Node* _parent;
        int _index;
        std::deque* _children;
    };
}

#endif // HEADER_GUARD__TREE

Node::Node(): _parent(NULL), _index(NULL), _children(NULL){
    _children = new std::deque;
    _index = 0;
}
Node::Node( Node* parent ): _parent(parent), _index(NULL), _children(NULL){
    _children = new std::deque;
    _index = 0;
    _parent->AppendChild( this );
}
Node* Node::GetFirstChild(){
    return _children->front();
}
Node* Node::GetChild( int index ){
    return _children->at(index);
}
Node* Node::GetLastChild() {
    return ( _children->back() );
}

void Node::AppendChild( Node* child ) {
    _children->push_back( child );
    unsigned int index = _children->size();
    child->SetIndex( index );
}
void Node::AddChild( Node* child ,int index ) {
    std::deque::iterator i = _children->begin();
    i = i + index;
    _children->insert( i, child );
    child->SetIndex( index );
}
void Node::RemoveChild( int index ) {
    std::deque::iterator i = _children->begin();
    i = i + index;
    _children->at(index)->~Node();
    _children->erase( i );
}
Node::~Node() {
    _parent = NULL;
    _index = 0;
    for(int i = 0; i >= _children.size(); i++ ) {
        _children->at(index)->~Node();
    }
    _children->clear();
    delete _children;
}

This is not real C++ code.

This is C written with a couple of classes.

Pointers are dangerous and should rarely be used in code. C++ has moved away from C in this regard over the last decade and all pointers should be either wrapped in a smart pointer or be part of a container structure.

For this a technique called RAII has been introduced. This is the concept that creation and destruction of an object are linked within the objects lifetime thus allowing you to control resources even in the face of exceptions.

There are a couple of ways to fix the code.

The simplest technique is to just use std::unique_ptr (or std::auto_ptr if you are using C++03).

Node( Node* parent );

Are you passing ownership of the parent?

No. You have a seprat constructor for no parent and ownership is not being passed as a result you should pass the parent by reference (if it has a parent it must not be NULL and must exist).

Node( Node& parent );

All these methods that return pointer.

Should they?

Node* GetFirstChild();
    Node* GetChild( int index );
    Node* GetLastChild();

If there is a possibility of NULL then yes, otherwise return a reference.

Here you are adding a child:

void AppendChild( Node* child );
    void AddChild( Node* child ,int index );

But there is no indication you are passing ownership. The person reading the code has to know how the internals of how your class works. Otherwise they do not know if the pointer passed should be dynamically allocated or not. You need to make this knowledge explicit in the interface. Here I would pass a unique_ptr to indicate that you are passing ownership of the pointer into the node.

OK. Parent is allowed to be a pointer.

Node* _parent;

You do not own the object and it is possible to be NULL. There is no responsibility for this node to clean up its parent.

_children should not be a pointer. It should be an object. Thus allows automatic cleanup and no requirement to manually create it. Also this simplifies the copy construction and assignment operator (that you have currently failed to define).

Secondly the container should not be holding pointer. Here you have an option either it should be a container of smart pointers, or it should be a container designed specifically to hold ownership of pointers (so that it can be done safely).

// Option 1:
    std::deque> _children;

    // Option 2:
    boost::ptr_deque            _children;

Personally I prefer option 2. As the contain provides access to the pointers as if they were normal objects. This makes writing functors and the interacting with the standard algorithms much easier.

Also I would question the use of deque over vector but that is a minor detail.
};
}

Secondary Comments:

Do initialization in the initialization list. You sort of try to NULL everything in the initialization list. It is best to actually initialize them and have an empty body.

Node::Node(): _parent(NULL), _index(NULL),             _children(NULL){
                      ^^^^ OK       ^^^^ Questionable  ^^^^^^^^ Should be an object

Node::Node( Node* parent ): _parent(parent), _index(NULL),     _children(NULL){
                                    ^^^^^^ OK       ^^^^ Questionable

In the constructor that takes a parent you don't check your input for NULL

// If somebody passes a NULL parent then this is no good.
_parent->AppendChild( this );

The use of your functions should be consistent.

Getting the first and last children can be badly defined if the node has no children. But the generic GetChild() function will throw an exception if you try and retrieve a child from an invalid index. These two different behaviors makes using your code hard to be consistent. I would change these so that they all or none throw an exception.

Node* Node::GetFirstChild(){
    return _children->front();
}
Node* Node::GetLastChild() {
    return ( _children->back() );
}
Node* Node::GetChild( int index ){
    return _children->at(index);
}

Manually calling the destructor is wrong here:

_children->at(index)->~Node();

Unless you allocated the memory in some other way the used 'Placement New' you should not be calling the destructor manually. But nothing in your interface indicates that. So this should be a normal call to delete.

delete _children->at(index);

When inserting a child into the middle is it intentional to only set the index of the inserted child?

void Node::AddChild( Node* child ,int index ) {
    std::deque::iterator i = _children->begin();
    i = i + index;
    _children->insert( i, child );

    // You set this node
    // But what about the nodes from index+x to the end.
    // Currently their internal index is unchanged.
    //     This could be intentional but it is hard to tell without a comment.
    child->SetIndex( index );
}

I would try something like this:

```
#ifndef HEADER_GUARD__TREE
#define HEADER_GUARD__TREE

#include

nam

StackExchange Code Review Q#9015, answer score: 3