可変引数テンプレートでfizzbuzz

やっぱりBoost.MPLのstringを使う以外に手はなさそうだ….


C++0xなら…というわけで可変引数テンプレートでfizzbuzzしてみました。
「普通(?)に boost::mpl::string でいいじゃん」という気がしますが、15くらいまでしか無理らしいので。

mpl::stringの制限のため、1〜15のみ計算しています。

っていうかまあ普通に可変引数テンプレートの練習用です。といっても型じゃなくてただの数値列だけど。


書いたコードはgist(または本エントリの末尾)です。


vtstring (Variadic Template Stringのつもり) とかいう文字列を扱うテンプレートを作って使ってます。


コードのmainにもありますが、Hello worldだったら

// Hello world
typedef vtstring::vtstring<'H','e','l','l','o',','> str;
typedef vtstring::vtstring<'W','o','r','l','d','!'> str2;
typedef vtstring::join<str, str2>::result ret;
cout << ret::c_str() << endl;
// => Hello,World!

とかいう感じで書きます。joinは複数のvtstringを結合します。
c_str はconst static char[] な定数にしようと思ったらエラーになったので、staticメソッドになってます。(この辺は初期化リストがまだサポートされていない関係? よく分かってません(汗))


fizzbuzzするためには数値を文字列(vtstring)に変換する必要があるので、vtstring::from_int というテンプレートも用意しています。特殊化のためにマクロ使ってるのが強引な感じ。

// int => vtstring
cout << vtstring::from_int<100>::result::c_str() << endl;
// => 100


この後のソースをビルドすると、以下のように答えが定数として埋め込まれたバイナリが出来上がります。

% readelf -x -a .rodata
...
Hex dump of section '.rodata':
  0x00400a00 01000200 006c656e 6774683a 20002d2d .....length: .--
  0x00400a10 2d004865 6c6c6f2c 576f726c 64210031 -.Hello,World!.1
  0x00400a20 30300000 00000000 00000000 00000000 00..............
  0x00400a30 00000000 00000000 00000000 00000000 ................
  0x00400a40 310a320a 46697a7a 0a340a42 757a7a0a 1.2.Fizz.4.Buzz.
  0x00400a50 46697a7a 0a370a38 0a46697a 7a0a4275 Fizz.7.8.Fizz.Bu
  0x00400a60 7a7a0a31 310a4669 7a7a0a31 330a3134 zz.11.Fizz.13.14
  0x00400a70 0a46697a 7a42757a 7a0a3136 0a31370a .FizzBuzz.16.17.
  0x00400a80 46697a7a 0a31390a 42757a7a 0a46697a Fizz.19.Buzz.Fiz
  0x00400a90 7a0a3232 0a32330a 46697a7a 0a42757a z.22.23.Fizz.Buz
  0x00400aa0 7a0a3236 0a46697a 7a0a3238 0a32390a z.26.Fizz.28.29.
  0x00400ab0 46697a7a 42757a7a 0a33310a 33320a46 FizzBuzz.31.32.F
  0x00400ac0 697a7a0a 33340a42 757a7a0a 46697a7a izz.34.Buzz.Fizz
  0x00400ad0 0a33370a 33380a46 697a7a0a 42757a7a .37.38.Fizz.Buzz
  0x00400ae0 0a34310a 46697a7a 0a34330a 34340a46 .41.Fizz.43.44.F
  0x00400af0 697a7a42 757a7a0a 34360a34 370a4669 izzBuzz.46.47.Fi
  0x00400b00 7a7a0a34 390a4275 7a7a0a46 697a7a0a zz.49.Buzz.Fizz.
  0x00400b10 35320a35 330a4669 7a7a0a42 757a7a0a 52.53.Fizz.Buzz.
  0x00400b20 35360a46 697a7a0a 35380a35 390a4669 56.Fizz.58.59.Fi
  0x00400b30 7a7a4275 7a7a0a36 310a3632 0a46697a zzBuzz.61.62.Fiz
  0x00400b40 7a0a3634 0a42757a 7a0a4669 7a7a0a36 z.64.Buzz.Fizz.6
  0x00400b50 370a3638 0a46697a 7a0a4275 7a7a0a37 7.68.Fizz.Buzz.7
  0x00400b60 310a4669 7a7a0a37 330a3734 0a46697a 1.Fizz.73.74.Fiz
  0x00400b70 7a42757a 7a0a3736 0a37370a 46697a7a zBuzz.76.77.Fizz
  0x00400b80 0a37390a 42757a7a 0a46697a 7a0a3832 .79.Buzz.Fizz.82
  0x00400b90 0a38330a 46697a7a 0a42757a 7a0a3836 .83.Fizz.Buzz.86
  0x00400ba0 0a46697a 7a0a3838 0a38390a 46697a7a .Fizz.88.89.Fizz
  0x00400bb0 42757a7a 0a39310a 39320a46 697a7a0a Buzz.91.92.Fizz.
  0x00400bc0 39340a42 757a7a0a 46697a7a 0a39370a 94.Buzz.Fizz.97.
  0x00400bd0 39380a46 697a7a0a 42757a7a 0a00     98.Fizz.Buzz..
