是否可以使用模板元编程创建和初始化值数组？

Question

我希望能够在编译时使用模板元编程创建一个计算值数组(为了简单起见,我希望每个值都是它的索引的平方).这可能吗？如何初始化数组中的每个位置？

(是的,有更简单的方法可以在不使用模板元编程的情况下执行此操作,只是想知道是否可以使用数组执行此操作.)

Answer 1

它在元编程中称为静态表生成.

#include <iostream>

const int ARRAY_SIZE = 5;

template <int N, int I=N-1>
class Table : public Table<N, I-1>
{
public:
    static const int dummy;
};

template <int N>
class Table<N, 0>
{
public:
    static const int dummy;
    static int array[N];
};

template <int N, int I>
const int Table<N, I>::dummy = Table<N, 0>::array[I] = I*I + 0*Table<N, I-1>::dummy;

template <int N>
int Table<N, 0>::array[N];

template class Table<ARRAY_SIZE>;

int main(int, char**)
{
    const int *compilerFilledArray = Table<ARRAY_SIZE>::array;
    for (int i=0; i < ARRAY_SIZE; ++i)
        std::cout<<compilerFilledArray[i]<<std::endl;
}

我们使用显式模板实例化和虚拟变量来强制编译器用索引方块填充数组.I*I之后的部分是递归分配每个数组元素所需的技巧.

Answer 2

虽然你不能像这样初始化一个数组,你可以通过创建一个递归struct来做几乎相同的事情:

template <int I>
struct squared {
    squared<I - 1> rest;
    int x;
    squared() : x((I - 1) * (I - 1)) {}
};

template <>
struct squared<1> {
    int x;
    squared() : x(0) {}
};

然后在您的代码中,您可以声明:

squared<5> s;

并且编译器确实会创建一个struct包含5 ints:0,1,4,16,25.

几个笔记:

1. 我对C++标准的解释是,它不能保证它的struct布局与数组相同.虽然它是POD类型,但POD类型保证在内存(1.8/5)中"连续"布局,第一个成员位于偏移0(9.2/17),后来成员位于更高地址(9.2/12),并且数组也是"连续"布局的(8.3.4/1),标准并没有说数组与这样的s 是布局兼容struct的.但是,任何理智的编译器都会以相同的方式放置这些对象. [编辑:正如ildjarn指出的那样,用户定义的构造函数的存在实际上使这个类非聚合,因此非POD.同样,任何理智的编译器都不会允许它影响它的布局.]
2. C++要求即使空struct为至少1个字节.如果没有,我们可以使用稍微更清晰的公式,其中递归的基本情况是,I == 0并且我们没有从I计算中减去1 .

如果我们可以将它struct放在一个union具有适当大小的数组中,以便于访问成员,那将是很好的.不幸的是,union如果该对象具有非平凡的构造函数,C++会禁止您在对象中包含对象.因此,最简单的方法i是使用一个好的老式演员:

squared<5> s;
cout << "3 squared is " << reinterpret_cast<int*>(&s)[3] << endl;

如果你愿意,你可以编写一个重载的operator[]()函数模板来使它更漂亮.

Answer 3

在c ++ 0x中可以使用可变参数模板.以下是如何创建二项式系数表的示例:

//typedefs used
typedef short int              index_t;
typedef unsigned long long int int_t;

//standard recursive template for coefficient values, used as generator
template <index_t n, index_t k> struct coeff {static int_t const value = coeff<n-1, k-1>::value + coeff<n-1, k>::value;};
template <index_t n>            struct coeff<n, 0> {static int_t const value = 1;};
template <index_t n>            struct coeff<n, n> {static int_t const value = 1;};

//helper template, just converts its variadic arguments to array initializer list
template<int_t... values> struct int_ary {static int_t const value[sizeof...(values)];};
template<int_t... values> int_t const int_ary<values...>::value[] = {values...};

//decrement k, pile up variadic argument list using generator
template<index_t n, index_t k, int_t... values> struct rec: rec<n, k-1, coeff<n, k-1>::value, values...> {};
//when done (k == 0), derive from int_ary
template<index_t n,            int_t... values> struct rec<n, 0, values...>: int_ary<values...> {};

//initialise recursion
template<index_t n> struct binomial: rec<n, n+1> {};

要访问元素,请使用二项式<N> :: value [k]等语法,其中N是编译时常量,k是从0到N(包括0和N)的索引.

Answer 4

我真的很喜欢 j_random_hackers 的答案——它既漂亮又简短。使用 C++11，可以将其扩展为

template <int I>
struct squared {
  squared<I - 1> rest;
  static const int x = I * I ;
  constexpr int operator[](int const &i) const { return (i == I ?  x : rest[i]); }
  constexpr int size() const { return I; }
};

template <>
struct squared<0> {
  static const int x = 0;
  constexpr int operator[](int const &i) const { return x; }
  constexpr int size() const { return 1; }
};

此代码在运行时都可用

  squared<10> s;

  for(int i =0; i < s.size() ; ++i) {
    std::cout << "s[" << i << "]" << " = " << s[i] << std::endl;
  }

以及编译时间

struct Foo {
  static const squared<10> SquareIt;
  enum { 
    X = 3,
    Y = SquareIt[ X ]
  };
};

int main() {
  std::cout << "Foo::Y = " << Foo::Y << std::endl;
}

并提供了一个很好的和可读的语法。