From cppreference.com
Defined in header
Call signature
template<std::forward_iteratorI,std::sentinel_for<I>S,classT,classProj=std::identity,std::indirect_strict_weak_order<constT*,std::projected<I,Proj>>Comp=ranges::less>constexprIupper_bound(Ifirst,Slast,constT&value,Compcomp={},Projproj={}); (1)(since C++20)
(until C++26)template<std::forward_iteratorI,std::sentinel_for<I>S,classProj=std::identity,classT=std::projected_value_t<I,Proj>,std::indirect_strict_weak_order<constT*,std::projected<I,Proj>>Comp=ranges::less>constexprIupper_bound(Ifirst,Slast,constT&value,Compcomp={},Projproj={});(since C++26)template<ranges::forward_rangeR,classT,classProj=std::identity,std::indirect_strict_weak_order<constT*,std::projected<ranges::iterator_t<R>,Proj>>Comp=ranges::less>constexprranges::borrowed_iterator_t<R>upper_bound(R&&r,constT&value,Compcomp={},Projproj={}); (2)(since C++20)
(until C++26)template<ranges::forward_rangeR,classProj=std::identity,classT=std::projected_value_t<ranges::iterator_t<R>,Proj>,std::indirect_strict_weak_order<constT*,std::projected<ranges::iterator_t<R>,Proj>>Comp=ranges::less>constexprranges::borrowed_iterator_t<R>upper_bound(R&&r,constT&value,Compcomp={},Projproj={});(since C++26)Searches for the first element (projected by proj) in the partitioned source range [first, last) or r which is ordered after value with the comparator comp (i.e. value is ordered before that projected element).
If the elements e of the source range are not partitioned with respect to the expression !bool(std::invoke(comp,value,std::invoke(proj,e))), the behavior is undefined.
The function-like entities described on this page are
(informally known as niebloids), that is:
Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to
.
When any of them are found by
as the name to the left of the function-call operator,
is inhibited.
Parameters
first, last - the iterator-sentinel pair defining the source
r - the source range value - the value to be compared with the (projected) elements comp - the comparator to be applied to the (projected) elements proj - the projection to be applied to the elements Return value
Iterator to the first element which is ordered after value, or the past-the-end iterator of the source range if no such element is found.
Complexity
Given N as ranges::distance(first,last) or ranges::distance(r):
1,2) At most log2(N)+𝓞(1) applications of comp and proj.
Notes
macroValueStdFeature
__cpp_lib_algorithm_default_value_type
(C++26)
for algorithms (
)Possible implementation
structupper_bound_fn{template<std::forward_iteratorI,std::sentinel_for<I>S,classProj=std::identity,classT=std::projected_value_t<I,Proj>,std::indirect_strict_weak_order<constT*,std::projected<I,Proj>>Comp=ranges::less>constexprIoperator()(Ifirst,Slast,constT&value,Compcomp={},Projproj={})const{Iit;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;}elsecount=step;}returnfirst;}template<ranges::forward_rangeR,classProj=std::identity,classT=std::projected_value_t<ranges::iterator_t<R>,Proj>,std::indirect_strict_weak_order<constT*,std::projected<ranges::iterator_t<R>,Proj>>Comp=ranges::less>constexprranges::borrowed_iterator_t<R>operator()(R&&r,constT&value,Compcomp={},Projproj={})const{return(*this)(ranges::begin(r),ranges::next(ranges::begin(r),ranges::end(r)),value,std::ref(comp),std::ref(proj));}};inlineconstexprupper_bound_fnupper_bound;Example
Run this code
#include<algorithm>#include<cassert>#include<complex>#include<iostream>#include<iterator>#include<vector>intmain(){namespaceranges=std::ranges;std::vector<int>data{1,1,2,3,3,3,3,4,4,4,5,5,6};{autolower=ranges::lower_bound(data.begin(),data.end(),4);autoupper=ranges::upper_bound(data.begin(),data.end(),4);ranges::copy(lower,upper,std::ostream_iterator<int>(std::cout," "));std::cout<<'\n';}{autolower=ranges::lower_bound(data,3);autoupper=ranges::upper_bound(data,3);ranges::copy(lower,upper,std::ostream_iterator<int>(std::cout," "));std::cout<<'\n';}usingCD=std::complex<double>;std::vector<CD>nums{{1,0},{2,2},{2,1},{3,0},{3,1}};autocmpz=[](CDx,CDy){returnx.real()<y.real();};#ifdef __cpp_lib_algorithm_default_value_typeautoit=ranges::upper_bound(nums,{2,0},cmpz);#elseautoit=ranges::upper_bound(nums,CD{2,0},cmpz);#endifassert((*it==CD{3,0}));}Output:
4 4 4 3 3 3 3 See also
finds the first element greater than the given value using binary search
(function template)
(C++20)
finds the range of elements matching the given value using binary search
(algorithm function object)
(C++20)
finds the first element not less than the given value using binary search
(algorithm function object)
(C++20)
divides a range of elements into two groups
(algorithm function object)