std::ranges::lower_bound

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 lower_bound( I first, S last, const T& value,
                         Comp comp = {}, Proj proj = {} );

template< std::forward_iterator I, std::sentinel_for<I> S,
          class Proj = std::identity,
          class T = std::projected_value_t<I, Proj>,
          std::indirect_strict_weak_order
              <const T*, std::projected<I, Proj>> Comp = ranges::less >
constexpr I lower_bound( I first, S last, const T& value,
                         Comp comp = {}, Proj proj = {} );

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>
    lower_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );

template< ranges::forward_range R,
          class Proj = std::identity,
          class T = std::projected_value_t<ranges::iterator_t<R>, Proj>
          std::indirect_strict_weak_order
              <const T*, std::projected<ranges::iterator_t<R>,
                                        Proj>> Comp = ranges::less >
constexpr ranges::borrowed_iterator_t<R>
    lower_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );

Описанные на этой странице функциональные объекты являются объектами-функциями алгоритмов (неформально известны как niebloids), то есть:

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

Параметры

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

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

Сложность

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

Примечания

На диапазоне, который полностью отсортирован (или, в более общем случае, частично упорядочен относительно value ) после проекции, std::ranges::lower_bound реализует алгоритм двоичного поиска. Следовательно, std::ranges::binary_search может быть реализована с его использованием.

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

struct lower_bound_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity,
             class T = std::projected_value_t<I, Proj>,
             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 = std::ranges::distance(first, last);
        while (count > 0)
        {
            it = first;
            step = count / 2;
            ranges::advance(it, step, last);
            if (comp(std::invoke(proj, *it), value))
            {
                first = ++it;
                count -= step + 1;
            }
            else
                count = step;
        }
        return first;
    }
    template<ranges::forward_range R, class Proj = std::identity,
             class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
             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 lower_bound_fn lower_bound;

Пример

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <iterator>
#include <vector>
namespace ranges = std::ranges;
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 binary_find(I first, S last, const T& value, Comp comp = {}, Proj proj = {})
{
    first = ranges::lower_bound(first, last, value, comp, proj);
    return first != last && !comp(value, proj(*first)) ? first : last;
}
int main()
{
    std::vector data{1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};
    //                                 ^^^^^^^^^^
    auto lower = ranges::lower_bound(data, 4);
    auto upper = ranges::upper_bound(data, 4);
    std::cout << "found a range [" << ranges::distance(data.cbegin(), lower)
              << ", " << ranges::distance(data.cbegin(), upper) << ") = { ";
    ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "}\n";
    // классический бинарный поиск, возвращающий значение только при его наличии
    data = {1, 2, 4, 8, 16};
    //               ^
    auto it = binary_find(data.cbegin(), data.cend(), 8); // '5' вернул бы end()
    if (it != data.cend())
        std::cout << *it << " found at index " << ranges::distance(data.cbegin(), it);
    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}};
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it2 = ranges::lower_bound(nums, {2, 0}, cmpz);
    #else
        auto it2 = ranges::lower_bound(nums, CD{2, 0}, cmpz);
    #endif
    assert((*it2 == CD{2, 2}));
}

found a range [6, 10) = { 4 4 4 4 }
8 found at index 3

См. также