专门针对树算法的 C++ 递归模板

Question

我正在使用递归 C++ 模板开发一种树状算法。我设法用下面的简化算法重现我的问题。该算法采用单个整数作为输入。它计算两个整数，它们是前一个整数的函数，然后递归进行：对于计算的每个整数，它使用完全相同的函数（也是深度的函数）计算另外两个整数，直到停止标准为遇见了。

我使用模板编写了以下代码。我使用这种设计选择是因为我最终想在 HLS 中实现该算法。

#define max_depth 5
#define two_to_maxdepth 32


// recursive template
template<unsigned int depth, unsigned int two_to_depth>
void split( int in[two_to_depth], int out[two_to_maxdepth], int aux[depth+1] )
{

  int next[two_to_depth*2];
  for (unsigned int ipart=0; ipart < two_to_depth; ++ipart){
    next[ipart]=ipart*in[ipart];
    next[ipart+two_to_depth]=ipart*in[ipart]+depth;
  }
  split<depth+1, two_to_depth*2>( next, out, aux);
}


// specialize
template<>
void split( int in[two_to_maxdepth], int out[two_to_maxdepth], int aux[max_depth+1])
{
  in=out;
}


int main()
{
  int in[1];
  int out[two_to_maxdepth];
  int aux[1];
  split<0,1>(in, out,aux);
}

但是，它无法编译，因为它无法推断出

depth

的值。我对此感到困惑：

depth

的值是在模板实例化中指定的。抱歉，如果问题太琐碎，但我看不出原因。

Answer 1

试试这个：

template<unsigned int depth_plus_one, unsigned int two_to_depth>
void split( int(& in)[two_to_depth], int (&out)[two_to_maxdepth], int (&aux)[depth_plus_one] )
{
  constexpr int depth=depth_plus_one-1;

这不再强制编译器反转 x+1 来推导 x，并阻止函数参数从数组到指针的衰减。

还修复终止情况。