GeezerVison is showing cpprefjp.github.io — std::ranges::upper_bound - cpprefjp C++日本語リファレンス
最終更新日時:
2026年09月11日 13時06分31秒 (JST)
Akira Takahashi
が更新
function template
<algorithm>
std::ranges:: upper_bound (C++20)
namespace std :: ranges {
template < forward_iterator I ,
sentinel_for < I > S ,
class T ,
class Proj = identity ,
indirect_strict_weak_order <
const T * ,
projected < I , Proj >
> Comp = ranges::less >
constexpr I
upper_bound ( I first ,
S last ,
const T & value ,
Comp comp = {},
Proj proj = {}); // (1) C++20
template < forward_iterator I ,
sentinel_for < I > S ,
class Proj = identity ,
class T = projected_value_t < I , Proj > ,
indirect_strict_weak_order <
const T * ,
projected < I , Proj >
> Comp = ranges::less >
constexpr I
upper_bound ( I first ,
S last ,
const T & value ,
Comp comp = {},
Proj proj = {}); // (1) C++26
template < forward_range R ,
class T ,
class Proj = identity ,
indirect_strict_weak_order <
const T * ,
projected < iterator_t < R > , Proj >
> Comp = ranges::less >
constexpr borrowed_iterator_t < R >
upper_bound ( R && r ,
const T & value ,
Comp comp = {},
Proj proj = {}); // (2) C++20
template < forward_range R ,
class Proj = identity ,
class T = projected_value_t < iterator_t < R > , Proj > ,
indirect_strict_weak_order <
const T * ,
projected < iterator_t < R > , Proj >
> Comp = ranges::less >
constexpr borrowed_iterator_t < R >
upper_bound ( R && r ,
const T & value ,
Comp comp = {},
Proj proj = {}); // (2) C++26
}
概要
指定された要素より大きい値が現れる最初の位置のイテレータを取得する
(1): イテレータ範囲を指定する
(2): Rangeを直接指定する
事前条件
[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) 回の比較を行う
備考
本関数は、本質的に 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)); })
(1), (2) :
C++26 : 引数として波カッコ初期化{}を受け付ける
std::vector < T > v ;
auto it = std :: ranges :: upper_bound ( v , { a , b });
例
基本的な使い方
#include <iostream>
#include <vector>
#include <algorithm>
struct X {
int key ; // プライマリキー
int value ; // 補助的な値
};
void push_stable ( std::vector < X >& queue , X elem )
{
// 挿入対象の値 elem よりも大きい要素の位置、すなわち
// elem と同値な要素グループの次の位置を検索する。
auto it = std::ranges::upper_bound ( queue , elem . key , {}, & X :: key );
queue . insert ( it , elem );
}
int main ()
{
// この関数単体としての使い方
{
// upper_bound で 3 より大きい要素の位置を検索する場合、
// 3 以下の物と 3 より大きい物がその順に並んでいれば、
// 必ずしもソートされている必要はない。
std::vector < int > v = { 3 , 1 , 4 , 6 , 5 };
// 3より大きい要素を二分探索で検索
auto it = std::ranges::upper_bound ( v , 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>
#include <iterator>
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::ranges::lower_bound ( v , { 3 , 4 });
auto last = std::ranges::upper_bound ( v , { 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
バージョン
言語
処理系
参照