テンプレートでたらいまわし

できたような気もするけどこれ本当に動いてるのか?

#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 TList>
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 };
};

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

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

template <class X, class Y, class Z, class T>
struct Tarai< Typelist< Typelist< NullType, T >,
                        TYPELIST_3(X, Y, Z) > >
{
    typedef Y Result;
    enum { value = Length<Y>::value };
};

template <class X1, class X2,
          class Y1, class Y2,
          class Z1, class Z2,
          class T1, class T2>
struct Tarai< Typelist< Typelist< Typelist<T1, T2>, NullType >,
                        Typelist< Typelist<X1, X2>,
                                  Typelist< Typelist<Y1, Y2>,
                                            Typelist< Typelist<Z1, Z2>,
                                                      NullType > > > > >
{
    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 };
};

template <class X, class Y, class Z, class T1, class T2, class U1, class U2>
struct Tarai< Typelist< Typelist< Typelist<T1, T2>, Typelist<U1, U2> >,
                        TYPELIST_3(X, Y, Z) > >
{
    typedef Tarai< Typelist< Typelist<T2, U2>, TYPELIST_3(X, Y, Z) > > T;
    typedef typename T::Result Result;
    enum { value = T::value };
};

typedef NullType T0;
typedef Typelist<int, T0> T1;
typedef Typelist<int, T1> T2;
typedef Typelist<int, T2> T3;
typedef Typelist<int, T3> T4;
typedef Typelist<int, T4> T5;
typedef Typelist<int, T5> T6;
typedef Typelist<int, T6> T7;
typedef Typelist<int, T7> T8;
typedef Typelist<int, T8> T9;
typedef Typelist<int, T9> T10;
typedef Typelist<int, T10> T11;
typedef Typelist<int, T11> T12;

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

    return 0;
}
  • 実行結果
% time g++ tarai.cpp

real    0m2.432s
user    0m2.348s
sys     0m0.064s

% time ./a.out
12

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

比較のために普通にCで書いたものは、

#include <stdio.h>

int tarai(int x, int y, int z)
{
    if (x <= y)
        return y;
    else
        return tarai(tarai(x - 1, y, z),
                     tarai(y - 1, z, x),
                     tarai(z - 1, x, y));
}

int main(int argc, char *argv[])
{
    if (argc < 3) {
        printf("Usage: %s x y z\n", argv[0]);
    } else {
        int x = atoi(argv[1]);
        int y = atoi(argv[2]);
        int z = atoi(argv[3]);

        printf("tarai(%d, %d, %d) = %d\n", x, y, z, tarai(x, y, z));
    }

    return 0;
}
% time gcc tarai.c

real    0m0.054s
user    0m0.028s
sys     0m0.024s

% time ./a.out 12 6 1
tarai(12, 6, 1) = 12

real    0m0.015s
user    0m0.012s
sys     0m0.000s

となって、実行時間はテンプレート版の方がかろうじて早い(コンパイル時に計算を済ませているんだから当たり前)。本当は数字が大きい方が差が出やすいんだけど、テンプレートの方はあまり数字を大きくできないので益々使えない。

参考:前回までのあらすじ

改めて眺めてみると、およそ生産的でないことばっかりやってるな。