std::ranges::upper_bound

Определено в заголовке <algorithm>

Вызов сигнатуры

Определено в заголовке `<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)
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)

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)

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)

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

2) То же, что и (1), но использует r в качестве исходного диапазона, как если бы использовалось ranges::begin(r) как first и ranges::end(r) как last.

Функциональные сущности, описанные на этой странице, являются ниблоидами, то есть:

Явные списки шаблонов аргументов не могут быть указаны при вызове любого из них.
Ни один из них не виден для поиска аргументов по имени.
При обнаружении любого из них с помощью обычного безусловного поиска в качестве имени слева от оператора вызова функции поиск аргументов по имени заблокирован.

На практике они могут быть реализованы в виде объектов функций или с использованием специальных расширений компилятора.

Параметры

first, last	-	итератор-маркер, определяющий частично упорядоченный диапазон для проверки
r	-	частично упорядоченный диапазон для проверки
value	-	значение для сравнения с элементами
pred	-	предикат для применения к спроецированным элементам
proj	-	проекция для применения к элементам

Возвращаемое значение

Итератор, указывающий на первый элемент, который больше, чем value, или last , если такой элемент не найден.

Сложность

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

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

struct upper_bound_fn
{
    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 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 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>
        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;

Пример

#include <algorithm>
#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';
    }
}

Вывод:

4 4 4 
3 3 3 3

См. также

ranges::equal_range (C++20)	возвращает диапазон элементов, соответствующих определенному ключу (ниблоид)
ranges::lower_bound (C++20)	возвращает итератор на первый элемент, который не меньше заданного значения (ниблоид)
ranges::partition (C++20)	разделяет диапазон элементов на две группы (ниблоид)
upper_bound	возвращает итератор на первый элемент, больше определенного значения (шаблон функции)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/upper_bound