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

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

C++ STLにおけるマップ（map）とは？

マップは連想コンテナの一種であり、キー（key）とそのキーに対応する値（mapped value）の組み合わせからなる要素を、特定の順序で格納することができます。マップコンテナ内のデータは、内部的に常に関連付けられたキーに基づいて自動的にソートされており、各要素には一意なキーを通じてアクセスします。

map::lower_bound()とは？

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

構文

Map_name.lower_bound(key& k);

パラメータ

この関数が受け取る引数は1つだけです。

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

戻り値

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

使用例

例1：基本的な使い方

入力

map<char, int> newmap;
newmap['a'] = 1;
newmap['b'] = 2;
newmap['c'] = 3;
newmap.lower_bound('b');

出力

b : 2

この例では、キー「b」以上のキーを持つ最初の要素として「b」自身が該当するため、その要素を指すイテレータが返されます。

例2：実践的なコード例

#include <bits/stdc++.h>
using namespace std;
int main() {
    map<int, int> TP_Map;
    TP_Map.insert({5, 50});
    TP_Map.insert({2, 30});
    TP_Map.insert({1, 10});
    TP_Map.insert({4, 70});
    cout << "\nTP Map is : \n";
    cout << "MAP_KEY\tMAP_ELEMENT\n";
    for (auto i = TP_Map.rbegin(); i != TP_Map.rend(); i++) {
        cout << i->first << "\t" << i->second << endl;
    }
    auto i = TP_Map.lower_bound(2);
    cout << "The lower bound of key 2 is ";
    cout << i->first << ": " << i->second << endl;
    auto i_1 = TP_Map.lower_bound(3);
    cout << "The lower bound of key 3 is ";
    cout << i_1->first << " :" << i_1->second << endl;
    return 0;
}

出力

TP Map is:
MAP_KEY     MAP_ELEMENT
5           50
4           70
2           30
1           10
The lower bound of key 2 is 2 :30
The lower bound of key 3 is 4 :70

このコードでは、リバースイテレータを使ってマップの内容を降順に出力した後、lower_bound()によってキー2とキー3の下限を求めています。キー2を指定した場合は同じキー2の要素（値30）が、キー3を指定した場合は3以上で最小のキーである4の要素（値70）が返されていることが確認できます。

まとめ

map::lower_bound()は、マップがキー順にソートされているという特性を活かした高速な検索手段であり、計算量はO(log n)です。また、似た関数として、指定したキーより大きいキーを持つ最初の要素を返すupper_bound()も用意されています。両者を適切に使い分けることで、範囲検索などの処理を効率的に実装できます。