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 を返す二項述語。 述語関数のシグネチャは以下と同等なものであるべきです。
シグネチャが |
| 型の要件 | ||
-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つのグループに分割します (関数テンプレート) |