c++ - C++ 中的四叉树或八叉树模板化实现

Question

我将编写一个 KDTree 的模板化实现，它目前只能作为 BarnesHut 实现的四叉树或八叉树。

这里的关键点是设计，我想指定树定义为模板参数的维数，然后简单地声明一些通用方法，这些方法会自动以正确的方式运行(我认为需要一些模板专门化然后)。

我想专门化模板以获得 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，这样循环展开器可以更快。

谢谢!

Answer 1

您可以使用 1 << N而不是 pow(2, N) .这是有效的，因为 1 << N是编译时常量，而 pow(2, N)不是编译时常量(即使它无论如何都会在编译时求值)。