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 01:00:00

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

2015 年 10 月 28 日

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

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

• binary-search
• lower-bound
• upper-bound
• equal-range
• set-union
• set-intersection
• set-difference
• set-symmetric-difference
• merge
• inplace-merge
• include

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

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

• unique
• unique-copy

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

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

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

上記では greater<int> でもってソートをしているが、binary_search の呼び出しでは比較述語を指定していない。これだと、binary_search は operator< でもって対象範囲がソートされているものと仮定して処理を行なうわけだ。これと同じコードを 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

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

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

• 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項：ソート済み範囲を必要とするアルゴリズムに注意しよう

コメント

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

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

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