How to declare array of same class type in header file?

Question

I am new to c++. I have a class called QuadTree. Now QuadTree can contain array of 4 other QuadTree. Either they all have values or they all will be null. So in my class header file QuadTree.h is as below.

    class QuadTree
    {
    public:
        QuadTree();
        ~QuadTree();

        void Clear();

    private:
        QuadTree nodes_[4];

    };

but this nodes_ declaration show error that

'incomplete type is not allowed'.

I have also tried

  QuadTree* nodes_[4];

then when I initialize in constructor

nodes_ = new QuadTree[4];

It gives me error 'expression must be a modifiable value'. I can declare that as list or something. but it's size is constant(always 4). So I want to use array. Please help me to declare in header file and how to initialize in constructor in QuadTree.cpp file.

Answer 1

A class cannot contain instances of itself. Doing so would require the class to be infinitely large, since each sub-object would contain a sub-sub-object, which would contain a sub-sub-sub-object, etc.

What a class can contain, is pointers to objects of its own type. Since a pointer can be null, it's possible to stop the infinite loop and only have a finite number of objects.

That means the following will work:

class QuadTree
{
public:
    QuadTree() : nodes_{nullptr}
    {
    }

    ~QuadTree() { delete[] nodes_; }

    // I've deleted these to make a QuadTree non-copyable.
    // You'll need to implement them to do a deep copy if you want that
    QuadTree(const QuadTree& other) = delete;
    QuadTree& operator=(const QuadTree& other) = delete;

    void Clear();

    void split() {
        nodes_ = new QuadTree[4] {
            { /* TODO QuadTree args */ },
            { /* TODO QuadTree args */ },
            { /* TODO QuadTree args */ },
            { /* TODO QuadTree args */ }
        };
    }

private:
    QuadTree* nodes_;
};

A smart pointer like std::unique_ptr could clean up the memory management a bit:

class QuadTree
{
public:
    // No longer have to explicitly initialize nodes_ to nullptr
    // since a default-constructed unique_ptr is null
    QuadTree();

    // No longer need to delete[] here; unique_ptr handles that for us
    ~QuadTree();

    // Copy constructor and assignment are now implicitly deleted since
    // unique_ptr is non-copyable.
    // You'll need to implement them to do a deep copy if you want that

    void Clear();

    void split() {
        nodes_.reset(new QuadTree[4] {
            { /* TODO QuadTree args */ },
            { /* TODO QuadTree args */ },
            { /* TODO QuadTree args */ },
            { /* TODO QuadTree args */ }
        });
    }

private:
    std::unique_ptr<QuadTree[]> nodes_;
};

To avoid the manual memory management, you could use a std::vector<QuadTree> instead of a raw QuadTree*. This comes with a small amount of memory overhead, since each std::vector has to track its size, but it makes it much less likely you'll end up with memory corruption issues, so it's likely worth it. Memory is cheap these days.

class QuadTree
{
public:
    QuadTree();
    ~QuadTree();

    // QuadTree is now implicitly copyable, since std::vector does a deep-copy by default

    void Clear();

    void split() {
        nodes_ = {
            { /* TODO QuadTree args */ },
            { /* TODO QuadTree args */ },
            { /* TODO QuadTree args */ },
            { /* TODO QuadTree args */ }
        };
    }

private:
    std::vector<QuadTree> nodes_;
};

To avoid the memory overhead of std::vector while keeping nice clean code, you could implement your own vector-like class with a static size. Writing such a class is a bit beyond the scope of a SO answer though.

Answer 2

class QuadTree
{
    QuadTree nodes_[4];

This is not possible because if every QuadTree contains 4 QuadTrees, and all of those QuadTrees contain 16 QuadTree children total, and all of those QuadTrees contain 256 total ... up to infinity QuadTrees. You cannot have a type of infinite size. It is also not possible because it is not possible to declare an array of incomplete type, and the class is incomplete within its definition (except the complete-class context, but that does not apply here).

A tree is a linked data structure. Therefore you should be using links i.e. pointers to connect the nodes:

class QuadTree
{
    QuadTree* nodes_[4];

---

then when I initialize in constructor

nodes_ = new QuadTree[4];

Arrays are not assignable.

And, you really shouldn't create instances of QuadTree within the constructor of QuadTree unconditionally or else you have an infinite recursion, and will overflow your stack.

A default initialised QuadTree should probably not have any children. In other words, the child pointers should either point to null, or the sentinel object depending on the design of your data structure. In order to initialise an array of pointers to null, you can use value-initialisation. Simplest is to use a default member initialiser:

class QuadTree
{
    QuadTree* nodes_[4] = {};

---

Alternative consideration: Using std::unique_ptr might be a better choice than a bare pointer.

Performance consideration: If the tree always has either 0 or 4 children, then creating all children in one array, and having a pointer to that array is preferable. See Miles Budnek's answer for more details.

Answer 3

QuadTree* nodes_[4];

That's one option—an array of four pointers to child nodes. Another option is

QuadTree *nodes_;

which is a pointer to array of nodes. You have to keep track of the length separately, but if it is always 4 it's clear—it only allows you to have no or exactly 4 children nodes though.

---

nodes_ = new QuadTree[4];

is initialization for the later. It returns a pointer to an array of four instances of QuadTree.

In the former case, the array is embedded in the object, so you initialize each member separately.

First, you should initialize it to contain four null pointers in the constructor. You do that like

QuadTree::QuadTree() : nodes_() {}

The initialization of arrays is a bit tricky, but nullptr is the default value here, so explicit initialization does what you need.

Then when you actually need the children, you simply do

nodes_[n] = new QuadTree();

You should probably have a parametric constructor that will initialize the other members so you don't start out with invalid objects.

---

However, in this day and age, what you should really be using is either

std::unique_ptr<QuadTree> nodes_[4];

an array of smart pointers, that will take care of deleting the child nodes when you delete the parent—because in C++ you must manage your memory. Or, for the second option, use

std::vector<QuadTree> nodes_;

vector is an array that will manage it's length—you have to make sure the QuadTree has correct move constructor though.

Answer 4

First, yes, you can only use pointer array in this case. Otherwise, it will be an endless cycle.

Second, you don't have to call 'new' for the array, since it's been already allocated when the object was created.

so you can use it directly

QuadTree::QuadTree() {
    for (int i = 0; i < 4; i++) {
        nodes_[i] = 0;
    }
}

or

QuadTree::QuadTree() {
    memset(nodes_, 0, sizeof(nodes_));
}