QuadTree or Octree templatized implementation in C++

Question

I'm going to write a templatized implementation of a KDTree, which for now should only work as Quadtree or Octree for a BarnesHut implementation.

The crucial point here is the design, I would like to specify the number of dimension where the tree is defined as template parameter and then simply declare some common methods, which automatically behave the correct way (I think some template specialization is needed then).

I would like to specialize the template in order to have 2^2 (quadtree) or 2^3 (octree) nodes.

Do someone have some design ideas? I would like to avoid inheritance because it constrains me to do dynamic memory allocation rather than static allocations.

Here N can be 2 or 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?
};

Another problem is that quadtree has 4 nodes but 2 dimension, octree has 8 nodes, but 3 dimension, i.e. number of nodes is 2^dimension. Can I specify this via template-metaprogramming? I would like to keep the number 4 and 8 so the loop unroller can be faster.

Thank you!

Answer 1

You can use 1 << N instead of pow(2, N). This works because 1 << N is a compile-time constant, whereas pow(2, N) is not a compile time constant (even though it will be evaluated at compile-time anyway).

Answer 2

If you are using a C++11 compiler that supports constexpr you could write yourself a constexpr-version of pow to do the calculation at runtime.