c ++四叉树的问题

Question

我正在一个库中实现一个四叉树，编译器不断抛出关于不完整类型的错误： 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);
    }
}

根据microsoft，不完整的类型是无法确定大小的类型，但是我不知道这可能来自哪里：bool divided可以确定； quadtree<capacity, t>* 是指针，其大小可以确定； std::vector<t> objs 是一个向量，这意味着它存储了一个动态分配的数组，这意味着它的大小也可以确定； rect2 b 也是如此，它只存储 4 个双打。知道问题出在哪里吗？

编辑：

错误信息如下：

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

Answer 1

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

那不是 "incomplete type" 的意思。这是适用于不完整类型的属性。

不完整类型是指尚未定义的类型。示例：

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

定义 class 的成员函数是另一件不能为不完整类型完成的事情。示例：

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

回到您的问题：您试图在 bin.cpp 中定义 quadtree 的成员函数，即使 bin.cpp 不包含 quadtree 的定义。 quadtree 必须先定义。只需包含包含定义的 header。

Answer 2

在quadtree.h中定义结构，但在结构内部您已经在构造函数的内联定义中使用它（quadtree(rect2 bounds): b(b) {}），这是不允许的，因为它不是尚未完全定义。编译器无法生成构造函数的代码，因为它还不知道还会有多少数据成员。

您可以通过仅声明构造函数来避免此问题：quadtree(rect2 bounds): b(b);，然后单独（在[=结构的 13=] 添加其定义 template<...> quadtree::quadtree(rect2 bounds) {}

Answer 3

问题在于如何定义属于模板的成员函数 class。

在你的class声明中，你说quadtree是一个有3个参数的模板，但是当你去定义成员函数时，你只列出了两个。

要修复它，您只需指定模板采用这三个参数：

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

您没有在这里指定第三个参数的默认值，因为您在声明模板时已经这样做了。

作为替代方案，您可以在模板 class 定义中定义内联函数。

请记住，模板 class 定义需要 in the header file，而不是 .cpp 文件。

Answer 4

来自（相当长的）未来的我，解决方案是放弃 std::enable_ifs。我仍然不清楚为什么它们会导致问题，但是在 class 正文中用一个 static_assert 替换它们就足以解决问题。无论如何，孩子们，不要使用这个代码。太可怕了。

c ++四叉树的问题

Problems with c++ quadtree

c++

quadtree

incomplete-type