0

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.

22
  • 2
    QuadTree nodes_[4]; does not work because the size of QuadTree would be infinite since every QuadTree will contain an array of 4 QuadTree each will contain an array of 4 ... Commented Jun 3, 2019 at 10:52
  • 1
    Correct. You cannot use an array. C++ simply does not work this way. You can use a std::vector, though. Commented Jun 3, 2019 at 10:56
  • 1
    What you're "trying to achieve" is a Java program, and not C++. Java is not C++, and objects and classes work fundamentally differently, in these two languages. Commented Jun 3, 2019 at 10:59
  • 1
    If you want a static array of 4 QuadTree objects I recommend that you create a second class that contains these. Commented Jun 3, 2019 at 11:01
  • 1
    A Java array and a C++ array are quite different things, because of semantics of the languages. In C++, a std::vector is closer to being equivalent to a Java array than a C++ array is. That's just the way it is. Commented Jun 3, 2019 at 11:02

4 Answers 4

3

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.

Sign up to request clarification or add additional context in comments.

7 Comments

Note that std::vector is bigger than just a pointer, and that overhead will be multiplied by the number of nodes. Custom data structures are a rare case where using a custom wrapper for a dynamic array may be preferable.
Agreed - make a vector-like class with fixed bounds 👍
In above split method(the first type with array) nodes_ = new Quadtree[4] { { /* TODO QuadTree args / }, { / TODO QuadTree args / }, { / TODO QuadTree args / }, { / TODO QuadTree args */ } }; It is giving error that 'expected a type specifier'
@mevitex I typoed QuadTree as Quadtree, but beyond that, it works for me.
@Peter the overhead is not multiplied by the number of vector elements. The overhead is multiplied by the number of vector objects. And each node contains a vector. Therefore the overhead of the vector (compared to pointer) is multiplied by the number of nodes. Tracking the number of elements is in fact the reason for the bigger size, and that feature is unused when the size is constant.
|
1
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.

4 Comments

Actually in constructor I just want to initialize array with null pointer.
You don't need an array of 4 QuadTree*. You just need one QuadTree* that points to an array of 4 QuadTrees.
How to declare that? Can you please write syntax here?
Your book probably explains dynamically allocating arrays!
0
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.

Comments

-1

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

5 Comments

The array is fixed size. Initializing it with a loop, in constructor body, is doubly an antipattern. Yes, it is correct. It is also a poor example.
@JanHudec, yes, you're right, there's better choice. I've revised the answer based on your suggestion. Thx.
No, memset is not a better choice. As far as I can tell there is nothing that would guarantee null pointers are actually represented with zeroes, though all practical compilers I've ever heard of do it that way. But they don't have to, so memset is actually Undefined Behaviour™. And the antipattern is sill there.
memset is a poor choice. std::fill at the very least plz for type safety
Yes, this is not good enough. Actually I prefer @eerorika's way to initialize, after I saw it: class QuadTree{ QuadTree* nodes_[4] = {};

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.