...

実行するとその文字列が単に出力される感じ。


以下fizzbuzzのソース(gistはこちら)。なおg++-4.6のsnapshot 20100701で

g++ --std=c++0x test.cpp

という感じでコンパイルして確認しています。

#include <iostream>
using namespace std;

namespace vtstring {

// 文字列を表す可変引数テンプレート
template <char... a> struct vtstring;
template <char a, char... b>
struct vtstring<a, b...>
{
	static const int size = 1 + vtstring<b...>::size; // サイズ
	
	// C文字列を返す関数 (定数はダメ。初期化リスト未サポートのため?)
	static const char* c_str() {
		static const char ret[] = {a,b...,0}; return ret;
	}
};
// NULL
template <>
struct vtstring<>
{
	static const int size = 0;
	static const char* c_str() { return ""; }
};

// 文字列の再帰的結合
template <class A, class... B>
struct join;
// 再帰
template <class A, class B, class... C>
struct join<A, B, C...>
{
	typedef typename join<typename join<A,B>::result,
			      C...>::result result;
};
// 結合
template <char... a, char... b>
struct join<vtstring<a...>, vtstring<b...>>
{
	typedef vtstring<a..., b...> result;
};

// 数値→文字列変換
template <int n>
struct from_int
{ // 10以上の場合
	typedef typename from_int<n/10>::result tens;
	typedef typename from_int<n%10>::result ones;
	typedef typename join<tens, ones>::result result;
};
// 10未満の場合
#define DEF_FROM_INT(N) \
template <> struct from_int<N> { typedef vtstring<N+'0'> result; }
DEF_FROM_INT(0);
DEF_FROM_INT(1);
DEF_FROM_INT(2);
DEF_FROM_INT(3);
DEF_FROM_INT(4);
DEF_FROM_INT(5);
DEF_FROM_INT(6);
DEF_FROM_INT(7);
DEF_FROM_INT(8);
DEF_FROM_INT(9);

};


// FizzBuzz
template <int i>
struct fizzbuzz {
	template <int n, int mod3, int mod5>
	struct fizzbuzz_ {
		typedef typename vtstring::from_int<n>::result result;
	};
	template <int n, int mod5>
	struct fizzbuzz_<n, 0, mod5> {
		typedef vtstring::vtstring<'F','i','z','z'> result;
	};
	template <int n, int mod3>
	struct fizzbuzz_<n, mod3, 0> {
		typedef vtstring::vtstring<'B','u','z','z'> result;
	};
	template <int n>
	struct fizzbuzz_<n, 0, 0> {
		typedef typename vtstring::vtstring<'F','i','z','z',
						    'B','u','z','z'> result;
	};
	
	typedef typename vtstring::join<
				typename fizzbuzz_<i, i%3, i%5>::result,
				vtstring::vtstring<'\n'>
			>::result result;
};


// i〜maxをループしてTを適用(map)し, Mでfold
template <int i, int max, template<int n> class T,
	  template<class... A> class M>
