C++ STLのsetコンテナでlower_bound()関数を使う方法

C++ STLのsetコンテナには、lower_bound()という便利なメンバ関数が用意されています。この関数は、引数として渡した値kと等しい要素を指すイテレータを返します。もしkがset内に存在しない場合は、「kより大きい要素のうち最小のもの」、つまり直後の要素を指すイテレータを返します。

setは内部的に要素を常にソート済みの状態で保持しているため、lower_bound()は二分探索によってO(log n)の計算量で効率的に動作します。

アルゴリズム

Begin
    空のsetコンテナsを初期化する。
    lower boundの値を指すためのイテレータを宣言する。
    setコンテナsに要素をいくつか挿入する。
    引数で渡したキーのlower boundを求める関数を呼び出し、
    結果をイテレータiterに格納する。
    求めたキーのlower boundの値を出力する。
End.

サンプルコード

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> s;               // 空のsetコンテナを宣言
    set<int>::iterator iter;  // lower boundの値を指すイテレータを宣言

    s.insert(7);              // setコンテナsに要素を挿入
    s.insert(6);
    s.insert(1);
    s.insert(4);
    s.insert(2);
    s.insert(9);
    s.insert(10);

    iter = s.lower_bound(4);  // キーを引数に渡してlower boundを取得
    cout << "The lower bound of 4 is: " << *iter << endl;

    iter = s.lower_bound(5);  // 5は存在しないため、次に大きい6が返る
    cout << "The lower bound of 5 is: " << *iter << endl;

    iter = s.lower_bound(8);  // 8は存在しないため、次に大きい9が返る
    cout << "The lower bound of 8 is: " << *iter << endl;

    return 0;
}

実行結果

The lower bound of 4 is: 4
The lower bound of 5 is: 6
The lower bound of 8 is: 9

ポイント解説

• キーが存在する場合： そのキー自身を指すイテレータが返されます（例： lower_bound(4) → 4）。
• キーが存在しない場合： キーより大きい最初の要素を指すイテレータが返されます（例： lower_bound(5) → 6）。
• 注意点： キーがコンテナ内の全要素よりも大きい場合、lower_bound()は終端イテレータend()を返します。end()を逆参照（*）すると未定義動作になるため、実際にアクセスする前にiter != s.end()のチェックを行うことが重要です。