Having attributes of the same class in C++

Question

I want to implement a generic, tree structure with C++ - with classes! - and this tree is composed by a key (which in my case is an integer) and a leftChild and rightChild attributes, which should be both of the same type as the tree itself

In C I can do this like:

typedef struct avl {
    int key;
    int bf;
    struct avl *leftChild;
    struct avl *rightChild;
} AVLTree;

And I attempted the following in my C++ code:

class MTree {
    public:
        int key;
        int bf;

        MTree leftChild;
        MTree rightChild;

        MTree() {}
        ~MTree() {};
 }

But it won't work and it gives me the following error message:

mtree-ops.cpp:12: error: field ‘leftChild’ has incomplete type

mtree-ops.cpp:13: error:error: field ‘rightChild’ has incomplete type

So you see, looks like I can't say my class has an attribute of its own type because that's like trying to make reference to something that doesn't really exist at the time of the definition. How can this be done using C++ classes?

Answer 1

(I cannot post comments yet.)

In short, MTree leftChild would have two MTree children of its own, each of which would have two children, and so on. Thus, MTree objects would be infinitely big, since they would contain infinitely many MTree instances.

See this question which is essentially identical. As mentioned there, you must resort to references or pointers to children, giving individual MTree objects finite size. For example,

class MTree
{
[...]
public:
    MTree* leftChild;
    MTree* rightChild;
};

(You could replace MTree* with MTree&.)

Answer 2

Here is the idomatic C++11 way to do it:

#include <memory>
class MTree {
  public:
    int key;
    int bf;

    std::unique_ptr<MTree> leftChild;
    std::unique_ptr<MTree> rightChild;

    MTree():key(0), bf(0) {}
    ~MTree() {};
};

std::unique_ptr is a smart pointer with next to zero overhead that represents a pointer that the containing struct has ownership over, and which can be nullptr.

To add a child, simply leftChild.reset( new MTree );

When a parent is destroyed, all of its children are destroyed automatically. If you want to take a child from a parent, do std::unique_ptr<MTree> branch = std::move( parent.leftChild );, which claims ownership over the left child and removes it from the parent.

If you just want a non-owning pointer, use parent.leftChild.get(). If you want to access the left child's key, parent.leftChild->key will do it (note: you are responsible for checking for nullptr.

Answer 3

I think your code should look like this

class MTree {
    public:
        int key;
        int bf;

        MTree * leftChild;
        MTree * rightChild;

        MTree() {}
        ~MTree() {};
}