| Constrained algorithms and algorithms on ranges(C++20) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Constrained algorithms, e.g.ranges::copy,ranges::sort, ... | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Execution policies(C++17) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Numeric operations | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Operations on uninitialized memory | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Defined in header <algorithm> | ||
| (1) | ||
template<class ForwardIt,class T> ForwardIt upper_bound( ForwardIt first, ForwardIt last, | (constexpr since C++20) (until C++26) | |
template<class ForwardIt,class T=typenamestd::iterator_traits <ForwardIt>::value_type> | (since C++26) | |
| (2) | ||
template<class ForwardIt,class T,class Compare> ForwardIt upper_bound( ForwardIt first, ForwardIt last, | (constexpr since C++20) (until C++26) | |
template<class ForwardIt,class T=typenamestd::iterator_traits <ForwardIt>::value_type, | (since C++26) | |
Searches for the first element in the partitioned range[first, last) which is ordered aftervalue.
Returns the first iteratoriter in If the elementselem of | (until C++20) |
Equivalent tostd::upper_bound(first, last, value,std::less{}). | (since C++20) |
[first, last) wherebool(comp(value,*iter)) istrue, orlast if no suchiter exists.[first, last) are notpartitioned with respect to the expressionbool(comp(value, elem)), the behavior is undefined.Contents |
| first, last | - | the pair of iterators defining the partitionedrange of elements to examine |
| value | - | value to compare the elements to |
| comp | - | binary predicate which returns true if the first argument is ordered before the second. The signature of the predicate function should be equivalent to the following: bool pred(const Type1&a,const Type2&b); While the signature does not need to haveconst&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) |
| Type requirements | ||
-ForwardIt must meet the requirements ofLegacyForwardIterator. | ||
-Compare must meet the requirements ofBinaryPredicate. It is not required to satisfyCompare. | ||
Iterator to the first element of the range[first, last) ordered aftervalue, orlast if no such element is found.
Given\(\scriptsize N\)N asstd::distance(first, last):
However, ifForwardIt is not aLegacyRandomAccessIterator, the number of iterator increments is linear in\(\scriptsize N\)N. Notably,std::map,std::multimap,std::set, andstd::multiset iterators are not random access, and so their memberupper_bound functions should be preferred.
See also the implementations inlibstdc++ andlibc++.
| upper_bound (1) |
|---|
template<class ForwardIt,class T=typenamestd::iterator_traits<ForwardIt>::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=typenamestd::iterator_traits<ForwardIt>::value_type,class Compare>ForwardIt upper_bound(ForwardIt first, ForwardIt last,const T& value, Compare comp){ ForwardIt it;typenamestd::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;} |
Althoughstd::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 anyvalue.
For any iteratoriter in[first, last),std::upper_bound requiresvalue<*iter andcomp(value,*iter) to be well-formed, whilestd::lower_bound requires*iter< value andcomp(*iter, value) to be well-formed instead.
| Feature-test macro | Value | Std | Feature |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type | 202403 | (C++26) | List-initialization for algorithms(1,2) |
#include <algorithm>#include <cassert>#include <complex>#include <iostream>#include <vector> struct PriceInfo{double price;}; int main(){conststd::vector<int> data{1,2,4,5,5,6}; for(int i=0; i<7;++i){// Search first element that is greater than iauto upper= std::upper_bound(data.begin(), data.end(), i); std::cout<< i<<" < "; upper!= data.end()?std::cout<<*upper<<" at index "<<std::distance(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_typeauto it= std::upper_bound(nums.cbegin(), nums.cend(),{2,0}, cmpz);#elseauto it= std::upper_bound(nums.cbegin(), nums.cend(), CD{2,0}, cmpz);#endifassert((*it== CD{3,0}));}
Output:
0 < 1 at index 01 < 2 at index 12 < 4 at index 23 < 4 at index 24 < 5 at index 35 < 6 at index 56 < not found 107.3 at index 4110.2 not found
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
| DR | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| LWG 270 | C++98 | Compare was required to satisfyCompare andT was requiredto beLessThanComparable (strict weak ordering required) | only a partitioning is required; heterogeneous comparisons permitted |
| LWG 384 | C++98 | at most\(\scriptsize \log(N)+1\)log2(N)+1 comparisons were allowed | corrected to\(\scriptsize \log_{2}(N)+O(1)\)log2(N)+O(1) |
| LWG 577 | C++98 | last could not be returned | allowed |
| LWG 2150 | C++98 | if any iteratoriter exists in[first, last) such thatbool(comp(value,*iter)) istrue, std::upper_boundcould return any iterator in [iter, last) | no iterator after iter can be returned |
| returns range of elements matching a specific key (function template)[edit] | |
| returns an iterator to the first elementnot less than the given value (function template)[edit] | |
| divides a range of elements into two groups (function template)[edit] | |
(C++11) | locates the partition point of a partitioned range (function template)[edit] |
(C++20) | returns an iterator to the first elementgreater than a certain value (algorithm function object)[edit] |
| returns an iterator to the first elementgreater than the given key (public member function of std::set<Key,Compare,Allocator>)[edit] | |
| returns an iterator to the first elementgreater than the given key (public member function of std::multiset<Key,Compare,Allocator>)[edit] |
