std::upper_bound

template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last,
                                 const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last,
                       const T& value, Compare comp );

template< class ForwardIt, class T, class Compare >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last,
                                 const T& value, Compare comp );

Возвращает итератор, указывающий на первый элемент в диапазоне [first, last) такой, что value < element (или comp(value, element)) является true (т.е., строго больше value), или last , если такой элемент не найден.

Диапазон [first, last) должен быть разбит относительно выражения !(value < element) или !comp(value, element), т. е., все элементы, для которых выражение истинно true, должны предшествовать всем элементам, для которых выражение истинно false. Полностью отсортированный диапазон соответствует этому критерию.

Первый вариант использует оператор < для сравнения элементов, второй вариант использует заданную функцию сравнения comp.

Параметры

Значение результата

Итератор, указывающий на первый элемент в диапазоне [first, last) такой, что value < element (или comp(value, element)) является true, или last , если такой элемент не найден.

Сложность

Количество выполненных сравнений логарифмически зависит от расстояния между first и last (максимум log₂(last - first) + O(1) сравнений).

Однако для не-LegacyRandomAccessIterators количество инкрементов итераторов линейно. Обратите внимание, что std::map, std::multimap, std::set, и std::multiset итераторы не являются случайного доступа, поэтому следует предпочитать их функции-члены upper_bound.

Возможная реализация

См. также реализации в libstdc++ и libc++.

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;
}

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 <vector>
 
struct PriceInfo { double price; };
 
int main()
{
    const std::vector<int> data{1, 2, 4, 5, 5, 6};
 
    for (int i = 0; i < 7; ++i)
    {
        // Search first element that is greater than i
        auto upper = std::upper_bound(data.begin(), data.end(), i);
 
        std::cout << i << " < ";
        upper != data.end()
            ? std::cout << *upper << " at index " << std::distance(data.begin(), upper)
            : std::cout << "not found";
        std::cout << '\n';
    }
 
    std::vector<PriceInfo> prices{{100.0}, {101.5}, {102.5}, {102.5}, {107.3}};
 
    for (double to_find : {102.5, 110.2})
    {
        auto prc_info = std::upper_bound(prices.begin(), prices.end(), to_find,
            [](double value, const PriceInfo& info)
            {
                return value < info.price;
            });
 
        prc_info != prices.end()
            ? std::cout << prc_info->price << " at index " << prc_info - prices.begin()
            : std::cout << to_find << " not found";
        std::cout << '\n';
    }
}

0 < 1 at index 0
1 < 2 at index 1
2 < 4 at index 2
3 < 4 at index 2
4 < 5 at index 3
5 < 6 at index 5
6 < not found 
107.3 at index 4
110.2 not found

Отчеты об ошибках

Следующие отчеты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

См. также