[C++11] コンパイル時に概ね1000要素以上の配列を初期化する

C++11という古代言語では配列をコンパイル時に初期化することにも大変な苦痛が伴った。
以下は0〜9999の数値を入力として受け取り、その2乗の値をコンパイル時に構築したルックアップテーブルから引いてきて出力するサンプルである。

サンプルコード

#include <iostream>
#include <array>

template <int... V> struct sequence {
  template <typename T> using join = typename T::template prepend<V...>;
  template <int... U> using prepend = sequence<U..., V...>;
  static constexpr std::array<int, sizeof...(V)> value = {V...};
};
template <int... V> constexpr std::array<int, sizeof...(V)> sequence<V...>::value;

template <int I, int N> struct pow_range {
  using to_sequence = typename pow_range<I, N / 2>::to_sequence::template join<typename pow_range<I + N / 2, N - N / 2>::to_sequence>;
};
template <int I> struct pow_range<I, 1> {
  using to_sequence = sequence<I * I>;
};

int main() {
  int x;
  std::cin >> x;
  std::cout << pow_range<0, 10000>::to_sequence::value[x] << std::endl;
  return 0;
}

ポイント

• テンプレートには再帰限界（C++11では推奨値1024）がある。概ね1000要素以上の大きな配列をコンパイル時に構築する場合は、再帰回数がlogNのオーダーになるよう、二分探索的にテンプレートを展開していく必要がある。
• 外出しでsequence<V...>::valueの行が再度無意味に書かれているように見えるが、これが無いとリンカでエラーになってしまう。以下は私の理解。
  • value[(実行時に決まる値)]をするためにはvalueが定義されている必要がある。
  • 最初のvalueはただの宣言。
  • 次の外出しのvalueが定義になっている。