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

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

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

mapは連想コンテナの一種で、キー(key)とマップ値(mapped value)のペアで構成される要素を、特定の順序で格納することができます。mapコンテナ内のデータは、内部で常にキーに基づいて自動的にソートされており、格納された値にはそれぞれ一意のキーを通じてアクセスします。

map::upper_bound()とは?

map::upper_bound()は、C++ STLに組み込まれている関数で、<map>ヘッダーファイル内で定義されています。この関数は、mapコンテナにおける「上限(upper bound)」を指すイテレータを返します。具体的には、検索キーkよりも大きいキーを持つ最初の要素を指すイテレータを返します。

構文

Map_name.upper_bound(key& k);

パラメータ

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

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

戻り値

この関数は、キーkよりも大きいキーを持つ最初の要素(キーkの直後に位置する要素)を指すイテレータを返します。該当する要素が存在しない場合は、end()イテレータを返します。

使用例

入力

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

出力

c:3

サンプルコード

#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.upper_bound(2);
    cout << "The upper bound of key 2 is ";
    cout << i->first << " :" << i->second << endl;
    auto i_1 = TP_Map.upper_bound(3);
    cout << "The upper 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 upper bound of key 2 is 4 :70
The upper bound of key 3 is 4 :70

動作の解説

上記のサンプルコードでは、mapに格納された要素がキーの昇順(1, 2, 4, 5)に自動的にソートされています(出力では逆イテレータを使っているため降順に表示されます)。upper_bound(2)を呼び出すと、キー2より大きい最初の要素であるキー4(値70)を指すイテレータが返されます。同様にupper_bound(3)の場合、キー3自体は存在しませんが、キー3より大きい最初の要素はキー4となるため、同じ結果が返されます。このようにupper_bound()は、二分探索を利用して効率的に「指定キーを超える最初の要素」を検索できる便利な関数です。