std::upper_bound
Объявление
<tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody>| Определено в заголовочном файле <algorithm>
|
||
| (1) | ||
template< class ForwardIt, class T > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value ); |
(constexpr начиная с C++20) (до C++26) |
|
template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value ); |
(начиная с C++26) | |
| (2) | ||
template< class ForwardIt, class T, class Compare > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); |
(constexpr начиная с C++20) (до C++26) |
|
template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type, class Compare > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); |
(начиная с C++26) | |
Описание
Возвращает минимальную (первую) позицию элемента входящего в диапазон [first, last) и имеющего значение больше чем value. Возвращает last, если такого элемента нет в диапазоне.
См. Диапазоны См. #Постусловия. Если диапазон не частично упорядочен относительно value, то поведение не определено. См. #Предусловия.
operator<. Вариант эквивалентен std::upper_bound(first, last, value, std::less{}) (начиная с C++20).Параметры
[first, last)
|
— | два итератора задающих диапазон элементов (частично упорядоченных) |
value
|
— | Значение для сравнения с элементами в диапазоне |
comp
|
— | объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true, если первый аргумент "меньше", чем второй.Определение сравнения должно быть эквивалентно:
Использование |
| Требования к типам | ||
-ForwardIterator.
| ||
-BinaryPredicate. It is not required to satisfy Compare.
| ||
Возвращаемое значение
итератор диапазона [first, last), указывающий на первый элемент со значением больше чем value, или last (если такой элемент не найден).
Предусловия
[[assume( (std::forward_iterator<ForwardIt>)&& //См. [[#Параметры]] (std::binary_predicate<Compare>)&& (!comp(value,value))&& (std::is_partitioned(first,last,std::bind(comp,value))) )]];
Предусловия comp, std::bind и std::is_partitioned тоже должны выполняться.
Возможное предусловие [[assume(std::is_sorted(first,last,comp))]] достаточно, но избыточно.
Постусловия
auto result=std::upper_bound(first,last,comp);
[[assume((result==last)||(comp(value,*result)))]]
[[assume((result==first)||(!comp(value,*std::prev(result))))]]
[[assume(!(std::distance(first ,result)<0))]]
[[assume(!(std::distance(result, last)<0))]]
Предусловия std::upper_bound тоже выполняются.
Исключения
Обеспечивает наивысшую гарантию обработки исключений, но не выше чем Compare и чем ForwardIt.
| Этот раздел не завершён Причина: Не откорректирована формулировка |
Сложность
Память=O(1)+O()+O()
Время=log
2()+O(1) сравнений элементов.
Однако если ForwardIt не LegacyRandomAccessIterator, то время линейно зависит от std::distance(first, last). Например, итераторы в std::map, std::multimap, std::set, и std::multiset не являются LegacyRandomAccessIterator, поэтому вместо std::upper_bound используйте аналогичные функции соответствующих контейнеров.
Заметки
Хотя std::upper_bound требует на диапазоне [first, last) только лишь частичного разбиения предикатом std::bind(comp,value), этот алгоритм обычно используется в случаях, когда [first, last) полностью отсортирован, поэтому бинарный поиск допустим для любого значения.
Для любого итератора iter в [first, last) std::upper_bound требует, чтобы value < *iter и\или comp(value, *iter) были правильно сформированы, в то время как std::lower_bound требует, чтобы вместо этого были правильно сформированы *iter < value и comp(*iter, value).
Возможная реализация
| Первый вариант |
|---|
template<
class ForwardIt
,class T //= typename std::iterator_traits<ForwardIt>::value_type
,class Compare //= typename std::less<T>
>//constexpr
ForwardIt upper_bound (
ForwardIt first, ForwardIt last
,T const& value
,Compare comp = std::less<T>()
)
{
typedef typename std::iterator_traits<ForwardIt>::distance_type dist; //use auto
for(dist count = std::distance (first,last); !(count==0); ) {
dist step( count / 2 );
ForwardIt it( first );
std::advance (it, step);
if ( comp (value,*it) ) count = step;
else {
first = ++it; //first = std::next(it);
count = count - step - 1;
}
return first;
}
|
| Второй вариант |
template<class ForwardIt, class T, class Compare>
ForwardIt upper_bound(ForwardIt first, ForwardIt last,
const T& value, Compare comp)
{
ForwardIt it;
std::iterator_traits<ForwardIt>::distance_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
Defect reports
Следующие изменения поведения были применены с обратной силой к ранее опубликованным стандартам C++:
| Номер | Применён | Поведение в стандарте | Корректное поведение |
|---|---|---|---|
| LWG 270 | C++98 | Compare was required to satisfy Compare and T was requiredto be LessThanComparable (strict weak ordering required) |
only a partitioning is required; heterogeneous comparisons permitted |
| LWG 384 | C++98 | at most log 2(N)+1 comparisons were allowed |
corrected to log 2(N)+O(1) |
| LWG 577 | C++98 | last could not be returned
|
allowed |
| LWG 2150 | C++98 | if any iterator iter exists in [first, last) such thatbool(comp(value, *iter)) is true, std::lower_boundcould return any iterator in [iter, last)
|
no iterator afteriter can be returned
|
См. также
(C++20) |
возвращает итератор на первый элемент, который больше определённого значения (ниблоид) |
| возвращает итератор на первый элемент больший, чем заданный ключ (public функция-элемент std::set)
| |
| возвращает итератор на первый элемент больший, чем заданный ключ (public функция-элемент std::multiset)
| |
| возвращает итератор на первый элемент больший, чем заданный ключ (public функция-элемент std::map)
| |
| возвращает итератор на первый элемент больший, чем заданный ключ (public функция-элемент std::multimap)
| |
| возвращает итератор на первый элемент не меньший, чем заданное значение (шаблон функции) | |
| определяет, существует ли элемент в частично упорядоченном диапазоне (шаблон функции) | |
| ищет диапазон элементов (шаблон функции) | |
| возвращает диапазон элементов, соответствующих определённому ключу (шаблон функции) | |
| сортирует диапазон в порядке возрастания (шаблон функции) | |
(C++11) |
проверяет, отсортирован ли диапазон по возрастанию (шаблон функции) |
| делит диапазон элементов на две группы (шаблон функции) | |
(C++11) |
определяет, разделён ли диапазон заданным предикатом (шаблон функции) |
(C++11) |
находит точку раздела разделённого на две группы диапазона (шаблон функции) |