GeezerVison is showing cpprefjp.github.io — std::upper_bound - cpprefjp C++日本語リファレンス
最終更新日時:
2026年08月25日 12時11分17秒 (JST)
Akira Takahashi
が更新
function template
<algorithm>
std:: upper_bound
namespace std {
template < class ForwardIterator ,
class T >
ForwardIterator
upper_bound ( ForwardIterator first ,
ForwardIterator last ,
const T & value ); // (1) C++98
template < class ForwardIterator ,
class T >
constexpr ForwardIterator
upper_bound ( ForwardIterator first ,
ForwardIterator last ,
const T & value ); // (1) C++20
template < class ForwardIterator ,
class T = typename iterator_traits < ForwardIterator >:: value_type >
constexpr ForwardIterator
upper_bound ( ForwardIterator first ,
ForwardIterator last ,
const T & value ); // (1) C++26
template < class ForwardIterator ,
class T ,
class Compare >
ForwardIterator
upper_bound ( ForwardIterator first ,
ForwardIterator last ,
const T & value ,
Compare comp ); // (2) C++98
template < class ForwardIterator ,
class T ,
class Compare >
constexpr ForwardIterator
upper_bound ( ForwardIterator first ,
ForwardIterator last ,
const T & value ,
Compare comp ); // (2) C++20
template < class ForwardIterator ,
class T = typename iterator_traits < ForwardIterator >:: value_type ,
class Compare >
constexpr ForwardIterator
upper_bound ( ForwardIterator first ,
ForwardIterator last ,
const T & value ,
Compare comp ); // (2) C++26
}
概要
イテレータ範囲[first, last)のうち、指定された要素より大きい値が現れる最初の位置のイテレータを取得する
要件
C++98 まで
first、last は前方向イテレータの要件を満たすこと。comp は 2 引数の関数オブジェクトで、結果の型は bool 型に変換可能であること。また、引数に非 const の関数を適用しないこと。T は LessThanComparable であること。operator< または comp は「狭義の弱順序 」であること。イテレータ範囲 [first, last) は operator< または comp を基準として昇順に並んでいること。
C++11 から
first、last は前方向イテレータの要件を満たすこと。comp は 2 引数の関数オブジェクトで、結果の型は bool 型に変換可能であること。また、引数に非 const の関数を適用しないこと。イテレータ範囲[first,last) の要素 e は !(value < e) または !comp(value, e) によって区分化 されていること。!(value < e) または !comp(value, e) が true となる全ての要素 e は、false となる全ての要素よりも左側（first に近い方）になければならない。
戻り値
[first, last] 内のイテレータ i のうち、以下の条件を満たす、最も右側（first から遠い方）のもの。
[first, i) 内の全てのイテレータ j が !(value < *j) または comp(value, *j) == false である。
（つまり、value より大きい要素のうち最初のものを指すイテレータ。value より大きい要素が無ければ last）
計算量
最大で log2(last - first) + O(1) 回の比較を行う
備考
本関数は、本質的に C++11 で追加された partition_point partition_point (first, last, [value](const T& e) { return !bool(value < e); })partition_point (first, last, [value, comp](const T& e) { return !bool(comp(value, e)); })
本関数の要件は、上記の通り C++98 までの方が C++11 よりも厳しい。
(1), (2) :
C++26 : 引数として波カッコ初期化{}を受け付ける
例
基本的な使い方
#include <iostream>
#include <vector>
#include <algorithm>
struct X {
int key ; // プライマリキー
int value ; // 補助的な値
bool operator < ( const X & rhs ) const {
// 型Xはプライマリキーでのみ順序付けされる。
return key < rhs . key ;
}
};
void push_stable ( std::vector < X >& queue , X elem )
{
// 挿入対象の値 elem よりも大きい要素の位置、すなわち
// elem と同値な要素グループの次の位置を検索する。
auto it = std::upper_bound ( queue . begin (), queue . end (), elem );
queue . insert ( it , elem );
}
int main ()
{
// この関数単体としての使い方
{
// upper_bound で 3 より大きい要素の位置を検索する場合、
// 3 以下の物と 3 より大きい物がその順に並んでいれば、
// 必ずしもソートされている必要はない。
std::vector < int > v = { 3 , 1 , 4 , 6 , 5 };
// 3より大きい要素を二分探索で検索
decltype ( v ) :: iterator it = std::upper_bound ( v.begin() , v.end() , 3 );
std::cout << * it << std::endl ;
}
// 応用例：安定順序・優先順位付きキューの実装
{
std::vector < X > queue ;
push_stable ( queue , { 100 , 1 });
push_stable ( queue , { 200 , 1 });
push_stable ( queue , { 300 , 1 });
push_stable ( queue , { 300 , 2 });
push_stable ( queue , { 200 , 2 });
push_stable ( queue , { 100 , 2 });
// プライマリキー key は同値だが異なる値 value を持つ要素間では
// キュー queue への要素挿入順序が維持されている。
// （std::priority_queue クラスでは挿入順序は保持されない。）
for ( const auto & e : queue ) {
std::cout << e . key << ':' << e . value << ' ' ;
}
std::cout << std::endl ;
}
}
出力
4
100:1 100:2 200:1 200:2 300:1 300:2
波カッコ初期化を入力として使用する (C++26)
#include <algorithm>
#include <iostream>
#include <vector>
struct Point {
int x ;
int y ;
bool operator == ( const Point & other ) const = default ;
auto operator <=> ( const Point & other ) const = default ;
};
int main () {
std::vector < Point > v = {
{ 1 , 2 },
{ 3 , 4 },
{ 3 , 4 },
{ 5 , 6 },
};
// 値{3, 4}が見つかる範囲を取得
auto first = std::lower_bound ( v.begin() , v.end() , { 3 , 4 });
auto last = std::upper_bound ( v.begin() , v.end() , { 3 , 4 });
if ( first != v.end() && last != v.end() ) {
while ( first != last ) {
std::cout << first -> x << "," << first -> y << std::endl ;
++ first ;
}
}
}
出力
3,4
3,4
実装例
template < class ForwardIterator , class T , class Compare >
ForwardIterator
upper_bound ( ForwardIterator first , ForwardIterator last , const T & value , Compare comp )
{
using diff = typename std::iterator_traits < ForwardIterator >:: difference_type ;
for ( diff len = std::distance ( first , last ); len != 0 ; ) {
diff half = len / 2 ;
ForwardIterator mid = first ;
std::advance ( mid , half );
if ( ! bool ( comp ( value , * mid ))) {
len -= half + 1 ;
first = ++ mid ;
} else {
len = half ;
}
}
return first ;
}
// operator< 用の関数オブジェクト
struct less_inner {
template < class T , class U >
bool operator ()( const T & lhs , const U & rhs ) { return bool ( lhs < rhs ); }
};
template < class ForwardIterator , class T >
ForwardIterator
upper_bound ( ForwardIterator first , ForwardIterator last , const T & value )
{
return std :: upper_bound ( first , last , value , less_inner ());
}
関連項目
参照