テンプレートでフィボナッチ数列
『Modern C++ Design』 (ISBN:4894714353)を読んでC++のテンプレートが面白かったのでちょっと遊んでみた。
#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) > /* Fib */ template <class TList> struct Fib; template <> struct Fib< NullType > { enum { value = 0 }; }; template <class X> struct Fib< TYPELIST_1(X) > { enum { value = 1 }; }; template < class X, class Y, class Z > struct Fib< Typelist< X, Typelist<Y, Z> > > { enum { value = Fib< Typelist<Y, Z> >::value + Fib<Z>::value }; }; int main(int argc, char *argv[]) { int n1 = Fib< TYPELIST_1(int) >::value; std::cout << "Fibonacci(1) = " << n1 << std::endl; int n2 = Fib< TYPELIST_2(int, int) >::value; std::cout << "Fibonacci(2) = " << n2 << std::endl; int n3 = Fib< TYPELIST_3(int, int, int) >::value; std::cout << "Fibonacci(3) = " << n3 << std::endl; int n4 = Fib< TYPELIST_4(int, int, int, int) >::value; std::cout << "Fibonacci(4) = " << n4 << std::endl; int n5 = Fib< TYPELIST_5(int, int, int, int, int) >::value; std::cout << "Fibonacci(5) = " << n5 << std::endl; int n6 = Fib< TYPELIST_6(int, int, int, int, int, int) >::value; std::cout << "Fibonacci(6) = " << n6 << std::endl; int n7 = Fib< TYPELIST_7(int, int, int, int, int, int, int) >::value; std::cout << "Fibonacci(7) = " << n7 << std::endl; int n8 = Fib< TYPELIST_8(int, int, int, int, int, int, int, int) >::value; std::cout << "Fibonacci(8) = " << n8 << std::endl; int n9 = Fib< TYPELIST_9(int, int, int, int, int, int, int, int, int) >::value; std::cout << "Fibonacci(9) = " << n9 << std::endl; return 0; }
- 実行結果
% ./a.out Fibonacci(1) = 1 Fibonacci(2) = 1 Fibonacci(3) = 2 Fibonacci(4) = 3 Fibonacci(5) = 5 Fibonacci(6) = 8 Fibonacci(7) = 13 Fibonacci(8) = 21 Fibonacci(9) = 34
ポイントは、全ての計算がコンパイル時に行われるということ。この性質はLispのマクロと同じ。特に、型推論が一種のパターンマッチングになっている点はSchemeの「健全な」マクロとかなり近いものを感じる。
…で、本当はテンプレートでたらいまわしてみたかったんだけど、さすがにこれまでテンプレートを使ったことがなくていきなりは無理だった。