C++ STLのmultimap::upper_bound()関数とは？構文・戻り値・サンプルコードを徹底解説

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

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

multimapは連想コンテナの一種で、mapコンテナとよく似た性質を持っています。キー値とマップ値を組み合わせた要素を、特定の順序で格納することができます。mapとの最大の違いは、同じキーに対して複数の要素を関連付けられるという点です。また、内部のデータは常にキーに基づいて自動的にソートされて管理されます。

multimap::upper_bound()とは？

multimap::upper_bound() は、C++ STLに組み込まれた関数であり、<map> ヘッダーファイル内で定義されています。この関数は、multimapコンテナ内の「上限境界」を指すイテレータを返します。具体的には、指定したキー k よりも後ろに位置すると判断される最初の要素を指すイテレータを返します。

なお、似た関数として lower_bound() がありますが、lower_bound() が「キー以上」の最初の要素を返すのに対し、upper_bound() は「キーより大きい」最初の要素を返すという違いがある点に注意しましょう。

構文

Map_name.upper_bound(key& k);

パラメータ

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

• k − 検索対象となるキーの値です。

戻り値

この関数は、キー k よりも後ろに位置するとみなされる次の要素を指すイテレータを返します。該当する要素が存在しない場合は、end() イテレータが返されます。

基本的な使用例

入力：

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

出力：

c:3

この例では、キー 'b' の upper_bound を求めているため、'b' より大きいキーである 'c' に関連付けられた要素が返されます。

サンプルコード

#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のupper bound
    auto i = mul.upper_bound(1);
    cout << "Upper bound of key 1 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    // キー2のupper bound
    i = mul.upper_bound(2);
    cout << "Upper bound of key 2 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    // キー3のupper bound
    i = mul.upper_bound(3);
    cout << "Upper bound of key 3 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    return 0;
}

実行結果

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

Upper bound of key 1 is: 2 10
Upper bound of key 2 is: 3 40
Upper bound of key 3 is: 4 60

このように、upper_bound() を使うことで、multimap内の重複するキーの中でも、指定したキーを超える最初の要素を効率的に取得できることがわかります。キーごとの範囲検索（例：lower_bound() と upper_bound() を組み合わせた処理）にも活用できるため、ぜひ覚えておきましょう。