2015-11-24-01-STL書籍の掲載コードをCL-STLで書いてみよう-18 - project-enigma

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_ifremove_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-ifremove-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では述語を純粋関数にしなくても良い」というつもりはないよ。述語は純粋関数であるべきだし、パラメータ以外のなんらかのデータを参照するとしても、ともかく純粋関数のように振る舞うべきだ。まぁ今回はそんな話でした。

 

このシリーズのこれまでのエントリ

 

コメント

このページにコメントする

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.