6

我将编写一个 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，以便循环展开器可以更快。

谢谢！

4

2 回答 2

8

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

于 2012-05-15T11:17:05.770 回答
2

如果您使用的是支持的 C++11 编译器，constexpr您可以自己编写一个constexpr-versionpow来在运行时进行计算。

于 2012-05-15T11:14:52.590 回答