2015-10-28-01-STL書籍の掲載コードをCL-STLで書いてみよう-14 - project-enigma

2015-10-28-01-STL書籍の掲載コードをCL-STLで書いてみよう-14

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

最終更新日付:2015/10/28 21:52:11


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

2015 年 10 月 28 日

今回は Effective STL の第34項、「ソート済み範囲を必要とするアルゴリズムに注意しよう」で。コードは少ないけど。

まず、「ソートされたデータしか処理しないアルゴリズムのリスト」を見ておこう。

まぁ、なんていうか、STL に慣れている人間には「そりゃそうだよね」と言われて終わる話でしかない。まぁそう言わずに続けよう。最初の4つは二分探索をするために対象範囲がソートされていることを要求する。また、続く4つは集合演算で、線型時間での実行を保証するために対象範囲がソートされていることを要求する。残る3つは、マージや包含関係の確認のためにやはりソート範囲を要求する‥‥‥と。

あと、これとは別に2つのアルゴリズムが挙げられている。これは、必ずしもソート範囲でなくても良い、という理由からだ。隣接する等値要素を(removeアルゴリズムと同じ意味で)削除するというモノ。

で、「対象範囲がソートされていること」という要求を満足するためには、なんていうか、当たり前だけどソートをする必要があるわけで、そのソートをする際に明示的に比較述語を指定した場合には前述のアルゴリズムを呼び出す場合に注意が必要ですよ、という話になるわけだ。以下は書籍に掲載されているマズい例。

vector<int> v;
//...
sort( v.begin(), v.end(), greater<int>() );
//...

bool a5Exists = binary_search( v.begin(), v.end(), 5 );

 

上記では greater<int> でもってソートをしているが、binary_search の呼び出しでは比較述語を指定していない。これだと、binary_searchoperator< でもって対象範囲がソートされているものと仮定して処理を行なうわけだ。これと同じコードを CL-STL で書いて、実際に動かしてみよう。以下のようになる。あ、ちなみに stl:greater を使う理由はないので #'> を渡している。

(let ((v (new stl:vector #{0 1 2 3 4 5 6 7 8 9})))
  (stl:sort (stl:begin v) (stl:end v) #'>)
  (let ((a5-exists (stl:binary-search (stl:begin v) (stl:end v) 5)))
    a5-exists))

;=> NIL

 

実際、期待した動作をしなかったわけだな。これを正しく動作するコードにするには、stl:binary-search にもソートと同じ比較述語を渡す必要がある。書籍のコードは面倒なので掲載せず、CL-STL のコードだけにしておこう。こうなる。

(let ((v (new stl:vector #{0 1 2 3 4 5 6 7 8 9})))
  (stl:sort (stl:begin v) (stl:end v) #'>)
  (let ((a5-exists (stl:binary-search (stl:begin v) (stl:end v) 5 #'>)))
    a5-exists))

;=> T

 

まぁ、こんな感じです。ではまた次回。

 

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

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


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