Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help 
std::ranges::upper_bound(3)   C++ Standard Libary  std::ranges::upper_bound(3)

NAME
       std::ranges::upper_bound	- std::ranges::upper_bound

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<
	  const								   T*,
       (1) (since C++20)
	  std::projected<I, Proj>> Comp	= ranges::less >
	  constexpr I

	  upper_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*,
       (2) (since C++20)
	  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	= {}
	  );

	  1)  Returns  an  iterator pointing to	the first element in the range
       [first, last) that
	  is greater than value, or last if no	such  element  is  found.  The
       range [first, last)
	  must	be  partitioned	with respect to	the expression or !comp(value,
       element), i.e.,
	  all elements for which the expression	is true	must precede all  ele-
       ments for which
	  the expression 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 may not be specified when call-
       ing any of them.
	    * None of them is visible to argument-dependent lookup.
	    *  When  one of them is found by normal unqualified	lookup for the
       name to the left
	      of the function-call operator,  it  inhibits  argument-dependent
       lookup.

	  In  practice,	 they  may be implemented as function objects, or with
       special compiler
	  extensions.

Parameters
	  first, last -	iterator-sentinel defining the partially-ordered range
       to examine
	  r	      -	the partially-ordered range to examine
	  value	      -	value to compare the elements to
	  pred	      -	predicate to apply to the projected elements
	  proj	      -	projection to apply to the elements

Return value
	  Iterator pointing to the first element that is greater  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.

Possible implementation
	  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::iden-
       tity,
		     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;

Example
       // Run this code

	#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_itera-
       tor<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_itera-
       tor<int>(std::cout, " "));
		std::cout << '\n';
	    }
	}

Output:
	4 4 4
	3 3 3 3

See also
	  ranges::equal_range returns range of elements	 matching  a  specific
       key
	  (C++20)	      (niebloid)
	  ranges::lower_bound  returns	an  iterator  to the first element not
       less than the given
	  (C++20)	      value
			      (niebloid)
	  ranges::partition   divides a	range of elements into two groups
	  (C++20)	      (niebloid)
			      returns an iterator to the first element greater
       than a certain
	  upper_bound	      value
			      (function	template)

http://cppreference.com		  2022.07.31	   std::ranges::upper_bound(3)

Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::ranges::upper_bound&sektion=3&manpath=FreeBSD+Ports+15.0>

home | help