std::upper_bound

ヘッダ `<algorithm>` で定義
	(1)
template<class ForwardIt, class T > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );			(C++20未満)
template<class ForwardIt, class T > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );			(C++20以上)
		(2)
template<class ForwardIt, class T, class Compare > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );				(C++20未満)
template<class ForwardIt, class T, class Compare > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );				(C++20以上)

範囲 [first, last) 内の value より大きい最初の要素を指すイテレータ、またはそのような要素が見つからない場合は last を返します。

範囲 [first, last) は式 !(value < element) または !comp(value, element) について分割されていなければなりません。すなわち、その式が true となるすべての要素が、その式が false となるすべての要素よりも前になければなりません。完全にソートされた範囲はこの基準を満たします。

1つめのバージョンは要素の比較に operator< を使用し、2つめのバージョンは指定された比較関数 comp を使用します。

first, last	-	調べる要素の範囲
value	-	要素と比較する値
comp	-	第1引数が第2引数より小さい (つまり前に順序付けされる) 場合に true を返す二項述語。述語関数のシグネチャは以下と同等なものであるべきです。 bool pred(const Type1 &a, const Type2 &b); シグネチャが const& を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなならず、値カテゴリに関わらず `Type1` および `Type2` 型 (およびそれらの const 修飾された型) のすべての値を受理できなければなりません (そのため Type1 & は許されません。また Type1 に対してムーブがコピーと同等でなければ Type1 も許されません(C++11以上))。型 Type1 は、 T 型のオブジェクトから暗黙に変換可能なものでなければなりません。型 Type2 は、 ForwardIt 型のオブジェクトの逆参照から暗黙に変換可能なものでなければなりません。
型の要件
- `ForwardIt` は LegacyForwardIterator の要件を満たさなければなりません。
- `Compare` は BinaryPredicate の要件を満たさなければなりません。 Compare を満たす必要はありません。

[編集]戻り値

value より大きい最初の要素を指すイテレータ、またはそのような要素が見つからない場合は last。

[編集]計算量

行われる比較の回数は first と last の距離の対数です (多くとも $log 2 (last - first) + O(1)$ 回の比較)。しかし、 LegacyRandomAccessIterator でない場合、イテレータのインクリメント回数は線形になります。

[編集]実装例

1つめのバージョン

template<class ForwardIt, class T> ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value){ ForwardIt it;typenamestd::iterator_traits<ForwardIt>::difference_type count, step; count =std::distance(first, last);   while(count >0){ it = first; step = count /2;std::advance(it, step);if(!(value <*it)){ first =++it; count -= step +1;}else count = step;}return first;}

2つめのバージョン

template<class ForwardIt, class T, class Compare> ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp){ ForwardIt it;typenamestd::iterator_traits<ForwardIt>::difference_type count, step; count =std::distance(first, last);   while(count >0){ it = first; step = count /2;std::advance(it, step);if(!comp(value, *it)){ first =++it; count -= step +1;}else count = step;}return first;}

[編集]例

Run this code

#include <algorithm>#include <iostream>#include <iterator>#include <vector>   int main(){std::vector<int> data ={1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};   auto lower =std::lower_bound(data.begin(), data.end(), 4);auto upper = std::upper_bound(data.begin(), data.end(), 4);   std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));}

出力:

4 4 4

[編集]欠陥報告

以下の動作変更欠陥報告は以前に発行された C++ 標準に遡って適用されました。

DR	適用先	発行時の動作	正しい動作
LWG 270	C++98	Compare was required to be a strict weak ordering	only a partitioning is needed; heterogeneous comparisons permitted

[編集]関連項目

equal_range	特定のキーに一致する要素の範囲を返します (関数テンプレート)[edit]
lower_bound	指定された値より小さくない最初の要素を指すイテレータを返します (関数テンプレート)[edit]
partition	指定範囲の要素を2つのグループに分割します (関数テンプレート)[edit]

言語
標準ライブラリヘッダ
フリースタンディング処理系とホスト処理系
名前付き要件
言語サポートライブラリ
コンセプトライブラリ(C++20)
診断ライブラリ
ユーティリティライブラリ
文字列ライブラリ
コンテナライブラリ
イテレータライブラリ
範囲ライブラリ(C++20)
アルゴリズムライブラリ
数値演算ライブラリ
ローカライゼーションライブラリ
入出力ライブラリ
ファイルシステムライブラリ(C++17)
正規表現ライブラリ(C++11)
アトミック操作ライブラリ(C++11)
スレッドサポートライブラリ(C++11)
技術仕様書

cppreference.com

名前空間

変種

表示

操作