lower_bound(), upper_bound()

いつか制覇しようと思っていたlower_bound()とupper_bound()。C++編（標準ライブラリ） 第１８章 並べ替えのアルゴリズムを読むことで理解できた。以下のように考えると分かりやすい。

• lower_bound() と upper_bound() はともに、すでに昇順にソート済のコンテナに対して作用する。
• vector::iterator itr = lower_bound(vec.begin(), vec.end(), 15); と書くと、「vecが昇順にソートされた状態を崩さずに15を挿入可能な場所のうち、もっとも先頭に近い位置」がitrに入る。
• vector::iterator itr = upper_bound(vec.begin(), vec.end(), 15); と書くと、「vecが昇順にソートされた状態を崩さずに15を挿入可能な場所のうち、もっとも末尾に近い位置」がitrに入る。

以下のようなコードを書くと、15が挿入されるべきindexが得られているのが分かる。

#include <iostream>
#include <vector>

using namespace std;

int main(void){
    int _vec[] = {10, 10, 15, 15, 15, 20, 20};
    vector<int> vec(&_vec[0], &_vec[ sizeof(_vec)/sizeof(_vec[0]) ]); // 注意：vecはすでに昇順にソート済なのを前提とする

    vector<int>::iterator itr;
    itr = lower_bound(vec.begin(), vec.end(), 15);
    cout << "15 will be inserted in index " << distance(vec.begin(), itr) << endl;

    itr = upper_bound(vec.begin(), vec.end(), 15);
    cout << "15 will be inserted in index " << distance(vec.begin(), itr) << endl;
                     
    return 0;
}

出力は以下。

15 will be inserted in index 2
15 will be inserted in index 5

insert()をlower_bound()またはupper_bound()と組み合わせることで、ソート済のコンテナに要素を1つ適切な場所に挿入することができる。以下は、コンテナに15を挿入する例。upper_bound()の代わりにlower_bound()を使っても、結果は同じ。

    vec.insert( upper_bound(vec.begin(), vec.end(), 15), 15);