C++ STLのupper_bound()関数とは？使い方とサンプルコードを解説

この記事では、C++ STLにおけるupper_bound()関数について解説します。この関数は、コンテナ内で「valより後」とみなされる最初の要素を指すイテレータを返します。構文は以下の通りです。

iterator upper_bound (const value_type& val);
const_iterator upper_bound (const value_type& val) const;

戻り値はイテレータであり、コンテナ内でvalより後とみなされる最初の要素を指します。なお、upper_bound()はlower_bound()と対になる関数で、lower_bound()が「val以上」の最初の要素を返すのに対し、upper_bound()は「valより大きい」最初の要素を返す点が異なります。

使用例

#include <iostream>
#include <set>
using namespace std;
int main () {
    set<int> myset;
    set<int>::iterator itlow,itup;
    for (int i = 1; i < 10; i++) myset.insert(i*10);
    itup = myset.upper_bound (60);
    myset.erase(itup);
    cout << "myset contains:";
    for (set<int>::iterator it = myset.begin(); it!=myset.end(); ++it)
    cout << ' ' << *it;
}

実行結果

myset contains: 10 20 30 40 50 60 80 90

コードの解説

このサンプルコードでは、まずsetに10から90までの10の倍数を挿入しています。続いてupper_bound(60)を呼び出すことで、60より大きい最初の要素である「70」を指すイテレータを取得し、その要素をerase()で削除しています。

その結果、実行結果の出力には70が含まれておらず、upper_bound()が正しく「指定した値より後の最初の要素」を特定できていることが確認できます。

注意点

upper_bound()を使用する際には、以下の点に注意しましょう。

• 対象のコンテナは、あらかじめソートされた状態（またはsetやmapのような自動的にソートされる連想コンテナ）である必要があります。
• 該当する要素が存在しない場合、戻り値はend()イテレータになります。
• 計算量は二分探索によるもので、要素数をnとするとO(log n)です。