std::upper_bound

[править] Объявление

[править] Описание

Возвращает минимальную (первую) позицию элемента входящего в диапазон [first, last) и имеющего значение больше чем value. Возвращает last, если такого элемента нет в диапазоне. См. Диапазоны См. #Постусловия. Если диапазон не частично упорядочен относительно value, то поведение не определено. См. #Предусловия.

[править] Параметры

[править] Возвращаемое значение

итератор диапазона [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(Compare)+O(ForwardIt)
Время=log
2(std::distance(first, last))+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).

[править] Возможная реализация

См. libstdc++ и libc++.

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++:

[править] См. также