std::ranges::upper_bound
Определён в заголовочном файле <algorithm> | ||
|---|---|---|
| Сигнатура вызова | ||
template< std::forward_iterator I, std::sentinel_for<I> S,
class T, class Proj = std::identity,
std::indirect_strict_weak_order
<const T*, std::projected<I, Proj>> Comp = ranges::less >
constexpr I upper_bound( I first, S last, const T& value,
Comp comp = {}, Proj proj = {} );
| (1) |
(начиная с C++20) (до C++26) |
template< std::forward_iterator I, std::sentinel_for<I> S,
class Proj = std::identity,
class T = std::projected_value_t<I, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<I, Proj>> Comp = ranges::less >
constexpr I upper_bound( I first, S last, const T& value,
Comp comp = {}, Proj proj = {} );
| (начиная с C++26) | |
template< ranges::forward_range R,
class T, class Proj = std::identity,
std::indirect_strict_weak_order
<const T*, std::projected<ranges::iterator_t<R>,
Proj>> Comp = ranges::less >
constexpr ranges::borrowed_iterator_t<R>
upper_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
| (2) |
(начиная с C++20) (до C++26) |
template< ranges::forward_range R,
class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<ranges::iterator_t<R>,
Proj>> Comp = ranges::less >
constexpr ranges::borrowed_iterator_t<R>
upper_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
| (начиная с C++26) |
[first, last), который больше value, или last, если такой элемент не найден. Диапазон [first, last) должен быть разбит на группы относительно выражения или !comp(value, element), то есть все элементы, для которых выражение имеет значение true, должны предшествовать всем элементам, для которых выражение имеет значение false. Полностью отсортированный диапазон удовлетворяет этому критерию.r, как если бы ranges::begin(r) использовался в качестве first, а ranges::end(r) — в качестве last.Описанные на этой странице функциональные объекты являются функциональными объектами алгоритмов (неофициально называемыми ниблоидами
Параметры
first, last - пара итератора и сентинела, задающая частично упорядоченный диапазон элементов для проверки
r - частично упорядоченный диапазон для проверки
value - значение для сравнения с элементами
pred - предикат, применяемый к спроецированным элементам
proj - проекция, применяемая к элементам
Возвращаемое значение
Итератор, указывающий на первый элемент, который больше value, или last, если такой элемент не найден.
Сложность
Количество сравнений и применений проекции логарифмически зависит от расстояния между first и last (не более log2(last - first) + O(1) сравнений и применений проекции). Однако для итератора, который не моделирует random_access_iterator, количество его инкрементов линейно.
Возможная реализация
struct upper_bound_fn
{
template<std::forward_iterator I, std::sentinel_for<I> S,
class Proj = std::identity, class T = std::projected_value_t<I, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<I, Proj>> Comp = ranges::less>
constexpr I operator()(I first, S last, const T& value,
Comp comp = {}, Proj proj = {}) const
{
I it;
std::iter_difference_t<I> count, step;
count = ranges::distance(first, last);
while (count > 0)
{
it = first;
step = count / 2;
ranges::advance(it, step, last);
if (!comp(value, std::invoke(proj, *it)))
{
first = ++it;
count -= step + 1;
}
else
count = step;
}
return first;
}
template<ranges::forward_range R, class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<ranges::iterator_t<R>,
Proj>> Comp = ranges::less>
constexpr ranges::borrowed_iterator_t<R>
operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
{
return (*this)(ranges::begin(r), ranges::end(r), value,
std::ref(comp), std::ref(proj));
}
};
inline constexpr upper_bound_fn upper_bound;
|
Примечания
| Макрос проверки поддержки возможностей | Значение | Стандарт | Возможность |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type | 202403 | (C++26) | Инициализация списком для алгоритмов (1,2) |
Пример
#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
namespace ranges = std::ranges;
std::vector<int> data{1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};
{
auto lower = ranges::lower_bound(data.begin(), data.end(), 4);
auto upper = ranges::upper_bound(data.begin(), data.end(), 4);
ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}
{
auto lower = ranges::lower_bound(data, 3);
auto upper = ranges::upper_bound(data, 3);
ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}
using CD = std::complex<double>;
std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
#ifdef __cpp_lib_algorithm_default_value_type
auto it = ranges::upper_bound(nums, {2, 0}, cmpz);
#else
auto it = ranges::upper_bound(nums, CD{2, 0}, cmpz);
#endif
assert((*it == CD{3, 0}));
}
Вывод:
4 4 4 3 3 3 3
См. также
|
(C++20) | находит диапазон элементов, соответствующих заданному значению, с помощью двоичного поиска (функциональный объект алгоритма) |
|
(C++20) | находит с помощью двоичного поиска первый элемент, не меньший заданного значения (функциональный объект алгоритма) |
|
(C++20) | разделяет диапазон элементов на две группы (функциональный объект алгоритма) |
| находит с помощью двоичного поиска первый элемент, больший заданного значения (шаблон функции) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges/upper_bound
