34項 ソート済み範囲を必要とするアルゴリズムに注意しよう

ソート済み範囲を必要とするアルゴリズムに注意しよう

binary_serachやset_unionなどは、ソート済み範囲を必要とします。ソートされていない範囲にアルゴリズムを使うと未定義の動作が起こります。

また、ソートの昇順や降順にも気をつける必要があります。
binary_serachは、デフォルトで昇順にソートされた範囲を前提としているので、次のコードは未定義になります。

vector<int> v;
...
sort(v.begin(), v.end(), greater<int>()); //降順にソートする
...

bool a5Exists = 
        binary_search(v.begin(), v.end(), 5); //binary_searchは昇順を前提としている

正しく動かすには、sortに使った比較関数をbinary_searchでも使います。

bool a5Exists = 
        binary_search(v.begin(), v.end(), 5, greater<int>());