C++ STLのmultimap::lower_bound()関数の使い方を徹底解説

本記事では、C++ STLにおける multimap::lower_bound() 関数の動作、構文、および具体的な使用例について詳しく解説します。

C++ STLにおけるmultimapとは?

multimap(マルチマップ)は、mapコンテナとよく似た連想コンテナの一種です。キー(key)と値(mapped value)のペアで構成される要素を、特定の順序で格納することができます。mapとの最大の違いは、同じキーに対して複数の要素を関連付けられるという点です。コンテナ内部のデータは、常にキーに基づいて自動的にソートされて管理されます。

multimap::lower_bound()とは?

multimap::lower_bound() は、C++ STLに組み込まれた関数であり、<map> ヘッダーファイル内で定義されています。この関数は、multimapコンテナにおける「下限(lower bound)」を指すイテレータを返します。具体的には、指定したキー k 以上となる最初の要素を指すイテレータが返されます。

構文

multi.lower_bound(key& k);

パラメータ

この関数が受け取るパラメータは1つだけです。

• k − 検索対象となるキー。

戻り値

この関数は、指定されたキー「k」以上の値を持つ最初の要素を指すイテレータを返します。該当する要素が存在しない場合は、end() イテレータが返されます。

入力例

multimap<char, int> newmap;
newmap.insert(make_pair('a', 1));
newmap.insert(make_pair('b', 2));
newmap.insert(make_pair('c', 3));
newmap.lower_bound(b);

出力

b:2

使用例

次に、実際のコード例を見てみましょう。複数の要素を挿入したmultimapに対して、lower_bound() を呼び出し、その結果を確認します。

#include <bits/stdc++.h>
using namespace std;
int main(){
    // multimapの作成
    multimap<int, int> mul;
    mul.insert({ 2, 10 });
    mul.insert({ 1, 20 });
    mul.insert({ 1, 30 });
    mul.insert({ 3, 40 });
    mul.insert({ 3, 50 });
    mul.insert({ 4, 60 });
    // キー1の下限
    auto i = mul.lower_bound(1);
    cout << "Lower bound of key 1 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    // キー2の下限
    i = mul.lower_bound(2);
    cout << "Lower bound of key 2 is: ";
    cout << (*i).first <<" "<<(*i).second << endl;
    // キー3の下限
    i = mul.lower_bound(3);
    cout << "Lower bound of key 3 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    return 0;
}

出力結果

上記のコードを実行すると、以下の出力が生成されます。

Lower bound of key 1 is: 1 20
Lower bound of key 2 is: 2 10
Lower bound of key 3 is: 3 40

まとめ

multimap::lower_bound() は、指定したキー以上の最初の要素を効率的に検索できる便利な関数です。計算量はO(log n)であり、要素数が多いコンテナでも高速に動作します。同じキーに複数の値が紐づくmultimapの特性を活かした検索処理において、ぜひ活用してみてください。