2015-12-17-01-STL書籍の掲載コードをCL-STLで書いてみよう-23
>> Site top >> weblog >> 月別アーカイブ >> 2015年12月のlog >> 2015-12-17-01-STL書籍の掲載コードをCL-STLで書いてみよう-23
最終更新日付:2015/12/17 01:00:00
STL書籍の掲載コードをCL-STLで書いてみよう-23
2015 年 12 月 17 日
気がついたらもう10日も放置しているこのシリーズ。そろそろ Effective STL の話は終わりにしたいので頑張るとしよう(その後何をやるか決めてないのだけど)。今回はタイトルが長いな。「第45項:count、find、binary_search、lower_bound、upper_bound、およびequal_rangeの違いを理解しよう」から。
さて、第45項の趣旨はと言えば、ソート済み(あるいはそうでない)シーケンスや連想コンテナにおいて、どのような局面でどの検索系アルゴリズム(または同名のメソッド)を使用するべきか、というものだ。この項は長いので、とりあえず流していこう。
まず、ソートしていないシーケンスで指定した値を数える場合。これは count アルゴリズム一択だ。線型時間がかかる。
list<Widget> lw; Widget w; //... if( std::count( lw.begin(), lw.end(), w ) ) { //... } else { //... }
で、これが CL-STL だと以下のようになる。あ、そうそう。Widget は面倒なので、CL-STL のコードサンプルでは全て整数値を使う。うん、面倒。
(let ((lw (new stl:list #{0 1 2 3 4 5 6 7 8 9})) (w 6)) (if (< 0 (stl:count (stl:begin lw) (stl:end lw) w)) :found :not-found)) ;=> :FOUND
次、カウントするのではなく、最初に見つかった要素の位置を知りたい場合。ソートされていないシーケンスの場合は find アルゴリズムを使うしかない。これも線型時間。そしてこれは反復子を返すので、見つかったかどうかの判定には end 反復子の結果と比較しなければならない。
if( std::find( lw.begin(), lw.end(), w ) != lw.end() ) { //... } else { //... }
CL-STL だと以下。
(let ((lw (new stl:list #{4 0 10 8 6 2})) (w 5)) (if (_/= (stl:find (stl:begin lw) (stl:end lw) w) (stl:end lw)) :found :not-found)) ;=> :NOT-FOUND
ただし、通常は見つかった場合にその反復子で何かしたいはずなので、以下のようになるよ、という話。そりゃそうだよね。
list<Widget>::iterator i = std::find( lw.begin(), lw.end(), w ); if( i != lw.end() ) { //... } else { //... }
CL-STL なら以下のように。
(let ((lw (new stl:list #{0 2 4 6 8 10})) (w 8)) (let ((i (stl:find (stl:begin lw) (stl:end lw) w))) (if (_/= i (stl:end lw)) i :not-found))) ;=> #<CL-STL:LIST-ITERATOR {1005463F23}>
では次にソート済みのランダムアクセスコンテナにいこう。二分探索で要素の有無だけを調べられれば良いなら、binary_search アルゴリズムの出番だ。こいつは真偽値を返すだけ。
vector<Widget> vw; //... std::sort( vw.begin(), vw.end() ); Widget w; //... if( std::binary_search( vw.begin(), vw.end(), w ) ) { //... } else { //... }
CL-STL ならこんな感じ。ここからはランダムなシーケンスを生成してソートしてから動かすように書いているため、実行するたびに結果が違う。
(let ((vw (new stl:vector 100))) (stl:generate (stl:begin vw) (stl:end vw) (lambda () (random 100))) (stl:sort (stl:begin vw) (stl:end vw)) (let ((w 13)) (if (stl:binary-search (stl:begin vw) (stl:end vw) w) :found :not-found))) ;=> :NOT-FOUND
二分探索で見つかった場合にその要素を指す反復子が必要なら、lower_bound を使う必要がある。
vector<Widget>::iterator i = lower_bound( vw.begin(), vw.end(), w ); if( i != vw.end() && *i == w ) { //... } else { //... }
lower_bound は常に反復子を返すから、end 反復子以外が返された場合でも値のチェックが必要だ。慣れるまでは頭に入り難いかもしれないが、lower_bound がやることは「指定された値よりも小さくない最小の要素を返す」ということだ。ちなみに、upper_bound は「指定された値よりも大きい最小の要素を返す」。
それはさておき、CL-STL ならこう。
(let ((vw (new stl:vector 100))) (stl:generate (stl:begin vw) (stl:end vw) (lambda () (random 100))) (stl:sort (stl:begin vw) (stl:end vw)) (let* ((w 13) (i (stl:lower-bound (stl:begin vw) (stl:end vw) w))) (if (and (_/= i (stl:end vw)) (_== (_* i) w)) i :not-found))) ;=> #<CL-STL:VECTOR-ITERATOR {1005FA0D93}>
ちなみに、lower-bound は「等価」を基準にして検索している一方、上記の if では「等値」で復帰値のチェックをしている、これは問題になる場合があるよ、という話が書籍にはあるが、これは割愛。
で、割愛された上記の話題に関連して「等価な要素の数を調べる効果的な方法」として挙げられているのが、equal_range を使う方法。これは要するに lower_bound と upper_bound の併わせ技だ。
vector<Widget> w; //... std::sort( vw.begin(), vw.end() ); typedef vector<Widget>::iterator VWIter; typedef pair<VWiter,VWiter> VWIterPair; VWIterPair p = std::equal_range( vw.begin(), vw.end(), w ); if( p.first != p.second ) { //... } else { //... }
CL-STL ならこう。まぁなんというか、ちゃんと動く。
(let ((vw (new stl:vector #{0 1 2 3 4 1 2 3 4 2 3 4 3 4 4}))) (stl:sort (stl:begin vw) (stl:end vw)) (let* ((w 3) (p (stl:equal-range (stl:begin vw) (stl:end vw) w))) (if (_/= (stl:first p) (stl:second p)) (stl:distance (stl:first p) (stl:second p)) :not-found))) ;=> 4
あ—、なんていうか、疲れてしまった。今回はここまでにしよう。この第45項でさらに書くことがあるかどうかは改めて確認して、あれば次回は続きをやるということで。
このシリーズのこれまでのエントリ
- 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項:述語を純粋関数にしよう
- 2015-12-02 - 第40項:ファンクタクラスを変換可能にしよう
- 2015-12-03 - 第43項:独自に作成したループよりアルゴリズムの呼び出しを優先して使おう
- 2015-12-04 - 第43項:独自に作成したループよりアルゴリズムの呼び出しを優先して使おう - 2
- 2015-12-08 - 第44項:アルゴリズムより同名のメンバ関数を優先して使おう
- 2015-12-17 - 第45項:count、find、binary_search、lower_bound、upper_bound、およびequal_rangeの違いを理解しよう
コメント
このページのタグ
Page tag : STLとその移植
Page tag : Common Lisp
Copyright(C) 2005-2021 project-enigma.
Generated by CL-PREFAB.