std::upper_bound
Актуально для C++23.
#include <algorithm>
Актуально на 2024-03-06.
Define overload #1
template<class ForwardIterator, class Tp> constexpr inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const Tp& value);
Ищет первый элемент в последовательности [first, last], который больше "value".
Последовательность [first, last] должна быть отсортированна в порядке возрастания.
Вернёт итератор на этот элемент или last, если подходящего значения не нашлось.
Для последовательности из итераторов поддерживающих произвольный доступ, cложность алгоритма log 2(n).
Для последовательности из итераторов НЕ поддерживающих произвольный доступ, cложность алгоритма O(n).
Example, possible implementation
Define overload #2
template<class ForwardIterator, class Tp, class Compare>
constexpr ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const Tp& value, Compare comp);
Ищет первый элемент в последовательности [first, last], для которого бинарный предикат comp(value, elem) возвратит false.
Диапазон [first, last] должен быть отсортирован так же, как если бы он был отсортирован с помощью бинарного предиката "comp".
Вернёт итератор на этот элемент или last, если подходящего значения не нашлось.
Для последовательности из итераторов поддерживающих произвольный доступ, cложность алгоритма log 2(n).
Для последовательности из итераторов НЕ поддерживающих произвольный доступ, cложность алгоритма O(n).
Example, possible implementation
Examples
Example 1:
#include <iostream>
#include <algorithm>
int main()
{
auto data = {0, 1, 3, 5, 7, 9};
auto it = std::upper_bound(std::begin(data), std::end(data), 4);
if (it != std::end(data))
{
std::cout << *it << std::endl;
}
return 0;
}
5
Changelog
See also
TODO
This page was last modified on 2024-03-06