2015-10-30-01-STL書籍の掲載コードをCL-STLで書いてみよう-15
>> Site top >> weblog >> 月別アーカイブ >> 2015年10月のlog >> 2015-10-30-01-STL書籍の掲載コードをCL-STLで書いてみよう-15
最終更新日付：2015/10/30 01:00:00
STL書籍の掲載コードをCL-STLで書いてみよう-15
2015 年 10 月 30 日
アルゴリズムの話がもう少し続く。今回は、第36項、「copy_ifの正しい実装について理解しよう」をやってみよう。
実際問題として、いまや copy_if の正しい作り方を確認する必要はない。C++11 以降、copy_if は STL に正式に追加されているからだ。CL-STL も同様。だが、この項で書かれていることには学ぶことが多いので、ちょっと追いかけてみようと思う。
まずは書籍の内容から。欠陥 Widget を判定する関数 isDefective があるものとして、copy_if があれば以下のようにしてそれらを標準エラー出力に書き出せる。
bool isDefective( const Widget& w );
vector<Widget> widgets;
//...
copy_if( widgets.begin(), widgets.end(),
ostream_iterator<Widget>( cerr, "\n" ), isDefective );
書籍では、述語に not1 をかけたものを使って remove_copy_if を使えばいいと考えた人は多い、としている。著者である Scott Meyers さんもその一人だそうだ。以下のように。
template<typename InputITerator,
typename OutputIterator,
typename Predicate>
OutputIterator copy_if( InputIterator begin, InputIterator end,
OutputIterator destBegin, Predicate p ) {
return remove_copy_if( begn, end, destBegin, not1( p );
}
ただ、これは誤っていると書かれている。理由は、述語パラメータ p に関数を渡すとコンパイルに通らないからだ。アダプタを満足させるためには、関数を ptr_fun に渡した結果を使う必要がある。まぁ、そりゃそうだよね。
ここで、上記のコードと同じことを CL-STL でやったらどうなるだろう？ やはり動作しないのだろうか？ 例えば、以下のように。
(defun my-copy-if (begin end dest-begin pred)
(stl:remove-copy-if begin end
dest-begin (stl:new not1 pred)))
結論を書いてしまえば、CL-STL では上記のコードで動作する。細かい理由は書かないけれど、簡単に言ってしまえば「動的型付け言語である Common Lisp 上に作成された CL-STL では、アダプタが typedef を要求したりはしないから」ということだ。
CL-STL では、ファンクタは関数であれクラスであれ、stl:functor-call という総称関数に応答するもののことだ。関数は CL-STL 自身がデフォルトのメソッドを用意しているので、全ての関数は stl:functor-call できる。ラムダ式も関数だ。だから上記の my-copy-if は以下のようにもできる。これなら not1 オブジェクトを新規に作成する必要もない。
(defun my-copy-if (begin end dest-begin pred)
(stl:remove-copy-if begin end dest-begin
(lambda (v)
(not (stl:functor-call pred v)))))
とはいえ、CL-STL の copy-if が上記のように実装されているわけではない。最大の理由は、stl:functor-call は総称関数であり、汎用的であり、結果として（多少なりとも）遅いからだ。CL-STL の実装を見る前に、書籍に掲載されているcopy_if の「正しい」実装を確認しておこう。
template<typename InputITerator,
typename OutputIterator,
typename Predicate>
OutputIterator copy_if( InputIterator begin, InputIterator end,
OutputIterator destBegin, Predicate p ) {
while( begin != end ) {
if( p( *begin ) )
*destBegin++ = *begin;
++begin;
}
return destBegin;
}
で、CL-STL ではこれが以下のようになる。CL-OPERATOR の with-operators マクロを使っているのでわかりにくいかもしれない。というか、わかりにくいよな。ポイントは、呼び出しにおいては反復子やファンクタのコピーが作成されるわけではないため、明示的にコピーをしなければならないということ、そして、毎回 stl:functor-call を呼ぶのではなく、stl:functor-function で funcall 可能な関数を取得しているということだ。このあたりの仕組みは後日改めて書くことになるだろう。
(defmethod copy-if ((first input-iterator)
(last input-iterator) (result output-iterator) pred)
(with-operators
(let ((dest @~result))
(if (_== first last)
dest
(let ((pred (functor-function @~pred)))
(declare (type cl:function pred))
(for (((itr @~first)) (_/= itr last) ++itr :returns dest)
(let ((v *itr))
(when (funcall pred v)
(_= *dest v)
++dest))))))))
実際には、上記の実装は「総称関数の実装メソッドのひとつ」でしかない。最適化のために、渡された反復子がポインタベースのものだった場合や、コンスリストベースのものだった場合のために特殊化されたメソッドがたくさんある。これらの「実装詳細を理解しているライブラリによる最適化」は結構多くの局面で機能するため、上記のように総称関数呼び出しだらけに見えることから想像される程パフォーマンスは悪くない。‥‥‥と思う。
さて、次回も Effective STL だが、アルゴリズムの章の最後になる。そのあとはいよいよファンクタの話になる。というか、10月中にアルゴリズムの章を終わらせるつもりだったんだけどな。
このシリーズのこれまでのエントリ
- 2015-09-19 - 第47項：書き込み専用コードの作成は避けよう
- 2015-09-20 - 第9項：消去オプションは注意して選択しよう
- 2015-09-22 - 第9項：消去オプションは注意して選択しよう - 2
- 2015-09-28 - 第9項：消去オプションは注意して選択しよう - 3
- 2015-09-30 - 第14項：reserve を使って不必要な割り当てを避けよう
- 2015-10-01 - 第17項：余分な容量を取り除くには「swap技法」を使おう
- 2015-10-09 - 第27項：コンテナのconst_iteratorをiteratorに変換するには、distanceとadvanceを使おう
- 2015-10-12 - 第５項：単一要素メンバ関数より範囲メンバ関数を使おう
- 2015-10-14 - 第30項：出力先範囲の大きさを確認しよう
- 2015-10-16 - 第31項：ソートの選択肢を知っておこう
- 2015-10-17 - 第31項：ソートの選択肢を知っておこう - 2
- 2015-10-23 - 第32項：本当に削除したい場合は、remove風アルゴリズムの後にeraseを使おう
- 2015-10-25 - 第33項：ポインタのコンテナには注意してremove風アルゴリズムを使おう
- 2015-10-28 - 第34項：ソート済み範囲を必要とするアルゴリズムに注意しよう
- 2015-10-30 - 第36項：copy_ifの正しい実装について理解しよう
コメント
このページのタグ
Page tag : STLとその移植
Page tag : Common Lisp
Copyright(C) 2005-2018 project-enigma.
Generated by CL-PREFAB.
