FreeBSD Manual Pages
std::ranges::lower_bound(3) C++ Standard Libary std::ranges::lower_bound(3) NAME std::ranges::lower_bound - std::ranges::lower_bound Synopsis Defined in header <algorithm> Call signature template< std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, (since std::indirect_strict_weak_order C++20) <const T*, std::projected<I, Proj>> Comp = (until ranges::less > C++26) 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 (since <const T*, std::projected<I, Proj>> Comp = C++26) 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 (1) <const T*, (since std::projected<ranges::iterator_t<R>, C++20) Proj>> Comp = (until ranges::less > C++26) constexpr ranges::borrowed_iterator_t<R> lower_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} ); template< ranges::forward_range R, (2) class Proj = std::identity, class T = std::projected_value_t<ranges::iterator_t<R>, Proj> std::indirect_strict_weak_order <const T*, (since std::projected<ranges::iterator_t<R>, C++26) Proj>> Comp = ranges::less > constexpr ranges::borrowed_iterator_t<R> lower_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} ); 1) Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found. The range [first, last) must be partitioned with respect to the expression std::invoke(comp, std::invoke(proj, element), value), i.e., all ele- ments for which the expression is true must precede all elements for which the ex- pression is false. A fully-sorted range meets this criterion. 2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last. The function-like entities described on this page are niebloids, that is: * Explicit template argument lists cannot be specified when call- ing any of them. * None of them are visible to argument-dependent lookup. * When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is in- hibited. In practice, they may be implemented as function objects, or with special compiler extensions. Parameters first, last - iterator-sentinel pair defining the partially-ordered range to examine r - the partially-ordered range to examine value - value to compare the projected elements to comp - comparison predicate to apply to the projected ele- ments proj - projection to apply to the elements Return value Iterator pointing to the first element that is not less than value, or last if no such element is found. Complexity The number of comparisons and applications of the projection per- formed are logarithmic in the distance between first and last (at most log 2(last - first) + O(1) comparisons and applications of the projec- tion). However, for an iterator that does not model random_access_iterator, the number of iterator increments is linear. Notes On a range that's fully sorted (or more generally, partially ordered with respect to value) after projection, std::ranges::lower_bound implements the bi- nary search algorithm. Therefore, std::ranges::binary_search can be implemented in terms of it. Feature-test macro Value Std Feature __cpp_lib_algorithm_default_value_type 202403 (C++26) List-initial- ization for algorithms (1,2) Possible implementation 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; Example // Run this code #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"; // classic binary search, returning a value only if it is present data = {1, 2, 4, 8, 16}; // ^ auto it = binary_find(data.cbegin(), data.cend(), 8); // '5' would return end() if (it != data.cend()) std::cout << *it << " found at index "<< ranges::dis- tance(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})); } Output: found a range [6, 10) = { 4 4 4 4 } 8 found at index 3 See also ranges::equal_range returns range of elements matching a spe- cific key (C++20) (niebloid) ranges::partition divides a range of elements into two groups (C++20) (niebloid) ranges::partition_point locates the partition point of a partitioned range (C++20) (niebloid) ranges::upper_bound returns an iterator to the first element greater than a (C++20) certain value (niebloid) returns an iterator to the first element not less than the lower_bound given value (function template) http://cppreference.com 2024.06.10 std::ranges::lower_bound(3)
NAME | Synopsis | Parameters | Return value | Complexity | Notes | Possible implementation | Example | Output: | See also
Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::ranges::lower_bound&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>