はじめてのテンプレートメタプログラミング

や、初めてじゃないんだけどね（＾＾；　だけどそれなりに本格的にやったのは始めてかも。
テンプレートメタプログラミングというのは簡単に言えばテンプレートの静的展開を利用した高速化です。詳しくはこちらのページに書いてあります。
http://ubiety.uwaterloo.ca/~tveldhui/papers/Template-Metaprograms/
以前も紹介した気もしますがまあいいや。

んで今回何を作ったかというと、固定長配列におけるバイナリサーチです。ソート済みの固定長配列にある値がどこに挿入されるかという問題。解決方法は中心の値を見て大きければ上半分で、小さければ下半分でまた同じように中心の値を見るという方法。速度は理論上はＯ(logＮ)になるはずです。
まあぶっちゃけ。STLのstd::lower_boundです（＾＾；　結果も大体同じのを返します。

というわけで実装。

template< class I, unsigned int SIZE, class RAN_IT = I* >
struct BinarySearch{
	static inline RAN_IT Search( RAN_IT aBuffer, I value ){
		return ( value < aBuffer[SIZE>>1] ) ? BinarySearch< I, (SIZE>>1), RAN_IT >::Search( aBuffer, value ) :
			( ( value > aBuffer[SIZE>>1] ) ? BinarySearch< I, ((SIZE-1)>>1), RAN_IT >::Search( aBuffer + ((SIZE>>1)+1), value ) :
			aBuffer + (SIZE>>1) );
	}
};

template< class I, class RAN_IT >
struct BinarySearch< I, 0, RAN_IT >
{
	static inline RAN_IT Search( RAN_IT aBuffer, I value ){
		return aBuffer;
	}
};

使い方はstd::lower_boundとほぼ一緒です。
int a[100];
int* p = BinarySearch< int, 100 >::Search( a, 10 );
//↑10の位置を探す。
実際にlower_boundと比較したのですが、一応恐ろしく早くなっています。が、早くなった理由がテンプレートメタプログラミングの結果かどうかはわかりません。
まず、lower_boundは、配列の中身に比較対象と一致したのがあれば、それの一番下に持ってくるような仕様になっています。一方で今回の自作関数はたまたま見つけたらそのポインタをいきなり返します(そもそも一番下に持ってくる必要性が個人的には不要だったので)。なのでそもそもの検索回数が少ないです。
あともう一つ、そもそもテンプレート展開されているかが怪しいです。まSIZEに100000とか入れてテストしたのですが、ちゃんと展開されているなら100000個もクラスが生成されるはずなのに出来上がったバイナリはたったの10kbyteしかなかった。どうも怪しい・・・。
とはいえ、とりあえずlower_boundの100倍以上の速度がでたのでよしとします（ぇー

最後に気が付いたんだけど、固定長なのにランダムイテレータとか間抜けなことやってた（＾＾；　まあ固定長配列クラスとかでイテレータがあれば使えますよきっと。