はんぶんこしよう

FCD によると、C++0x では少なくとも 1024 回の再帰的なテンプレートの実体化が保証されることになっています。
1024 回というのは、通常は十分に大きく問題のない数字なのですが、メタプログラミングな気分の時には、ちょっと少ないカナ？という気持ちに、ちょっとなります。

例えば N 個の要素を持つ配列（のような何か）を作る場合。

template <typename... seq>
struct array;

template <typename ary, typename val>
struct pushf;

template <typename... seq, typename val>
struct pushf<array<seq...>, val> {
  typedef array<val, seq...> type;
};

template <typename val, int n>
struct construct_n {
  typedef typename construct_n<val, n-1>::type tmp;
  typedef typename pushf<tmp, val>::type type;
};

template <typename val>
struct construct_n<val, 0> {
  typedef array<> type;
};

typedef
  typename construct_n<int, 1023>::type // error: template instantiation depth exceeds maximum of 1024 (use -ftemplate-depth= to increase the maximum) instantiating ‘struct construct_n<int, 8976>’
  ary;

10000 万個も作らせようとしちゃいけません。ごめんなさいですね。
こういうときは半分ずつ処理してあげればいいですね。

template <typename lhs, typename rhs>
struct append;

template <typename... lhs, typename... rhs>
struct append<array<lhs...>, array<rhs...>> {
  typedef array<lhs..., rhs...> type;
};

template <typename val, int n>
struct construct_n;

template <typename val>
struct construct_n<val, 0> {
  typedef array<> type;
};

template <typename val>
struct construct_n<val, 1> {
  typedef array<val> type;
};

template <typename val, int n>
struct construct_n<val, n> {
  static const int lhs_size = n / 2;
  static const int rhs_size = n - lhs_size;
  typedef typename construct_n<val, lhs_size>::type lhs;
  typedef typename construct_n<val, rhs_size>::type rhs;
  typedef typename append<lhs, rhs>::type type;
};

typedef
  typename construct_n<int, 1023>::type
  ary;

やったー。

基本的にはこの方針でいいのですが、基本的にインデックスアクセスが O(N) なので、なかなか厳しいのです。
とはいえ、頑張れば at(X) を O(1) にすることはできます…が、 X = 10000 とかだとちょっとやってられません。

ということで、現実的な X はどれぐらいかなっていう話と、実装の話を書く予定だったのですが、遅くなってしまったので、寝ます。
おやすみなさい。