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 & を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなならず、値カテゴリに関わらず |
| 型の要件 | ||
-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; 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 (!(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; 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(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
[編集] 欠陥報告
以下の動作変更欠陥報告は以前に発行された C++ 標準に遡って適用されました。
| DR | 適用先 | 発行時の動作 | 正しい動作 |
|---|---|---|---|
| LWG 270 | C++98 | Compare was required to be a strict weak ordering | only a partitioning is needed; heterogeneous comparisons permitted |
[編集] 関連項目
| 特定のキーに一致する要素の範囲を返します (関数テンプレート) | |
| 指定された値より小さくない最初の要素を指すイテレータを返します (関数テンプレート) | |
| 指定範囲の要素を2つのグループに分割します (関数テンプレート) |
