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

NAME
     std::upper_bound - std::upper_bound

Synopsis
	Defined in header <algorithm>
	template< class ForwardIt, class T >
							   (constexpr since
	ForwardIt upper_bound( ForwardIt first, 	   C++20)
	ForwardIt last, 				   (until C++26)

			       const T& value );
	template< class ForwardIt, class T =
	typename std::iterator_traits

	 <ForwardIt>::value_type >			   (since C++26)
	constexpr ForwardIt upper_bound( ForwardIt
	first, ForwardIt last,

					 const T&
	value );
	template< class ForwardIt, class T, class
	Compare >				   (1)
									    (con-
     stexpr since
	ForwardIt	     upper_bound(	     ForwardIt		  first,
     C++20)
	ForwardIt last, 						    (un-
     til C++26)

			       const T& value,
	Compare comp );
	template< class ForwardIt, class T =
	typename std::iterator_traits		       (2)

	 <ForwardIt>::value_type,
		  class 		       Compare			       >
     (since C++26)
	constexpr ForwardIt upper_bound( ForwardIt
	first, ForwardIt last,

					 const T&
	value, Compare comp );

	Searches  for  the  first element in the partitioned range [first, last)
     which is
	ordered after value.

	1) The order is determined by operator<:

	Returns the first iterator iter in [first, last) where bool(value <
	*iter) is true, or last if no such iter exists.
									       (un-
     til C++20)
	If the elements elem of [first, last) are not partitioned with respect
	to the expression bool(value < elem), the behavior is undefined.
	Equivalent  to	std::upper_bound(first,   last,   value,   std::less{}).
     (since C++20)

	2) The order is determined by comp:
	Returns  the first iterator iter in [first, last) where bool(comp(value,
     *iter)) is
	true, or last if no such iter exists.
	If the elements elem of [first, last) are not partitioned  with  respect
     to the
	expression bool(comp(value, elem)), the behavior is undefined.

Parameters
	first, last - the partitioned range of elements to examine
	value	    - value to compare the elements to
		      binary  predicate which returns true if the first argument
     is ordered
		      before the second.

		      The signature of the predicate function should be  equiva-
     lent to the
		      following:

		       bool pred(const Type1 &a, const Type2 &b);

	comp	     -	While  the  signature does not need to have const &, the
     function must
		      not modify the objects passed to it and must  be	able  to
     accept all
		      values of type (possibly const) Type1 and Type2 regardless
     of value
		      category (thus, Type1 & is not allowed
		      ,  nor is Type1 unless for Type1 a move is equivalent to a
     copy
		      (since C++11)).
		      The type Type1 must be such that an object of type  T  can
     be implicitly
		      converted  to  Type1.  The type Type2 must be such that an
     object of type
		      ForwardIt can be dereferenced  and  then	implicitly  con-
     verted to Type2.

Type requirements
	-
	ForwardIt must meet the requirements of LegacyForwardIterator.
	-
	Compare  must  meet  the  requirements of BinaryPredicate. It is not re-
     quired to satisfy
	Compare.

Return value
	Iterator to the first element of the range [first, last)  ordered  after
     value, or
	last if no such element is found.

Complexity
	Given \(\scriptsize N\)N as std::distance(first, last):

	1) At most \(\scriptsize \log_{2}(N)+O(1)\)log
	2(N)+O(1) comparisons with value using
	operator<
	(until C++20)
	std::less{}
	(since C++20).
	2) At most \(\scriptsize \log_{2}(N)+O(1)\)log
	2(N)+O(1) applications of the comparator comp.

	However, if ForwardIt is not a LegacyRandomAccessIterator, the number of
     iterator
	increments is linear in \(\scriptsize N\)N. Notably, std::map, std::mul-
     timap,
	std::set,  and	std::multiset  iterators  are  not random access, and so
     their member
	upper_bound functions should be preferred.

Possible implementation
	See also the implementations in libstdc++ and libc++.

					   upper_bound (1)
      template<class ForwardIt, class  T  =  typename  std::iterator_traits<For-
     wardIt>::value_type>
      ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
      {
	  return std::upper_bound(first, last, value, std::less{});
      }
					   upper_bound (2)
      template<class  ForwardIt,  class  T  = typename std::iterator_traits<For-
     wardIt>::value_type,
	       class Compare>
      ForwardIt upper_bound(ForwardIt first, ForwardIt	last,  const  T&  value,
     Compare comp)
      {
	  ForwardIt it;
	  typename std::iterator_traits<ForwardIt>::difference_type count, step;
	  count = std::distance(first, last);

	  while (count > 0)
	  {
	      it = first;
	      step = count / 2;
	      std::advance(it, step);

	      if (!comp(value, *it))
	      {
		  first = ++it;
		  count -= step + 1;
	      }
	      else
		  count = step;
	  }

	  return first;
      }

