【C++ STL】multisetのlower_bound()関数を実例付きでわかりやすく解説

この記事では、C++ STLにおける multiset コンテナの lower_bound() 関数について、実際のコード例を交えながら詳しく解説します。

lower_bound()関数とは

lower_bound() は、指定したキー値以上の要素がコンテナ内に最初に現れる位置を指すイテレータを返す関数です。具体的には、以下のような動作を行います。

• 引数に渡した値と等しい要素がコンテナ内に存在する場合、そのうち最初の要素へのイテレータを返します。
• 等しい要素が存在しない場合は、渡した値より大きい要素のうち最小のもの（直後に続く要素）へのイテレータを返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int main(){
    multiset<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(2);
    s.insert(1);
    s.insert(4);
    cout << "The multiset elements are: ";
    for (auto it = s.begin(); it != s.end(); it++)
        cout << *it << " ";
    auto it = s.lower_bound(2);
    cout << "\nThe lower bound of key 2 is ";
    cout << (*it) << endl;
    it = s.lower_bound(3);
    cout << "The lower bound of key 3 is ";
    cout << (*it) << endl;
    it = s.lower_bound(7);
    cout << "The lower bound of key 7 is ";
    cout << (*it) << endl;
    return 0;
}

実行結果

The multiset elements are: 1 1 2 2 4
The lower bound of key 2 is 2
The lower bound of key 3 is 4
The lower bound of key 7 is 5

コードの解説

まず、multiset に 1、2、2、1、4 の5つの整数を挿入しています。重複する要素も許可されるため、コンテナの中身は「1 1 2 2 4」となります。

キーが存在する場合：lower_bound(2)

キーとして 2 を指定すると、2 以上の要素のうち最初のもの、つまり先頭の「2」へのイテレータが返されます。そのため出力は「2」です。

キーが存在しない場合：lower_bound(3)

キーとして 3 を指定すると、3 と等しい要素はコンテナ内に存在しないため、3 より大きい最初の要素である「4」へのイテレータが返されます。

全要素より大きいキーの場合：lower_bound(7)

キーとして 7 を指定すると、7 以上の要素はコンテナ内に存在しません。この場合、end() イテレータ（末尾の次の位置）が返されるため、間接参照すると未定義動作となります。このサンプルでは「5」が出力されていますが、これは実装依存の挙動であり、実務では戻り値が end() と一致していないか必ず確認することが重要です。

まとめ

multiset::lower_bound() を使うことで、ソート済みの状態を保ったまま効率的に対象以上の要素を検索できます。計算量は O(log n) であり、二分探索ベースの高速な処理が可能です。キーの存在有無にかかわらず安全に扱うためには、戻り値のイテレータが end() でないことをチェックする習慣をつけましょう。