2015-11-24-01-STL書籍の掲載コードをCL-STLで書いてみよう-18
>> Site top >> weblog >> 月別アーカイブ >> 2015年11月のlog >> 2015-11-24-01-STL書籍の掲載コードをCL-STLで書いてみよう-18
最終更新日付:2015/11/24 08:44:40
STL書籍の掲載コードをCL-STLで書いてみよう-18
2015 年 11 月 24 日
いよいよ今回からファンクタの話に入る。前回まででざっくりと説明した通り、ラムダ式やクロージャで大体カタがつくことを考えると不毛な話になりそうだ。とりあえず、Effective STL の「第39項:述語を純粋関数にしよう」をやってみようと思う。
まぁ、要するにこの項で書かれていることは「述語を純粋関数にしないと痛いメに遭うぜ」ということだ。その説明のために使われているのが、BadPredicate というクラス。こいつが呼び出されると、あろうことか「3回目に呼ばれた時だけ真を返す」。
class BadPredicate : public unary_function<Widget, bool> { public: BadPredicate() : timesCalled( 0 ) {} bool operator()( const Widget& ) { return ++timesCalled == 3; } private: size_t timesCalled; }
で、こいつを以下のように使うと何が起きるだろうか、という話。
vector<Widget> vw; //... vw.erase( remove_if( vw.begin(), vw.end(), BadPredicate() ), vw.end() );
ここで参考として提示されているのが、良くある remove_if の実装。find_if で条件を満たす最初の要素を検索し、そこからは remove_copy_if を使用している。
template <typename FwdIterator, typename Predicate> FwdIterator remove_if( FwdIterator begin, FwdIterator end, Predicate p ) { begin = find_if( begin, end, p ); if( begin == end ) return begin; else { FwdIterator next = begin; return remove_copy_if( ++next, end, begin, p ); } }
ここでのキモは、p がコピー渡しされていることだ。だから、p(のコピー)は find_if と remove_copy_if のそれぞれで1回ずつ真を返す。結果として、2つの値が削除されるわけだ。それ故に、述語は純粋関数でなければならん‥‥‥と。
で、これを CL-STL でやりましょうというのにはあまり意味がないのだけれど、一応そういう趣旨のシリーズなのでやりましょう。まずは、bad-predicate クラスを作ってみる。改めて見ると、やっぱりファンクタの作成は煩雑だねぇ。
(defclass bad-predicate (#-cl-stl-0x98 stl:functor #+cl-stl-0x98 stl:unary-function) ((times-called :initform 0 :initarg :times-called :accessor bad-pred-times-called))) (declare-constructor bad-predicate (0)) (labels ((__bad-pred-ctor (n) (let ((obj (make-instance 'bad-predicate :times-called n))) (setf (stl::__functor-closure obj) (lambda (arg) (declare (ignore arg)) (= 3 (incf (bad-pred-times-called obj))))) obj))) (define-constructor bad-predicate () (__bad-pred-ctor 0)) (defmethod operator_clone ((obj bad-predicate)) (__bad-pred-ctor (bad-pred-times-called obj))))
で、問題は remove-if だ。何が問題かというと、CL-STL では find-if や remove-copy-if を使う実装にはなっていないのだ。ファンクタや反復子のコピーを極力避ける目的でそうなっているのだけれど、そのためにこの問題は再現できないのだ。仕方ないので、以下のような my-remove-if を作って試すことにした。
(defun my-remove-if (begin end pred) (let ((begin (stl:find-if begin end pred))) (if (_== begin end) begin (let ((next (clone begin))) (stl:remove-copy-if (_++ next) end begin pred)))))
これを使って以下のようにしてみる‥‥‥お、成功だ。成功というのも変だが、とにかく「2回削除されてしまう」という事象を再現できたわけだ。
(let ((vec (new stl:vector #{0 1 2 3 4 5 6 7 8 9}))) (stl:erase vec (my-remove-if (stl:begin vec) (stl:end vec) (new bad-predicate)) (stl:end vec)) (stl:shrink-to-fit vec) (stl:data vec)) ;=> #(0 1 3 4 6 7 8 9)
先に書いた通り、stl:remove-if の実装はこの問題とは無縁なので、以下のようにしても事象は再現しない。
(let ((vec (new stl:vector #{0 1 2 3 4 5 6 7 8 9}))) (stl:erase vec (stl:remove-if (stl:begin vec) (stl:end vec) (new bad-predicate)) (stl:end vec)) (stl:shrink-to-fit vec) (stl:data vec)) ;=> #(0 1 3 4 5 6 7 8 9)
もちろん、だからといって「CL-STLでは述語を純粋関数にしなくても良い」というつもりはないよ。述語は純粋関数であるべきだし、パラメータ以外のなんらかのデータを参照するとしても、ともかく純粋関数のように振る舞うべきだ。まぁ今回はそんな話でした。
このシリーズのこれまでのエントリ
- 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 - 第5項:単一要素メンバ関数より範囲メンバ関数を使おう
- 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の正しい実装について理解しよう
- 2015-11-03 - 第37項:範囲に関する要約情報を取得するには、accumulateまたはfor_eachを使おう
- 2015-11-05 - 第37項:範囲に関する要約情報を取得するには、accumulateまたはfor_eachを使おう - 2
- 2015-11-24 - 第39項:述語を純粋関数にしよう
コメント
このページのタグ
Page tag : STLとその移植
Page tag : Common Lisp
Copyright(C) 2005-2018 project-enigma.
Generated by CL-PREFAB.