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

さらに高速化・簡単化できた。

#include <iostream>

/* NullType */
class NullType;

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

/* 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;
};

/* Int */
template <int n>
struct Int
{
    typedef typename Int<n - 1>::Result TList;
    typedef Typelist< void, TList > Result;
};

template <>
struct Int<0>
{
    typedef NullType Result;
};

/* Tarai */
template <class T, int x, int y, int z>
struct Tarai1;

template <int x, int y, int z>
struct Tarai
{
    typedef typename Int<x>::Result X;
    typedef typename Int<y>::Result Y;
    typedef typename LessEq<X, Y>::Result B;
    enum { value = Tarai1<B, x, y, z>::value };
};

template <int x, int y, int z>
struct Tarai1<True, x, y, z>
{
    enum { value = y };
};

template <int x, int y, int z>
struct Tarai1<False, x, y, z>
{
    enum { xx = Tarai<x - 1, y, z>::value };
    enum { yy = Tarai<y - 1, z, x>::value };
    enum { zz = Tarai<z - 1, x, y>::value };
    enum { value = Tarai<xx, yy, zz>::value };
};

int main(int argc, char *argv[])
{
    int n = Tarai<24, 12, 1>::value;
    std::cout << n << std::endl;

    return 0;
}

• 実行結果

% time g++ tarai4.cpp

real    0m2.907s
user    0m2.776s
sys     0m0.104s

% time ./a.out
24

real    0m0.003s
user    0m0.004s
sys     0m0.000s