| 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 lower_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 lower_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 isnot ordered beforevalue.
Returns the first iteratoriter in If the elementselem of | (until C++20) |
Equivalent tostd::lower_bound(first, last, value,std::less{}). | (since C++20) |
[first, last) wherebool(comp(*iter, value)) isfalse, orlast if no suchiter exists.[first, last) are notpartitioned with respect to the expressionbool(comp(elem, value)), 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) not ordered beforevalue, 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 memberlower_bound functions should be preferred.
See also the implementations inlibstdc++ andlibc++.
| lower_bound (1) |
|---|
template<class ForwardIt,class T=typenamestd::iterator_traits<ForwardIt>::value_type>ForwardIt lower_bound(ForwardIt first, ForwardIt last,const T& value){return std::lower_bound(first, last, value,std::less{});} |
| lower_bound (2) |
template<class ForwardIt,class T=typenamestd::iterator_traits<ForwardIt>::value_type,class Compare>ForwardIt lower_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(*it, value)){ first=++it; count-= step+1;}else count= step;} return first;} |
Althoughstd::lower_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.
Unlikestd::binary_search,std::lower_bound does not requireoperator< orcomp to be asymmetric (i.e.,a< b andb< a always have different results). In fact, it does not even requirevalue<*iter orcomp(value,*iter) to be well-formed for any iteratoriter in[first, last).
| 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<8;++i){// Search for first element x such that i ≤ xauto lower= std::lower_bound(data.begin(), data.end(), i); std::cout<< i<<" ≤ "; lower!= data.end()?std::cout<<*lower<<" at index "<<std::distance(data.begin(), lower):std::cout<<"not found";std::cout<<'\n';} std::vector<PriceInfo> prices{{100.0},{101.5},{102.5},{102.5},{107.3}}; for(constdouble to_find:{102.5,110.2}){auto prc_info= std::lower_bound(prices.begin(), prices.end(), to_find,[](const PriceInfo& info,double value){return info.price< value;}); 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}};auto cmpz=[](CD x, CD y){return x.real()< y.real();};#ifdef __cpp_lib_algorithm_default_value_typeauto it= std::lower_bound(nums.cbegin(), nums.cend(),{2,0}, cmpz);#elseauto it= std::lower_bound(nums.cbegin(), nums.cend(), CD{2,0}, cmpz);#endifassert((*it== CD{2,2}));}
Output:
0 ≤ 1 at index 01 ≤ 1 at index 02 ≤ 2 at index 13 ≤ 4 at index 24 ≤ 4 at index 25 ≤ 5 at index 36 ≤ 6 at index 57 ≤ not found102.5 at index 2110.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\)log(N)+1 comparisons were allowed | corrected to\(\scriptsize \log_{2}(N)+O(1)\)log2(N)+1 |
| LWG 2150 | C++98 | if any iteratoriter exists in[first, last) such thatbool(comp(*iter, value)) isfalse, std::lower_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] | |
| divides a range of elements into two groups (function template)[edit] | |
(C++11) | locates the partition point of a partitioned range (function template)[edit] |
| returns an iterator to the first elementgreater than a certain value (function template)[edit] | |
| returns an iterator to the first elementnot less than the given key (public member function of std::set<Key,Compare,Allocator>)[edit] | |
| returns an iterator to the first elementnot less than the given key (public member function of std::multiset<Key,Compare,Allocator>)[edit] | |
(C++20) | returns an iterator to the first elementnot less than the given value (algorithm function object)[edit] |
