home | help 
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 elements
     for which
	the expression is true must precede all elements for which  the  expres-
     sion is false.
	A fully-sorted range meets this criterion.
	2)  Same as (1), but uses r as the source range, as if using ranges::be-
     gin(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 calling
     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 inhib-
     ited.

	In practice, they may be implemented as function objects, or  with  spe-
     cial 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 elements
	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 performed
     are
	logarithmic in the distance between first and last (at most log
	2(last - first) + O(1) comparisons and applications of the  projection).
     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 binary
     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-initializa-
     tion 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 re-
     turn 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	specific
     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)
home | help