BoostのMPLへのいざない part 2

　Boostのチュートリアルでは、STLのiter_swapを実装しているけれど、同じにするのでは能がない。ここでは、STLのcopyのようなものの実装を通して、型計算を学ぶことにしよう 2 型計算 2.1 君に仕事だ 　君は、とあるプロジェクトで働くことになった。君に割り当てられた仕事は、copy_and_sumという関数を実装することだ。これは、STLのcopyのように振舞いつつ、コピーする値をすべて加算して、合計を返すという関数だ。次のように使う。

int main() { std::vector<int> src, dest(3) ; src.push_back(1) ; src.push_back(2) ; src.push_back(3) ; int ret = copy_and_sum( src.begin(), src.end(), dest.begin() ) ; std::cout << ret << std::endl ; // 6 std::cout << dest[0] << dest[1] << dest[2] << std::endl ; // 123 }

2.2 早速実装しよう 　優秀な君ならば、ものの5分で書けるだろう。ちょろい仕事だ。さて、さっそくにも実装しようとしたが、問題がある。

template < typename InputIterator, typename OutputIterator > T copy_and_sum ( InputIterator first, InputIterator last , OutputIterator result ) ;

　いったい、どうやって戻り値の型、Tを指定すればいいのだろう。引数の型は、イテレータなのだ。値とは、イテレータを参照したときの型だ。しかし君は迷わない。ド素人ならいざ知らず、君はSTLを呼吸している男だ。だからこそ、このプロジェクトにも抜てきされたのだ。君は、すべてのイテレータには、value_typeという型がネストされていることを知っている。ソレを使えばよい。

template < typename InputIterator, typename OutputIterator > typename InputIterator::value_type copy_and_sum ( InputIterator first, InputIterator last , OutputIterator result ) { typedef typename InputIterator::value_type value_type ; value_type ret = value_type() ; while ( first != last) { ret += *first ; *result = *first ; ++first ; ++result ; } return ret ; }

　C++を呼吸している優秀な君は、Dependant Nameを型として扱う場合には、typenameをつけなければならないということをも、当然知っている。君はこの美しいまでに完璧なコードをコミットした。 2.3 問題発生 　ところが、君の同僚が、次のような文句をつけてきた。以下のコードがコンパイルできないというのだ。

void f( int * first, int * last, int * dest) { int ret = copy_and_sum(first, last, dest) ; }

　これは問題だ。intのポインタ型には、ネストされた型など存在しない。一体どうすればいいのだろう。 2.4 長い長い道のり 　優秀なプログラマであり、現在はMS社で働いている、Butler Lampsonは言った。 　　"We can solve any problem by introducing an extra level of indirection." 　　「あらゆる問題は、ラッパをかませば解決する」と。 　この言葉は、かのAndrew Koenigも、この考えが好きで、彼の著作、RUMINATIONS on C++では、難しい問題をクラスで包み、参照カウントを使って解決している。 　int型のポインタにvalue_typeなどというネストされた型を付け加えることはできないが、そのようなテンプレートクラスを作ることはできる。幸いにも、この考え方は実に一般的で、STLには、iterator_traitsというクラスがある。コレを使えば、次のようにコードを書き直すことができる。

template < typename InputIterator, typename OutputIterator > typename std::iterator_traits<InputIterator>::value_type copy_and_sum ( InputIterator first, InputIterator last , OutputIterator result ) { typedef typename std::iterator_traits<InputIterator>::value_type value_type ; value_type ret = value_type() ; while ( first != last) { ret += *first ; *result = *first ; ++first ; ++result ; } return ret ; }

　これがいわゆる、ラッパだ。ネストされたvalue_typeを直接使う代わりに、iterator_traitsで包み、差を許容する。iterator_traitsは、部分的特殊化(partial specialization)をつかい、すべてのポインタに対して、value_typeなどを提供している。また、そのほかにも、 2.5 メタ関数という概念 　ここでは概念の説明をするが、すこし眠くなりそうな話なので、コーヒーなどをすすりつつ読んでほしい。 　ここで、前回のbinaryやiterator_traitsと、普通の関数との間に、何か似たような性質を感じないだろうか。普通の関数は、実行時に、引数とともに呼び出され、値を返す。一方、iterator_traitsは、コンパイル時に、型を引数として渡され、型を返す。binaryでは、コンパイル時の定数として、値を返すことができた。これらの性質から、関数に似ているといえる。このテンプレートクラスのことを、メタ関数(Metafunction)と呼ぶことにしよう。メタ関数、コレは重要な概念である。メタ関数には、次のような特色がある。 　・特殊化(Specialization) 　　　ある型に対して、別定義のクラスを用意することができる。一種の条件分岐だ。とくに、部分的特殊化(partial specialization)をつかえば、すべてのポインタに対する条件分岐をさせることができる。 　・多値を返す(Multiple "return values") 　　　C++では、普通の関数は、ひとつしか値を返せないが、メタ関数は、複数の値を返すことができる。単に、複数のtypedefを作ればいい。 　Boostでは、多値を返すメタ関数を、Blob(ある映画由来の造語)として敬遠している。なぜならば、多くの戻り値があるということは、それだけテンプレートの実体化(instantiate)が面倒になり、コンパイルが遅くなるからだ。必要な戻り値だけを定義すべきだ。 　また、ポリモーフィズムの観点から言っても、アンチパターンである。そこで、Boostのライブラリでは、メタ関数は次のようになっている。

metafunction-name<type-arguments ...>::type

　メタ関数とは、明示的に呼び出す(invoke)必要がある。呼び出す(invoke)とは、テンプレートを実体化(instanciate)することである。実体化(instanciate)するためには、クラス内部の型や定数を参照しなければならない。

// Point of Declaration template < typename T > struct metafuncion ; template < typename T > struct metafunction { typedef T type ; } ;//Point of Definition void f() { typedef metafunction<int> mf ; // ここでは実体化されない typedef metafunction<mf> mmf ; //ここでも実体化されない typedef mmf::type::type type ; // Point of Instanciation }

　Boostでは、メタ関数とは、ネストされた型typeによって呼び出す(invoke)ことができるものをさす。 2.6 数値メタ関数 　メタ関数は、数値を返すこともできる。文法は、次のとおりである。

metafunction-name<type-arguments ...>::type::value

　いくつかのメタ関数は、typeでメタ関数を呼び出さなくても、直接valueを持っている。コレは主に、コードを簡潔にするためだ。 2.7 コンパイル時の選択 　さて、仕事に戻ろう。iterator_traitsを使った、copy_and_sumをコミットした君の元へ、ベンチマークを取っている同僚から、バグ票があがってくる。なんと、copy_and_sumが遅いというのだ。話を聞くと、int型の配列で、まず合計値を計算し、つぎにmemcpyを使ってコピーした場合と、copy_and_sum関数を使った場合を比較すると、copy_and_sum関数が1.5倍ほど遅いらしい。 　コピーするコードは、この上もなくシンプルなので、これ以上改良しようがない。おそらく、コンパイラベンダーは、memcpyに特殊な最適化を施しているのだろう。しかし、copy_and_sumの実装で、memcpyを使うわけには行かない。なぜならば、memcpyを使えるのは、ビットワイズコピーが許される、POD(Plain old data)型に限られているからだ。 　ここで、コンパイル時に、選択をする必要に迫られる。もし、InputIteratorとOutputIteratorの型が同じで、int *型や float *型といった型であれば、memcpyを使ってもよいだろう。それ以外は、依然と同じように処理するのだ。この型を判断するには、テンプレートの特殊化を使い、int型やfloat型などのときだけ、trueを返すようなメタ関数を作ってやればよい。

template < typename T > struct is_it_ok_to_memcpy { static bool const value = false ; } ; template < > struct is_it_ok_to_memcpy< int > { static bool const value = true ; } ; template < > struct is_it_ok_to_memcpy< unsigned int > { static bool const value = true ; } ; template < > struct is_it_ok_to_memcpy< float > { static bool const value = true ; } ; void f() { is_it_ok_to_memcpy< int >::value ; // true is_it_ok_to_memcpy< float >::value ; // true is_it_ok_to_memcpy< std::vector<int> >::value ; // false }

　しかし、必要になるたびに、いちいち作っていくのは面倒だ。幸いにして、Boostには、type_traitsという便利なライブラリがある。コレを使おう。すぐにもこのように書きたいところだが、それはできない。

template < typename InputIterator, typename OutputIterator > typename std::iterator_traits<InputIterator>::value_type copy_and_sum ( InputIterator first, InputIterator last , OutputIterator result ) { typedef typename std::iterator_traits<InputIterator>::value_type value_type ; value_type ret = value_type() ; typedef boost::remove_cv<InputIterator>::type itype ; typedef boost::remove_cv<OutputIterator>::type otype ; typedef boost::remove_pointer<InputIterator>::type irptype ; if ( boost::is_same<itype, otype>::value && boost::is_arithmetic< irptype >::value ) { memcpy(result, first, sizeof(irptype) * static_cast<size_t>(last - first) ) ; while ( first != last ) { ret += *first ; ++first ; } } else { while ( first != last ) { ret += *first ; *result = *first ; ++first ; ++result ; } } return ret ; }

　何が悪いのか。このコードでは、if文の両方の分岐がコンパイルされてしまう。普通のイテレータは、void *型に変換できないので、コンパイルエラーとなる。ここでは、片方だけがコンパイルされるような工夫が必要だ。そこで、次のようになる。

template < bool b > struct copy_and_sum_impl { template < typename InputIterator, typename OutputIterator > static typename std::iterator_traits<InputIterator>::value_type do_it ( InputIterator first, InputIterator last , OutputIterator result ) { typedef typename std::iterator_traits<InputIterator>::value_type value_type ; value_type ret = value_type() ; while ( first != last ) { ret += *first ; *result = *first ; ++first ; ++result ; } return ret ; } } ; template < > struct copy_and_sum_impl< true > { template < typename InputIterator, typename OutputIterator > static typename std::iterator_traits<InputIterator>::value_type do_it ( InputIterator first, InputIterator last , OutputIterator result ) { typedef typename std::iterator_traits<InputIterator>::value_type value_type ; value_type ret = value_type() ; typedef boost::remove_pointer<InputIterator>::type irptype ; memcpy(result, first, sizeof(irptype) * static_cast<size_t>(last - first) ) ; while ( first != last ) { ret += *first ; ++first ; } return ret ; } } ; template < typename InputIterator, typename OutputIterator > typename std::iterator_traits<InputIterator>::value_type copy_and_sum ( InputIterator first, InputIterator last , OutputIterator result ) { typedef boost::remove_cv<InputIterator>::type itype ; typedef boost::remove_cv<OutputIterator>::type otype ; typedef boost::remove_pointer<InputIterator>::type irptype ; bool const b = boost::is_same<itype, otype>::value && boost::is_arithmetic< irptype >::value ; return copy_and_sum_impl< b >::do_it(first, last, result) ; }

　分かりにくい？　それならば、これならどうか。

struct oridinary_impl { template < typename InputIterator, typename OutputIterator > static typename std::iterator_traits<InputIterator>::value_type do_it ( InputIterator first, InputIterator last , OutputIterator result ) { typedef typename std::iterator_traits<InputIterator>::value_type value_type ; value_type ret = value_type() ; while ( first != last ) { ret += *first ; *result = *first ; ++first ; ++result ; } return ret ; } } ; struct memcpy_impl { template < typename InputIterator, typename OutputIterator > static typename std::iterator_traits<InputIterator>::value_type do_it ( InputIterator first, InputIterator last , OutputIterator result ) { typedef typename std::iterator_traits<InputIterator>::value_type value_type ; value_type ret = value_type() ; typedef boost::remove_pointer<InputIterator>::type irptype ; memcpy(result, first, sizeof(irptype) * static_cast<size_t>(last - first) ) ; while ( first != last ) { ret += *first ; ++first ; } return ret ; } } ; template < typename InputIterator, typename OutputIterator > typename std::iterator_traits<InputIterator>::value_type copy_and_sum ( InputIterator first, InputIterator last , OutputIterator result ) { typedef boost::remove_cv<InputIterator>::type itype ; typedef boost::remove_cv<OutputIterator>::type otype ; typedef boost::remove_pointer<InputIterator>::type irptype ; return boost::mpl::eval_if < boost::mpl::and_< boost::is_same<itype, otype> , boost::is_arithmetic< irptype > > , memcpy_impl , oridinary_impl >::do_it(first, last, result) ; }

　MPLを使えば、このような記述が可能だ。