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

2015-12-21-01-STL書籍の掲載コードをCL-STLで書いてみよう-24

>> Site top >> weblog >> 月別アーカイブ >> 2015年12月のlog >> 2015-12-21-01-STL書籍の掲載コードをCL-STLで書いてみよう-24

最終更新日付:2015/12/21 22:19:46


STL書籍の掲載コードをCL-STLで書いてみよう-24

2015 年 12 月 21 日

前回に続いて、「第45項:count、find、binary_search、lower_bound、upper_bound、およびequal_rangeの違いを理解しよう」から少しだけお釣り拾い。そう、ほんの少し。

拾っておきたいのは、 lower_boundupper_bound を(挿入や削除の)位置特定に使用するという話題。Effective STL では、以下のようにタイムスタンプだの ageLimit だのというコードが示されていた。

Timestamp ageLimit;
//...
vt.erase( vt.begin(),
          std::lower_bound( vt.begin(), vt.end(), ageLimit ));

 

ご想像通り、Timestamp とか正直面倒なので、ここは整数値だけで勘弁願おう。ここでは、「3 より小さな値を全て削除」している。lower-bound は「指定された値よりも小さくない最小の要素を検索」するから、以下のコードはシーケンス中に 3 がなくても正しく動作する。

(let ((vt (new stl:vector #{1 2 2 3 3 3 4 4 4 4 5 5 5 5 5})))
  (stl:erase vt (stl:begin vt)
                (stl:lower-bound (stl:begin vt)
                                 (stl:end   vt) 3))
  (stl:for (n vt) (format t " ~A" n)))

;=> 3 3 3 4 4 4 4 5 5 5 5 5

 

同様に、「3 以下の値を全て削除」なら upper-bound を使えば良い。

(let ((vt (new stl:vector #{1 2 2 3 3 3 4 4 4 4 5 5 5 5 5})))
  (stl:erase vt (stl:begin vt)
                (stl:upper-bound (stl:begin vt)
                                 (stl:end   vt) 3))
  (stl:for (n vt) (format t " ~A" n)))

;=>  4 4 4 4 5 5 5 5 5

 

次は挿入位置の特定。Effective STL では、以下のようなコードが示されていた。lpPerson クラスのための std::list だ。名前順にソートされているこのシーケンスに「新人」を割り込ませる位置を特定するために upper_bound を使用しているわけだ。同姓同名のオブジェクトがすでにいる場合、upper_boundlower_bound の使い分けがどのような効果を生むか、考えてみて欲しい。

Person newPerson;
//...
lp.insert( std::upper_bound( lp.begin(), lp.end(),
                             newPerson, PersonNameLess ),
           newPerson );

 

同じ(ような)ことをする CL-STL コードは以下の通りだ。

(let ((lp (new stl:list #{"tinker" "tailor" "soldier"})))
  (stl:sort lp #'string<)
  (let ((name "spy"))
    (stl:insert lp (stl:upper-bound (stl:begin lp)
                                    (stl:end   lp) name #'string<)
                name))
  (stl:for (n lp) (format t " ~A" n)))

;=> soldier spy tailor tinker

 

ところで、だ。list のシーケンスに対して upper-bound が使えることに驚いた人がいるかもしれない(もちろん lower-bound も同じだ)。自分も以前はランダムアクセスシーケンスにしか使えないと思い込んでいた。これは CL-STL に限った話ではない。STL においてもこれらのアルゴリズムが取るパラメータはランダムアクセス反復子ではなく前方向反復子なのだ。だからこれらのアルゴリズムが保証するのは『対数オーダの比較回数』だけだ。探索は線型時間がかかる場合がある。それは与える反復子の種類による。

そんなわけで第45項はおしまい。

 

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

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


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