编译时间循环

Question

我想知道是否有可能有一些编译时循环.
例如,我有以下模板类:

template<class C, int T=10, int B=10>
class CountSketch
{
public:
    CountSketch()
    {   
         hashfuncs[0] = &CountSketch<C>::hash<0>;
         hashfuncs[1] = &CountSketch<C>::hash<1>;
         // ... for all i until i==T which is known at compile time
    };
private:
    template<int offset>
    size_t hash(C &c)
    {
        return (reinterpret_cast<int>(&c)+offset)%B;
    }
    size_t (CountSketch::*hashfuncs[T])(C &c);
};

我想知道我是否可以使用循环来循环初始化T哈希函数.循环的边界在编译时是已知的,因此,原则上,我没有看到任何无法完成的原因(特别是因为它可以在我手动展开循环时起作用).

当然,在这个具体的例子中,我可以用2个参数创建一个哈希函数(虽然我猜它的效率会低一些).因此,我对解决这个特定问题不感兴趣,而是知道类似情况下是否存在"编译时间循环".

谢谢!

Answer 1

不,这不是直接可能的.模板元编程是一种纯函数式语言.通过它定义的每个值或类型都是不可变的.循环固有地需要可变变量(重复测试某些条件直到X发生,然后退出循环).

相反,您通常会依赖递归.(每次使用不同的模板参数实例化此模板,直到达到某个终止条件).

但是,这可以解决所有与循环相同的问题.

编辑:这是一个快速示例,在编译时使用递归计算N的阶乘:

template <int N>
struct fac {
  enum { value = N * fac<N-1>::value };
};

template <>
struct fac<0> {
  enum { value = 1 };
};

int main() {
  assert(fac<4>::value == 24);
}

C++中的模板元编程是一种图灵完备语言,因此只要您没有遇到各种内部编译器限制,您就可以解决它的任何问题.

但是,出于实际目的,可能值得研究像Boost.MPL这样的库,它包含大量的数据结构和算法,可以简化许多元编程任务.

Answer 2

是.可能使用编译时递归.

我正在尝试使用您的代码,但由于它不可编译,因此这是一个经过修改和编译的例子:

template<class C, int T=10>
class CountSketch
{
  template<int N>
  void Init ()
  {
    Init<N-1>();
    hashfuncs[N] = &CountSketch<C>::template hash<N>;
    cout<<"Initializing "<<N<<"th element\n";
  }

public:
    CountSketch()
    {
      Init<T>();
    }
private:
   template<int offset>
   size_t hash(C &c)
   {
     return 0;
   }
   size_t (CountSketch::*hashfuncs[T])(C &c);
};

template<>
template<>
void CountSketch<int,10>::Init<0> ()
{
  hashfuncs[0] = &CountSketch<int,10>::hash<0>;
  cout<<"Initializing "<<0<<"th element\n";
}

演示.此解决方案的唯一约束是您必须提供最终的专用版本,CountSketch<int,10>::Init<0>无论何种类型和大小.

Answer 3

您需要boost::mpl::for_each和boost::mpl::range_c 的组合。

注意：这将产生运行时代码，而这正是您实际需要的。因为operator&在编译时无法知道结果。至少我不知道。

这样做的实际困难是构建一个基于 int 参数（在我们的例子中为 mpl::int_ ）的模板结构，并在operator()被调用时进行赋值，我们还需要一个函子来实际捕获 this 指针。

这比我预期的要复杂一些，但很有趣。

#include <boost/mpl/range_c.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/transform.hpp>
#include <boost/mpl/copy.hpp>

// aforementioned struct
template<class C, class I>
struct assign_hash;

// this actually evaluates the functor and captures the this pointer
// T is the argument for the functor U
template<typename T>
struct my_apply {
  T* t;
  template<typename U>
  void operator()(U u) {
    u(t);
  }
};

template<class C, int T=10, int B=10>
class CountSketch
{
public:
  CountSketch()
    {   
      using namespace boost::mpl;

      // we need to do this because range_c is not an ExtensibleSequence
      typedef typename copy< range_c<int, 0, T>,
                             back_inserter< vector<> > >::type r;
      // fiddle together a vector of the correct types
      typedef typename transform<r, typename lambda< assign_hash<C, _1 > >::type >
        ::type assignees;

      // now we need to unfold the type list into a run-time construct
      // capture this
      my_apply< CountSketch<C, T, B> > apply = { this };
      // this is a compile-time loop which actually does something at run-time
      for_each<assignees>(apply);
    };

  // no way around
  template<typename TT, typename I>
  friend struct assign_hash;

private:
  template<int offset>
  size_t hash(C& c)
    {
      return c;
      // return (reinterpret_cast<int>(&c)+offset)%B;
    }
  size_t (CountSketch::*hashfuncs[T])(C &c);
};

// mpl uses int_ so we don't use a non-type template parameter 
// but get a compile time value through the value member
template<class C, class I>
struct assign_hash {
  template<typename T>
  void operator()(T* t) {
    t->hashfuncs[I::value] = &CountSketch<C>::template hash<I::value>;
  }
};

int main() 
{
  CountSketch<int> a;
}