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 01:00:00
STL書籍の掲載コードをCL-STLで書いてみよう-18
2015 年 11 月 24 日
いよいよ今回からファンクタの話に入る。前回まででざっくりと説明した通り、ラムダ式やクロージャで大体カタがつくことを考えると不毛な話になりそうだ。とりあえず、Effective STL の「第39項：述語を純粋関数にしよう」をやってみようと思う。
まぁ、要するにこの項で書かれていることは「述語を純粋関数にしないと痛いメに遭うぜ」ということだ。その説明のために使われているのが、BadPredicate というクラス。こいつが呼び出されると、あろうことか「３回目に呼ばれた時だけ真を返す」。
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 のそれぞれで１回ずつ真を返す。結果として、２つの値が削除されるわけだ。それ故に、述語は純粋関数でなければならん‥‥‥と。
で、これを 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)))))
これを使って以下のようにしてみる‥‥‥お、成功だ。成功というのも変だが、とにかく「２回削除されてしまう」という事象を再現できたわけだ。
(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 - 第５項：単一要素メンバ関数より範囲メンバ関数を使おう
- 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.