Notes
	Although std::upper_bound only requires [first, last) to be partitioned,
     this
	algorithm  is usually used in the case where [first, last) is sorted, so
     that the
	binary search is valid for any value.

	For any iterator iter in [first, last), std::upper_bound requires  value
     < *iter and
	comp(value,  *iter)  to  be well-formed, while std::lower_bound requires
     *iter < value
	and comp(*iter, value) to be well-formed instead.

		  Feature-test macro	       Value	Std		 Feature
	__cpp_lib_algorithm_default_value_type 202403  (C++26)	List-initializa-
     tion for
							      algorithms (1,2)

Example
     // Run this code

      #include <algorithm>
      #include <cassert>
      #include <complex>
      #include <iostream>
      #include <vector>

      struct PriceInfo { double price; };

      int main()
      {
	  const std::vector<int> data{1, 2, 4, 5, 5, 6};

	  for (int i = 0; i < 7; ++i)
	  {
	      // Search first element that is greater than i
	      auto upper = std::upper_bound(data.begin(), data.end(), i);

	      std::cout << i << " < ";
	      upper != data.end()
		  ?   std::cout   <<  *upper  <<  "  at  index	"  <<  std::dis-
     tance(data.begin(), upper)
		  : std::cout << "not found";
	      std::cout << '\n';
	  }

	  std::vector<PriceInfo>  prices{{100.0},  {101.5},  {102.5},	{102.5},
     {107.3}};

	  for (double to_find : {102.5, 110.2})
	  {
	      auto  prc_info  =  std::upper_bound(prices.begin(),  prices.end(),
     to_find,
		  [](double value, const PriceInfo& info)
		  {
		      return value < info.price;
		  });

	      prc_info != prices.end()
		  ? std::cout << prc_info->price << " at index " <<  prc_info  -
     prices.begin()
		  : std::cout << to_find << " not found";
	      std::cout << '\n';
	  }

	  using CD = std::complex<double>;
	  std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
	  auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
	  #ifdef __cpp_lib_algorithm_default_value_type
	      auto  it	=  std::upper_bound(nums.cbegin(),  nums.cend(), {2, 0},
     cmpz);
	  #else
	      auto it = std::upper_bound(nums.cbegin(), nums.cend(),  CD{2,  0},
     cmpz);
	  #endif
	  assert((*it == CD{3, 0}));
      }

Output:
      0 < 1 at index 0
      1 < 2 at index 1
      2 < 4 at index 2
      3 < 4 at index 2
      4 < 5 at index 3
      5 < 6 at index 5
      6 < not found
      107.3 at index 4
      110.2 not found

	Defect reports

	The  following	behavior-changing  defect  reports were applied retroac-
     tively to
	previously published C++ standards.

	   DR	 Applied to	 Behavior as published		    Correct  be-
     havior
			    Compare  was required to satisfy only a partitioning
     is required;
	LWG 270  C++98	    Compare and T was required	     heterogeneous  com-
     parisons
			    to be LessThanComparable	    permitted
			    (strict weak ordering required)
			    at	 most	\(\scriptsize		  corrected   to
     \(\scriptsize
	LWG		384		  C++98 		  \log(N)+1\)log
     \log_{2}(N)+O(1)\)log
			    2(N)+1 comparisons were allowed 2(N)+O(1)
	LWG 577  C++98	    last could not be returned	    allowed
			    if any iterator iter exists in
			    [first, last) such that
	LWG 2150 C++98	    bool(comp(value, *iter)) is     no iterator after
			    true, std::lower_bound	    iter can be returned
			    could return any iterator in
			    [iter, last)

See also
	equal_range	    returns range of elements matching a specific key
			    (function template)
			    returns  an  iterator  to the first element not less
     than the given
	lower_bound	    value
			    (function template)
	partition	    divides a range of elements into two groups
			    (function template)
	partition_point     locates the partition point of a partitioned range
	(C++11) 	    (function template)
	ranges::upper_bound returns an iterator to  the  first	element  greater
     than a certain
	(C++20) 	    value
			    (niebloid)
			    returns  an  iterator  to  the first element greater
     than the given
	upper_bound	    key
			    (public member function of	std::set<Key,Compare,Al-
     locator>)

			    returns  an  iterator  to  the first element greater
     than the given
	upper_bound	    key
			    (public member  function  of  std::multiset<Key,Com-
     pare,Allocator>)

http://cppreference.com 	   2024.06.10		     std::upper_bound(3)

home | help