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 21:52:04

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 - 第５項：単一要素メンバ関数より範囲メンバ関数を使おう
• 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-2017 project-enigma.
Generated by CL-PREFAB.