struct loopN
{
	typedef typename M<
			typename T<i>::result,
			typename loopN<i+1, max, T, M>::result
		>::result result;
};
// 最後のループ
template <int max, template<int n> class T,
	  template<class... A> class M>
struct loopN<max, max, T, M>
{
	typedef typename T<max>::result result;
};


int main()
{
	// Hello World
	typedef vtstring::vtstring<'H','e','l','l','o',','> str;
	typedef vtstring::vtstring<'W','o','r','l','d','!'> str2;
	typedef vtstring::join<str, str2>::result ret;
	cout << ret::c_str() << endl;
	
	// length of vtstring
	cout << "length: " << ret::size << endl;
	
	// Null string
	typedef vtstring::vtstring<> null;
	cout << null::c_str();
	
	// int => vtstring
	cout << vtstring::from_int<100>::result::c_str() << endl;
	
	cout << "---" << endl;
	
	// fizzbuzz
	cout << loopN<1,100,fizzbuzz,vtstring::join>::result::c_str();
	
	return 0;
}

ちなみにfizzbuzzの文字列の型情報は異様なことになってます。
型に文字列全部はいってるもんなあ…

% nm
0000000000601030 d _DYNAMIC
00000000006011f8 d _GLOBAL_OFFSET_TABLE_
0000000000400960 t _GLOBAL__I_main
0000000000400a80 R _IO_stdin_used
                 w _Jv_RegisterClasses
                 U _ZNSolsEi@@GLIBCXX_3.4
                 U _ZNSt8ios_base4InitC1Ev@@GLIBCXX_3.4
                 U _ZNSt8ios_base4InitD1Ev@@GLIBCXX_3.4
                 U _ZNSt9basic_iosIcSt11char_traitsIcEE5clearESt12_Ios_Iostate@@GLIBCXX_3.4
                 U _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l@@GLIBCXX_3.4.9
0000000000601280 B _ZSt4cout@@GLIBCXX_3.4
                 U _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@@GLIBCXX_3.4
