std::upper_bound

Defined in header `<algorithm>`

template<class ForwardIt, class T > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );	(1)

template<class ForwardIt, class T, class Compare > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)

[first, last)より'大きい範囲value内の最初の要素を指すイテレータを返します。最初のバージョンは、要素を比較するoperator<使用して、2番目のバージョンは、指定された比較関数compを使用しています.
Original:
Returns an iterator pointing to the first element in the range [first, last) that is greater than value. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

first, last	-	検討する要素の範囲 Original: the range of elements to examine The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
value	-	に要素を比較する値 Original: value to compare the elements to The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
comp	-	比較関数. 最初の値が二つ目の値より小さい場合、 trueを返します. 比較関数のシグネチャは以下と同等でなければなりません. bool cmp(const Type1 &a, const Type2 &b); シグネチャは`const`を含まなくても構いませんが, 比較関数は渡されたオブジェクトを変更してはなりません. The type Type1 must be such that an object of type T can be implicitly converted to Type1. The type Type2 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type2.
型の要件
- `ForwardIt` は `ForwardIterator` の要求を満足しなければなりません。

[編集]値を返します

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

[編集]可能な実装

First version

template<class ForwardIt, class T> ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value){ ForwardIt it;std::iterator_traits<ForwardIt>::distance_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;}

Second version

template<class ForwardIt, class T, class Compare> ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp){ ForwardIt it;std::iterator_traits<ForwardIt>::distance_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;}

[編集]例

このコードを実行します

#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

[編集]複雑性

firstlastとの間の距離の対数

[編集]参照


equal_range	特定のキーと一致する要素の範囲を返します Original: returns range of elements matching a specific key The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (関数テンプレート)[edit]

lower_bound	最初の要素を指すイテレータを返す指定した値より小さくない Original: returns an iterator to the first element not less than the given value The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (関数テンプレート)[edit]

Apr	JUN	Aug
	26
2016	2017	2018

言語
コンセプト
ユーティリティライブラリ
ストリングスライブラリ
コンテナライブラリ
アルゴリズムライブラリ
イテレータライブラリ
ニューメリックスライブラリ
入力/出力ライブラリ
ローカライゼーションライブラリ
正規表現ライブラリ(C++11)
アトミック操作ライブラリ(C++11)
スレッドのサポートライブラリ(C++11)

cppreference.com

検索

名前空間

変種

表示

操作