C++中的QuadTree或Octree模板化实现

Question

我将编写一个模板化的KDTree实现，目前只能作为BarnesHut实现的Quadtree或Octree来使用。

重点在于设计，我希望将树定义的维度数量指定为模板参数，然后简单声明一些常用方法，这些方法会自动以正确的方式运行（我认为需要一些模板特化）。

我想要特化模板，以便具有2 ^ 2（四叉树）或2 ^ 3（八叉树）节点。

你们有一些设计思路吗？我想避免继承，因为这会限制我进行动态内存分配而不是静态分配。

这里N可以是2或3。

template<int N>
class NTree
{
public:
    NTree<N>( const std::vector<Mass *> &);
    ~NTree<N>()
    {
       for (int i=0; i<pow(2,N); i++)
          delete nodes[i];
    }
 private:
    void insert<N>( Mass *m );
    NTree *nodes[pow(2,N)]; // is it possible in a templatized way?
};

另一个问题是四叉树只有4个节点，但是2维，八叉树有8个节点，但是3维，即节点数为2^dimension。我能否通过模板元编程指定这个呢？我想保留数字4和8，这样循环展开器可以更快。

谢谢！

- linello

---

您错误地使用了“叶子”这个术语，正确的术语应该是“节点”。一个“叶子”是一个没有任何子节点的节点。 - Dietrich Epp

你也混淆了kd树和四叉/八叉树，它们不同（即二维树不等于四叉树）。 - KillianDS

没错，我只是想要一个n元树，它在2D中的行为类似于四叉树，在3D中的行为类似于八叉树，我正在编辑问题。 - linello

Answer 1

您可以使用 1 << N 代替 pow(2, N)。这是有效的，因为 1 << N 是编译时常量，而 pow(2, N) 不是编译时常量（尽管它将在编译时被计算）。

- Dietrich Epp

---

不错的想法！谢谢你！你觉得这种模板化实现方式可行或好吗？ - linello

不。我认为模板代码的编写和阅读会比两个单独的实现更困难：一个四叉树和一个八叉树。由于我们有专门针对一维数据的更好的数据结构，因此不太可能遇到N = 2，而每个节点大小的指数增长导致N> 3也不太可能。 - Dietrich Epp

你说得没错，但我也在使用一个针对向量和矩阵操作的模板化线性代数库（eigen），似乎只需要检查N是否等于2或3，然后相应地编写代码即可。我想将这两个实现合并以便维护。我会让你知道最新情况。 - linello

Answer 2

如果您使用支持constexpr的C++11编译器，您可以编写一个constexpr版本的pow函数，在运行时进行计算。

- Björn Pollex

---

不幸的是，我没有这样的编译器，而且C++11的一些特性对我来说仍然很模糊 :P - linello

你也可以在C++03中做到这一点。一个简单的递归模板元函数用于计算整数幂真的很容易实现。但是如果基数始终为2，像Dietrich Epp建议的那样使用位移运算会更好。 - Fiktik