Class with a pointer to itself

I need to make a quadtree.

I have:

Code:

---

class Quadtree
{
public:
    ...
private:
    Quadtree children[4];
    ...
};

---

I get an error saying: "error: field 'children' has an incomplete type"

Can anyone tell me what is wrong?

Thank you.

A struct/class can't contain a copy of itself!
Otherwise it would recursively fill memory as soon as you tried to instantiate it.

Quadtree *children[4];
fixes this.

An array is not a pointer. Here, you have a class that has an array with 4 elements of the same class. This is impossible, since your Quadtree object contains 4 Quadtree objects, each of which contains 4 Quadtree objects, each of which contains 4 Quadtree objects, etc.

What you can do is really store a Quadtree pointer, and then have this pointer point to the first element of an array of 4 Quadtree objects.

EDIT:
Oh yes, storing 4 Quadtree pointers, each of which points to exactly one Quadtree object, also works.

Ok, that makes sense. I tried using Quadtree *children[4]; but I get a lot of errors.

Why can I not do something like this:

Code:

---

Quadtree::Quadtree()
{
    children = new Quadtree[4];
    for (int i = 0; i < 4; i++)
        children[i] = NULL;
}

---

Anywhere I treat children as an array, I get an error. How can I treat children like an array?

Try changing it to something like this.

Code:

---

class Quadtree
{
private:
    Quadtree *children;

public:
    Quadtree() {
      children = new Quadtree[4];
    }
    ~Quadtree() {
      delete[] children;
    }
};

---

Edit: this will also cause a runtime error as it still recursively allocates Quadtree's, so Salem's method should work.

Wouldn't new Quadtree[4] make an array of quadtrees? Don't you want an array of pointers-to-quadtree?

You already have an array of 4 pointers, so just delete this line
children = new Quadtree[4];

Then when you need them, it's

Code:

---

children[i] = new Quadtree;

---

But you still need to watch out for calling the constructors recursively if you try to fill out a complete tree as soon as you construct it.

Quote:

---

Why can I not do something like this

---

Because children[i] is a Quadtree, not a pointer, assuming that children is a Quadtree pointer. You have to pick either what Salem suggested or what I suggested, not both.

Isn't the real problem that you are creating the children in the constructor of the same class, which makes the constructor infinitely recursive. You can't do THAT!

Likewise, you can't delete inside the destructor.

At the very least you would need to make sure that the constructor and destructor have some sort of condition (if the compiler would allows this sort of thing, it would crash the program either because of out-of-memory or out-of-stack, since you'd never stop calling the constructor, and should you ever end calling the constructor, the same thing happens for the destructor calls.

--
Mats

Ok, I understand. Thank you.

Quote:

---

Isn't the real problem that you are creating the children in the constructor of the same class, which makes the constructor infinitely recursive. You can't do THAT!

Likewise, you can't delete inside the destructor.

---

It depends. A Quadtree object can own another (or 4 other) Quadtree objects, but eventually there must be a Quadtree object that does not own any other Quadtree object.

With my suggestion, the Quadtree pointer can be null. With Salem's suggestion, this can be done by keeping the Quadtree pointers null, which implies that there is greater flexibility (though the placement new trick can be used with my suggestion, but that's a different story).

yahn's most recent code looks like an attempt to use Salem's suggestion with setting the pointers to null, and that would work, except that yahn also tried using my suggestion simultaneously. Considering the definition of a Quadtree though, my suggestion is probably not as good, since a Quadtree is not fixed at 4 children or none, but fixed at up to 4 children (but in my defense, I did not know that at the time).