テンプレートでたらいまわし（３回目）

こうするとだいぶ速くなった。

#include <iostream>

template <class T, class U>
struct Typelist
{
    typedef T Car;
    typedef U Cdr;
};

class NullType;

#define TYPELIST_1(T1) \
    Typelist<T1, NullType>

#define TYPELIST_2(T1, T2) \
    Typelist<T1, TYPELIST_1(T2) >

#define TYPELIST_3(T1, T2, T3) \
    Typelist<T1, TYPELIST_2(T2, T3) >

#define TYPELIST_4(T1, T2, T3, T4) \
    Typelist<T1, TYPELIST_3(T2, T3, T4) >

#define TYPELIST_5(T1, T2, T3, T4, T5) \
    Typelist<T1, TYPELIST_4(T2, T3, T4, T5) >

#define TYPELIST_6(T1, T2, T3, T4, T5, T6) \
    Typelist<T1, TYPELIST_5(T2, T3, T4, T5, T6) >

#define TYPELIST_7(T1, T2, T3, T4, T5, T6, T7) \
    Typelist<T1, TYPELIST_6(T2, T3, T4, T5, T6, T7) >

#define TYPELIST_8(T1, T2, T3, T4, T5, T6, T7, T8) \
    Typelist<T1, TYPELIST_7(T2, T3, T4, T5, T6, T7, T8) >

#define TYPELIST_9(T1, T2, T3, T4, T5, T6, T7, T8, T9) \
    Typelist<T1, TYPELIST_8(T2, T3, T4, T5, T6, T7, T8, T9) >

#define TYPELIST_10(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10) \
    Typelist<T1, TYPELIST_9(T2, T3, T4, T5, T6, T7, T8, T9, T10) >

/* Length */
template <class T>
struct Length;

template <>
struct Length<NullType>
{
    enum { value = 0 };
};

template <class T, class U>
struct Length< Typelist<T, U> >
{
    enum { value = 1 + Length<U>::value };
};

/* True */
class True;

/* False */
class False;

/* LessEq */
template <class T, class U>
struct LessEq;

template <>
struct LessEq< NullType, NullType >
{
    typedef True Result;
};

template <class U1, class U2>
struct LessEq< NullType, Typelist<U1, U2> >
{
    typedef True Result;
};

template <class T1, class T2>
struct LessEq< Typelist<T1, T2>, NullType >
{
    typedef False Result;
};

template <class T1, class T2, class U1, class U2>
struct LessEq< Typelist<T1, T2>, Typelist<U1, U2> >
{
    typedef typename LessEq<T2, U2>::Result Result;
};

/* Tarai */
template <class TList>
struct Tarai;

template <class B, class X, class Y, class Z>
struct Tarai1;

template <class X, class Y, class Z>
struct Tarai< TYPELIST_3(X, Y, Z) >
{
    typedef typename LessEq< X, Y>::Result B;
    typedef Tarai1< B, X, Y, Z > T;
    typedef typename T::Result Result;
    enum { value = T::value };
};

template <class X, class Y, class Z>
struct Tarai1< True, X, Y, Z >
{
    typedef Y Result;
    enum { value = Length<Y>::value };
};

template <class X1, class X2,
          class Y1, class Y2,
          class Z1, class Z2>
struct Tarai1< False, Typelist<X1, X2>, Typelist<Y1, Y2>, Typelist<Z1, Z2> >
{
    typedef Typelist<X1, X2> X;
    typedef Typelist<Y1, Y2> Y;
    typedef Typelist<Z1, Z2> Z;

    typedef typename Tarai< TYPELIST_3(X2, Y, Z) >::Result XX;
    typedef typename Tarai< TYPELIST_3(Y2, Z, X) >::Result YY;
    typedef typename Tarai< TYPELIST_3(Z2, X, Y) >::Result ZZ;

    typedef Tarai< TYPELIST_3(XX, YY, ZZ) > T;
    typedef typename T::Result Result;
    enum { value = T::value };
};

typedef NullType T0;

typedef Typelist<void, T0> T1;
typedef Typelist<void, T1> T2;
typedef Typelist<void, T2> T3;
typedef Typelist<void, T3> T4;
typedef Typelist<void, T4> T5;
typedef Typelist<void, T5> T6;
typedef Typelist<void, T6> T7;
typedef Typelist<void, T7> T8;
typedef Typelist<void, T8> T9;
typedef Typelist<void, T9> T10;

typedef Typelist<void, T10> T11;
typedef Typelist<void, T11> T12;
typedef Typelist<void, T12> T13;
typedef Typelist<void, T13> T14;
typedef Typelist<void, T14> T15;
typedef Typelist<void, T15> T16;
typedef Typelist<void, T16> T17;
typedef Typelist<void, T17> T18;
typedef Typelist<void, T18> T19;
typedef Typelist<void, T19> T20;

typedef Typelist<void, T20> T21;
typedef Typelist<void, T21> T22;
typedef Typelist<void, T22> T23;
typedef Typelist<void, T23> T24;
typedef Typelist<void, T24> T25;
typedef Typelist<void, T25> T26;
typedef Typelist<void, T26> T27;
typedef Typelist<void, T27> T28;
typedef Typelist<void, T28> T29;
typedef Typelist<void, T29> T30;

typedef Typelist<void, T30> T31;
typedef Typelist<void, T31> T32;
typedef Typelist<void, T32> T33;
typedef Typelist<void, T33> T34;
typedef Typelist<void, T34> T35;
typedef Typelist<void, T35> T36;
typedef Typelist<void, T36> T37;
typedef Typelist<void, T37> T38;
typedef Typelist<void, T38> T39;
typedef Typelist<void, T39> T40;

typedef Typelist<void, T40> T41;
typedef Typelist<void, T41> T42;
typedef Typelist<void, T42> T43;
typedef Typelist<void, T43> T44;
typedef Typelist<void, T44> T45;
typedef Typelist<void, T45> T46;
typedef Typelist<void, T46> T47;
typedef Typelist<void, T47> T48;
typedef Typelist<void, T48> T49;
typedef Typelist<void, T49> T50;

int main(int argc, char *argv[])
{
    int n = Tarai< TYPELIST_3(T24, T12, T1) >::value;
    std::cout << n << std::endl;

    return 0;
}

% time g++ tarai3.cpp

real    0m9.604s
user    0m9.449s
sys     0m0.108s

% time ./a.out
24

real    0m0.002s
user    0m0.000s
sys     0m0.000s

どうやらインスタンス化される型の数が多くなるにしたがって時間がかかるみたいだったので、x<=yを判定している部分を独立させたら結果は歴然（それでもtarai(48,24,1）のコンパイルには10分かかった）。
そろそろテンプレートの勘が掴めてきたので、次は遅延評価にチャレンジしたい。