std::lower_bound
提供: cppreference.com
 | このページは、Google 翻訳を使って英語版から機械翻訳されました。 翻訳には誤りや奇妙な言い回しがあるかもしれません。文章の上にポインタをおくと、元の文章が見れます。誤りを修正して翻訳を改善する手助けをしてください。翻訳についての説明は、ここをクリックしてください。 |
ヘッダ <algorithm> で定義 | ||
template<class ForwardIt, class T > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value ); | (1) | |
template<class ForwardIt, class T, class Compare > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | (2) | |
Returns an iterator pointing to the first element in the range [first, last) that is not less than value. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
目次 |
[編集]パラメータ
| first, last | - | iterators defining the range to examine |
| 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); シグネチャは |
| 型の要件 | ||
-ForwardIt は ForwardIterator の要件を満たさなければなりません。 | ||
[編集]値を返します
Iterator pointing to the first element that is not less than value, or last if no such element is found.
[編集]複雑性
firstlastとの間の距離の対数Original:
Logarithmic in the distance between
first and lastThe text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
You can help to correct and verify the translation. Click here for instructions.
[編集]可能な実装
| 1つめのバージョン |
|---|
template<class ForwardIt, class T> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value){ ForwardIt it;std::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(*it < value){ first =++it; count -= step +1;}else count = step;}return first;} |
| 2つめのバージョン |
template<class ForwardIt, class T, class Compare> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp){ ForwardIt it;std::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(*it, value)), 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
[編集]参照
| 特定のキーに一致する要素の範囲を返します (関数テンプレート) | |
| 指定された値より大きい最初の要素へのイテレータを返します (関数テンプレート) |
