メタプログラミングでFib関数をメモ化するとどうなるのか

メモ化されたC++テンプレートメタプログラミングなFib関数を考えてみた。
boost.mpl.mapをメモ帳代わりにして、計算していく。

#include <boost/mpl/if.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/map.hpp>
#include <boost/mpl/insert.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/int.hpp>
#include <iostream>

using namespace boost::mpl; 

template <typename m, int n>
struct fib_;

template <typename m, int n, bool cond>
struct fib__ {
	typedef struct fib_<m, n - 2>::type r1;
	typedef struct fib_<typename r1::first, n - 1>::type r2;
	typedef int_<r1::second::type::value + r2::second::type::value> r;

	typedef boost::mpl::pair<
		typename insert<m, boost::mpl::pair< int_<n>, r > >::type,
		r
	> type;
};

template <typename m, int n>
struct fib__<m, n, true> {
	typedef boost::mpl::pair<
		m,
		typename at< m, int_<n> >::type
	> type;
};

template <typename m, int n>
struct fib_ {
	typedef typename fib__<
		m, n,
		has_key< m, int_<n> >::type::value
	>::type type;
};


template <typename m>
struct fib_<m, 1> {
	typedef boost::mpl::pair<
		typename insert<m, boost::mpl::pair< int_<1>, int_<1> > >::type,
		int_<1>
	> type;		
};

template <typename m>
struct fib_<m, 2> {
	typedef boost::mpl::pair<
		typename insert<m, boost::mpl::pair< int_<2>, int_<1> > >::type,
		int_<1>
	> type;		
};

template <int n>
struct fib {
	enum {
		value = fib_< map0<>, n >::type::second::value
	};
};

int main() {
	std::cout << fib<50>::value << std::endl;
	return 0;
}

これでいけるかと思ったら、とんでもなく時間が掛かった挙げ句、コンパイラご臨終と相成った。流石に実装が愚直すぎたか……

$ g++ fib.cpp

cc1plus: out of memory allocating 1048576 bytes after a total of 15007744 bytes