【C++ STL】multisetのupper_bound()関数を実行例付きで解説

本記事では、C++ STLにおけるmultisetコンテナのupper_bound()関数について、具体的なコード例と実行結果をもとに分かりやすく解説します。

upper_bound()関数とは

multisetのupper_bound()は、引数として渡した値より大きい要素のうち、最初に現れるものを指すイテレータを返すメンバ関数です。もしコンテナ内にそのような要素が存在しない場合は、コンテナの末尾（end()）を指すイテレータを返します。

multisetは重複した値を許容する連想コンテナであり、内部では常に要素がソートされた状態で保持されます。そのため、upper_bound()による検索は二分探索に基づいており、O(log n)の計算量で効率的に実行できます。

サンプルコード

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

実行結果

The multiset elements are: 1 3 3 4 5
The upper bound of key 3 is 4
The upper bound of key 2 is 3
The upper bound of key 10 is 5

実行結果の詳細解説

このプログラムでは、multisetに1、3、3、5、4の順で値を挿入しています。multisetは自動的にソートを行うため、格納後の要素は「1 3 3 4 5」となり、重複値の3が2つ含まれている点に注目してください。

キー3を指定した場合

upper_bound(3)は「3より大きい最初の要素」を探します。重複している2つの3の直後にある4が該当するため、それを指すイテレータが返されます。

キー2を指定した場合

upper_bound(2)は「2より大きい最初の要素」を探します。この場合、先頭側の3が該当し、そのイテレータが返されます。

キー10を指定した場合

10より大きい要素はコンテナ内に存在しないため、関数はend()（末尾）を指すイテレータを返します。上記の出力ではたまたま5が表示されていますが、これはend()イテレータのデリファレンスであり、厳密には未定義動作を伴います。

実際の開発では、戻り値がend()と等しいかどうかを必ず確認してから要素にアクセスするようにしましょう。以下のように記述するのが安全です。

auto it = s.upper_bound(10);
if (it != s.end()) {
   cout << *it << endl;
} else {
   cout << "指定した値より大きい要素は存在しません" << endl;
}

まとめ

multiset::upper_bound()は、指定した値より大きい最初の要素を効率的に検索できる便利な関数です。ただし、該当要素が存在しない場合はend()イテレータが返されるため、参照前に必ず範囲チェックを行うことが重要です。lower_bound()との違いも押さえておくと、集合系コンテナの操作がさらに使いやすくなります。