00000000006013a0 b _ZStL8__ioinit
0000000000400890 t _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc.constprop.4
0000000000400ac0 u _ZZN8vtstring8vtstringIILc49ELc10ELc50ELc10ELc70ELc105ELc122ELc122ELc10ELc52ELc10ELc66ELc117ELc122ELc122ELc10ELc70ELc105ELc122ELc122ELc10ELc55ELc10ELc56ELc10ELc70ELc105ELc122ELc122ELc10ELc66ELc117ELc122ELc122ELc10ELc49ELc49ELc10ELc70ELc105ELc122ELc122ELc10ELc49ELc51ELc10ELc49ELc52ELc10ELc70ELc105ELc122ELc122ELc66ELc117ELc122ELc122ELc10ELc49ELc54ELc10ELc49ELc55ELc10ELc70ELc105ELc122ELc122ELc10ELc49ELc57ELc10ELc66ELc117ELc122ELc122ELc10ELc70ELc105ELc122ELc122ELc10ELc50ELc50ELc10ELc50ELc51ELc10ELc70ELc105ELc122ELc122ELc10ELc66ELc117ELc122ELc122ELc10ELc50ELc54ELc10ELc70ELc105ELc122ELc122ELc10ELc50ELc56ELc10ELc50ELc57ELc10ELc70ELc105ELc122ELc122ELc66ELc117ELc122ELc122ELc10ELc51ELc49ELc10ELc51ELc50ELc10ELc70ELc105ELc122ELc122ELc10ELc51ELc52ELc10ELc66ELc117ELc122ELc122ELc10ELc70ELc105ELc122ELc122ELc10ELc51ELc55ELc10ELc51ELc56ELc10ELc70ELc105ELc122ELc122ELc10ELc66ELc117ELc122ELc122ELc10ELc52ELc49ELc10ELc70ELc105ELc122ELc122ELc10ELc52ELc51ELc10ELc52ELc52ELc10ELc70ELc105ELc122ELc122ELc66ELc117ELc122ELc122ELc10ELc52ELc54ELc10ELc52ELc55ELc10ELc70ELc105ELc122ELc122ELc10ELc52ELc57ELc10ELc66ELc117ELc122ELc122ELc10ELc70ELc105ELc122ELc122ELc10ELc53ELc50ELc10ELc53ELc51ELc10ELc70ELc105ELc122ELc122ELc10ELc66ELc117ELc122ELc122ELc10ELc53ELc54ELc10ELc70ELc105ELc122ELc122ELc10ELc53ELc56ELc10ELc53ELc57ELc10ELc70ELc105ELc122ELc122ELc66ELc117ELc122ELc122ELc10ELc54ELc49ELc10ELc54ELc50ELc10ELc70ELc105ELc122ELc122ELc10ELc54ELc52ELc10ELc66ELc117ELc122ELc122ELc10ELc70ELc105ELc122ELc122ELc10ELc54ELc55ELc10ELc54ELc56ELc10ELc70ELc105ELc122ELc122ELc10ELc66ELc117ELc122ELc122ELc10ELc55ELc49ELc10ELc70ELc105ELc122ELc122ELc10ELc55ELc51ELc10ELc55ELc52ELc10ELc70ELc105ELc122ELc122ELc66ELc117ELc122ELc122ELc10ELc55ELc54ELc10ELc55ELc55ELc10ELc70ELc105ELc122ELc122ELc10ELc55ELc57ELc10ELc66ELc117ELc122ELc122ELc10ELc70ELc105ELc122ELc122ELc10ELc56ELc50ELc10ELc56ELc51ELc10ELc70ELc105ELc122ELc122ELc10ELc66ELc117ELc122ELc122ELc10ELc56ELc54ELc10ELc70ELc105ELc122ELc122ELc10ELc56ELc56ELc10ELc56ELc57ELc10ELc70ELc105ELc122ELc122ELc66ELc117ELc122ELc122ELc10ELc57ELc49ELc10ELc57ELc50ELc10ELc70ELc105ELc122ELc122ELc10ELc57ELc52ELc10ELc66ELc117ELc122ELc122ELc10ELc70ELc105ELc122ELc122ELc10ELc57ELc55ELc10ELc57ELc56ELc10ELc70ELc105ELc122ELc122ELc10ELc66ELc117ELc122ELc122ELc10EEE5c_strEvE3ret
0000000000400a9e u _ZZN8vtstring8vtstringIILc49ELc48ELc48EEE5c_strEvE3ret
0000000000400a91 u _ZZN8vtstring8vtstringIILc72ELc101ELc108ELc108ELc111ELc44ELc87ELc111ELc114ELc108ELc100ELc33EEE5c_strEvE3ret
0000000000601010 d __CTOR_END__
0000000000601000 d __CTOR_LIST__
0000000000601020 D __DTOR_END__
0000000000601018 d __DTOR_LIST__
0000000000400d40 r __FRAME_END__
0000000000601028 d __JCR_END__
0000000000601028 d __JCR_LIST__
0000000000601268 A __bss_start
                 U __cxa_atexit@@GLIBC_2.2.5
0000000000601258 D __data_start
0000000000400a30 t __do_global_ctors_aux
00000000004007f0 t __do_global_dtors_aux
0000000000601260 D __dso_handle
                 w __gmon_start__
0000000000601000 d __init_array_end
0000000000601000 d __init_array_start
0000000000400990 T __libc_csu_fini
00000000004009a0 T __libc_csu_init
                 U __libc_start_main@@GLIBC_2.2.5
0000000000601268 A _edata
00000000006013a8 A _end
0000000000400a6c T _fini
00000000004006e0 T _init
00000000004007a0 T _start
00000000004007cc t call_gmon_start
0000000000601390 b completed.5982
0000000000601258 W data_start
0000000000601398 b dtor_idx.5984
0000000000400860 t frame_dummy
00000000004008e0 T main
                 U strlen@@GLIBC_2.2.5

_ZZN8vtstring8vtstringIILc49ELc10ELc50ELc10... ってのをデマングルすると

vtstring::vtstring<(char)49, (char)10, (char)50, (char)10 ...

という感じ。