std::lower_bound
ヘッダ <algorithm> で定義 | ||
| (1) | ||
template<class ForwardIt, class T > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value ); | (C++20未満) | |
template<class ForwardIt, class T > constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value ); | (C++20以上) | |
| (2) | ||
template<class ForwardIt, class T, class Compare > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | (C++20未満) | |
template<class ForwardIt, class T, class Compare > constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | (C++20以上) | |
範囲 [first, last) 内の value より小さくない (つまり大きいまたは等しい) 最初の要素を指すイテレータ、またはそのような要素が見つからない場合は last を返します。
範囲 [first, last) は式 element < value または comp(element, value) について分割されていなければなりません。 すなわち、その式が true となるすべての要素が、その式が false となるすべての要素よりも前になければなりません。 完全にソートされた範囲はこの基準を満たします。
1つめのバージョンは要素を比較するために operator< を使用し、2つめのバージョンは指定された比較関数 comp を使用します。
目次 |
[編集]引数
| first, last | - | 調べる部分的に順序付けされた範囲を定義するイテレータ |
| value | - | 要素と比較する値 |
| comp | - | 第1引数が第2引数より小さい (つまり前に順序付けされる) 場合に true を返す二項述語。 述語関数のシグネチャは以下と同等なものであるべきです。 bool pred(const Type1 &a, const Type2 &b); シグネチャが const& を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなならず、値カテゴリに関わらず |
| 型の要件 | ||
-ForwardIt は LegacyForwardIterator の要件を満たさなければなりません。 | ||
-Compare は BinaryPredicate の要件を満たさなければなりません。 Compare を満たす必要はありません。 | ||
[編集]戻り値
value より小さくない最初の要素を指すイテレータ、またはそのような要素が見つからない場合は last。
[編集]計算量
行われる比較の回数は first と last の距離の対数です (多くとも log
2(last - first) + O(1) 回の比較)。 しかし、 LegacyRandomAccessIterator でない場合、イテレータのインクリメント回数は線形になります。
[編集]実装例
| 1つめのバージョン |
|---|
template<class ForwardIt, class T> ForwardIt lower_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(*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;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(*it, value)){ first =++it; count -= step +1;}else count = step;}return first;} |
[編集]例
#include <algorithm>#include <iostream>#include <iterator>#include <vector> template<class ForwardIt, class T, class Compare=std::less<>> ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={}){// ノート: 型 T と ForwardIt が逆参照された後の型は両方とも// Compare で使用される Type1 と Type2 のどちらにも暗黙に変換可能でなければなりません。// これは lower_bound の要件 (上を参照) よりも厳しいです。 first = std::lower_bound(first, last, value, comp);return first != last &&!comp(value, *first)? first : last;} 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, " ")); std::cout<<'\n'; // 古典的な二分探索。 存在する場合のみ値を返します。 data ={1, 2, 4, 6, 9, 10}; auto it = binary_find(data.cbegin(), data.cend(), 4);// もし 5 を検索した場合は end() を返します。 if(it != data.cend())std::cout<<*it <<" found at index "<<std::distance(data.cbegin(), it); return0;}
出力:
4 4 4 4 found at index 2
[編集]欠陥報告
以下の動作変更欠陥報告は以前に発行された C++ 標準に遡って適用されました。
| DR | 適用先 | 発行時の動作 | 正しい動作 |
|---|---|---|---|
| LWG 270 | C++98 | Compare was required to be a strict weak ordering | only a partitioning is needed; heterogeneous comparisons permitted |
[編集]関連項目
| 特定のキーに一致する要素の範囲を返します (関数テンプレート) | |
| 指定範囲の要素を2つのグループに分割します (関数テンプレート) | |
| 指定された値より大きい最初の要素へのイテレータを返します (関数テンプレート) |
