FreeBSD Manual Pages
std::ranges::binary_search(3) C++ Standard Libarystd::ranges::binary_search(3) NAME std::ranges::binary_search - std::ranges::binary_search Synopsis Defined in header <algorithm> Call signature template< std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, std::indirect_strict_weak_order (since <const T*, std::projected<I, Proj>> Comp = C++20) ranges::less > (until constexpr bool binary_search( I first, S last, const T& C++26) 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 = (since ranges::less > C++26) constexpr bool binary_search( I first, S last, const T& value, Comp comp = {}, Proj proj = {} ); template< ranges::forward_range R, (1) class T, class Proj = std::identity, std::indirect_strict_weak_order <const T*, (since std::projected<ranges::iterator_t<R>, C++20) Proj>> Comp = (until ranges::less > C++26) constexpr bool binary_search( 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 bool binary_search( R&& r, const T& value, Comp comp = {}, Proj proj = {} ); 1) Checks if a projected element equivalent to value appears within the range [first, last). 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. For ranges::binary_search to succeed, the range [first, last) must be at least partially ordered with respect to value, i.e. it must satisfy all of the following requirements: * partitioned with respect to std::invoke(comp, std::invoke(proj, element), value) (that is, all projected elements for which the expression is true precedes all elements for which the expression is false). * partitioned with respect to !std::invoke(comp, value, std::in- voke(proj, element)). * for all elements, if std::invoke(comp, std::invoke(proj, ele- ment), value) is true then !std::invoke(comp, value, std::invoke(proj, element)) is also true. A fully-sorted range meets these criteria. 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 - the range of elements to examine r - the range of elements to examine value - value to compare the elements to comp - comparison function to apply to the projected elements proj - projection to apply to the elements Return value true if an element equal to value is found, false otherwise. Complexity The number of comparisons and projections performed is logarithmic in the distance between first and last (at most log 2(last - first) + O(1) comparisons and projections). However, for iterator-sentinel pair that does not model std::random_access_iterator, number of it- erator increments is linear. Notes std::ranges::binary_search doesn't return an iterator to the found element when an element whose projection equals value is found. If an iterator is desired, std::ranges::lower_bound should be used instead. 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 binary_search_fn { template<std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity, class T = std::pro- jected_value_t<I, Proj>, std::indirect_strict_weak_order <const T*, std::projected<I, Proj>> Comp = ranges::less> constexpr bool operator()(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) const { auto x = ranges::lower_bound(first, last, value, comp, proj); return (!(x == last) && !(std::invoke(comp, value, std::in- voke(proj, *x)))); } 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 bool operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), value, std::move(comp), std::move(proj)); } }; inline constexpr binary_search_fn binary_search; Example // Run this code #include <algorithm> #include <cassert> #include <complex> #include <iostream> #include <ranges> #include <vector> int main() { constexpr static auto haystack = {1, 3, 4, 5, 9}; static_assert(std::ranges::is_sorted(haystack)); for (const int needle : std::views::iota(1) | std::views::take(3)) { std::cout << "Searching for " << needle << ": "; std::ranges::binary_search(haystack, needle) ? std::cout << "found " << needle << '\n' : std::cout << "no dice!\n"; } using CD = std::complex<double>; std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}}; auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); }; #ifdef __cpp_lib_algorithm_default_value_type assert(std::ranges::binary_search(nums, {4, 2}, cmpz)); #else assert(std::ranges::binary_search(nums, CD{4, 2}, cmpz)); #endif } Output: Searching for 1: found 1 Searching for 2: no dice! Searching for 3: found 3 See also ranges::equal_range returns range of elements matching a spe- cific key (C++20) (niebloid) ranges::lower_bound returns an iterator to the first element not less than the (C++20) given value (niebloid) ranges::upper_bound returns an iterator to the first element greater than a (C++20) certain value (niebloid) ranges::contains ranges::contains_subrange checks if the range contains the given el- ement or subrange (C++23) (niebloid) (C++23) determines if an element exists in a par- tially-ordered binary_search range (function template) http://cppreference.com 2024.06.10 std::ranges::binary_search(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::binary_search&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>