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; typename 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; typename 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; } |
[編集] 例
#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); return 0; }
出力:
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つのグループに分割します (関数テンプレート) | |
| 指定された値より大きい最初の要素へのイテレータを返します (関数テンプレート) |
