Problems with c++ quadtree

Question

I'm implementing a quadtree in a library, and the compiler keeps on throwing errors talking about an incomplete type: quadtree.h

template<int capacity,
         typename t,
         typename = std::enable_if<std::is_base_of<hasDim, t>::value && std::is_pointer<t>::value>>
struct quadtree {
    bool divided = false;
    quadtree<capacity, t>* nw,* ne,* sw,* se;
    std::vector<t> objs;
    rect2 b;

    quadtree(rect2 bounds): b(b) {}

    void addObj(t);
    void divide();
    void assign(t);
    void empty();
};

bin.cpp

#include "quadtree.h"

template<int capacity,
         typename t,
         typename = std::enable_if<std::is_base_of<hasDim, t>::value && std::is_pointer<t>::value>>
void quadtree<capacity, t>::addObj(t o) {
    if(!divided) {
        objs.push_back(o);
        if(objs.size() > capacity) {
            divide();
        }
    } else {
        assign(o);
    }
}

template<int capacity,
         typename t,
         typename = std::enable_if<std::is_base_of<hasDim, t>::value && std::is_pointer<t>::value>>
void quadtree<capacity, t>::divide() {
    divided = true;
    nw = new quadtree<capacity, t>(rect2(b.x(), b.y(), b.w()/2, b.h()/2));
    ne = new quadtree<capacity, t>(rect2(b.x()+b.w()/2, b.y(), b.w()/2, b.h()/2));
    sw = new quadtree<capacity, t>(rect2(b.x(), b.y()+b.h()/2, b.w()/2, b.h()/2));
    se = new quadtree<capacity, t>(rect2(b.x()+b.w(), b.y()+b.h(), b.w()/2, b.h()/2));
    for(auto o: objs) {
        assign(o);
    }
    objs.resize(0);
}

template<int capacity,
         typename t,
         typename = std::enable_if<std::is_base_of<hasDim, t>::value && std::is_pointer<t>::value>>
void quadtree<capacity, t>::assign(t o) {
    rect2 orect = o.makeRect();
    if(orect.intersects(nw.bounds)) {nw.addObj(o);}
    if(orect.intersects(ne.bounds)) {ne.addObj(o);}
    if(orect.intersects(sw.bounds)) {sw.addObj(o);}
    if(orect.intersects(se.bounds)) {se.addObj(o);}
}

template<int capacity,
         typename t,
         typename = std::enable_if<std::is_base_of<hasDim, t>::value && std::is_pointer<t>::value>>
void quadtree<capacity, t>::empty() {
    if(divided) {
        divided = false;
        nw.empty(); ne.empty(); sw.empty(); se.empty();
        delete nw, ne, sw, se;
    } else {
        objs.resize(0);
    }
}

According to microsoft, an incomplete type is one whose size can't be determined, but here I have no idea where this could come from: bool divided can be determined; the quadtree<capacity, t>*s are, well, pointers, whose size can be determined; std::vector<t> objs is a vector, which means it stores a dynamically allocated array, which means it's size can be determined as well; same goes for rect2 b which only stores 4 doubles. Any idea where the problem could come from?

EDIT:

Here's the error message:

bin.cpp:32:40: error: invalid use of incomplete type 'struct quadtree<capacity, t>'
   32 |  void quadtree<capacity, t>::addObj(t o) {
      |

score 1 · Answer 1 · answered Apr 04 '20 at 21:43

According to microsoft, an incomplete type is one whose size can't be determined

That's not what "incomplete type" means. That's a property that applies to types that are incomplete.

An incomplete type is one that has not been defined. Example:

class X;            // this is not a definition; X is incomplete
auto s = sizeof(X); // program is ill-formed because size of X is not known

Defining member functions of a class is another thing that cannot be done for an incomplete type. Example:

class Y;            // this is not a definition; Y is incomplete
Y::Y() {}           // program is ill-formed because Y is incomplete

Back to your problem: You attempt to define member functions of quadtree within bin.cpp, even though bin.cpp does not contain the definition of quadtree. quadtree must be defined first. Simply include the header which contains the definition.

It is included, I don't show it in the question because bin.cpp holds implementations for the entire library and the includes are at the top of the file. anyway I double checked, and it is actually there. thanks anyway :) — lenerdv, Apr 04 '20 at 21:53
@leonardovegetti Well, I can only solve problems that are in the example; I cannot guess what problems are or aren't in some other program. The header is not included in the example. — eerorika, Apr 04 '20 at 21:54

score 0 · Answer 2 · answered Apr 04 '20 at 21:50

In quadtree.h, you define the structure, but inside the structure you are already using it in the inline definition of the constructor (quadtree(rect2 bounds): b(b) {}), this is not allowed, as it is not fully defined yet. The compiler cannot produce the constructor's code, because it doesn't yet know how much more data members might come.

You can avoid the problem by only declaring the constructor: quadtree(rect2 bounds): b(b);, and then separately (after the }of the struct) adding its definition template<...> quadtree::quadtree(rect2 bounds) {}

tried, but nothing changed apart from the fact that the error is also thrown for the constructor — lenerdv, Apr 04 '20 at 21:57

score 0 · Answer 3 · answered Apr 05 '20 at 01:29

The problem is with how you define the member functions that belong to the template class.

In your declaration of the class, you say that quadtree is a template that takes 3 parameters, but when you go to define the member functions you only list two.

To fix it, you need to just specify that the template is taking those three parameters:

template<int capacity,
         typename t,
         typename z>
void quadtree<capacity, t, z>::divide() {

You don't specify the default value for the 3rd parameter here because you've already done that when you declared the template.

As an alternative you can just define the functions inline in the template class definition.

And keep in mind that template class definitions need to go in the header file, not a .cpp file.

score 0 · Accepted Answer · answered May 03 '21 at 16:38

Me from (quite a bit in) the future, the solution was to ditch the std::enable_ifs. It's still unclear to me why they were causing problems, but replacing those with one static_assert in the class body was enough to fix the problem. Anyway, kids, don't use this code. It's terrible.

Problems with c++ quadtree

4 Answers4