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を使えば、このような記述が可能だ。
No comments:
Post a Comment