| 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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
std::ranges| Non-modifying sequence operations | |||||||||||||||||||||||||||||||||
| Modifying sequence operations | |||||||||||||||||||||||||||||||||
| Partitioning operations | |||||||||||||||||||||||||||||||||
| Sorting operations | |||||||||||||||||||||||||||||||||
| Binary search operations (on sorted ranges) | |||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||
| Set operations (on sorted ranges) | |||||||||||||||||||||||||||||||||
| Heap operations | |||||||||||||||||||||||||||||||||
| Minimum/maximum operations | |||||||||||||||||||||||||||||||||
| Permutation operations | |||||||||||||||||||||||||||||||||
| Fold operations | |||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||
| Operations on uninitialized storage | |||||||||||||||||||||||||||||||||
| Return types | |||||||||||||||||||||||||||||||||
Defined in header <algorithm> | ||
Call signature | ||
| (1) | ||
template<std::forward_iterator I,std::sentinel_for<I> S, class T,class Proj=std::identity, | (since C++20) (until C++26) | |
template<std::forward_iterator I,std::sentinel_for<I> S, class Proj=std::identity, | (since C++26) | |
| (2) | ||
template<ranges::forward_range R, class T,class Proj=std::identity, | (since C++20) (until C++26) | |
template<ranges::forward_range R, class Proj=std::identity, | (since C++26) | |
[first, last) that isnot less than (i.e. greater or equal to)value, orlast if no such element is found.The range[first, last) must be partitioned with respect to the expressionstd::invoke(comp,std::invoke(proj, element), value), i.e., all elements for which the expression istrue must precede all elements for which the expression isfalse. A fully-sorted range meets this criterion.The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:
Contents |
| first, last | - | the iterator-sentinel pair defining the partially-orderedrange of elements to examine |
| r | - | the partially-ordered range to examine |
| value | - | value to compare the projected elements to |
| comp | - | comparison predicate to apply to the projected elements |
| proj | - | projection to apply to the elements |
Iterator pointing to the first element that isnot less thanvalue, orlast if no such element is found.
The number of comparisons and applications of the projection performed are logarithmic in the distance betweenfirst andlast (at mostlog2(last - first) + O(1) comparisons and applications of the projection). However, for an iterator that does not modelrandom_access_iterator, the number of iterator increments is linear.
On a range that's fully sorted (or more generally, partially ordered with respect tovalue) after projection,std::ranges::lower_bound implements the binary search algorithm. Therefore,std::ranges::binary_search can be implemented in terms of it.
| Feature-test macro | Value | Std | Feature |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type | 202403 | (C++26) | List-initialization for algorithms(1,2) |
struct lower_bound_fn{template<std::forward_iterator I,std::sentinel_for<I> S,class Proj=std::identity,class T= std::projected_value_t<I, Proj>,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= std::ranges::distance(first, last); while(count>0){ it= first; step= count/2;ranges::advance(it, step, last);if(comp(std::invoke(proj,*it), value)){ first=++it; count-= step+1;}else count= step;}return first;} template<ranges::forward_range R,class Proj=std::identity,class T= std::projected_value_t<ranges::iterator_t<R>, Proj>,std::indirect_strict_weak_order<const T*, std::projected<ranges::iterator_t<R>, Proj>> Comp=ranges::less>constexprranges::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));}}; inlineconstexpr lower_bound_fn lower_bound; |
#include <algorithm>#include <cassert>#include <complex>#include <iostream>#include <iterator>#include <vector> namespace ranges= std::ranges; 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 binary_find(I first, S last,const T& value, Comp comp={}, Proj proj={}){ first= ranges::lower_bound(first, last, value, comp, proj);return first!= last&&!comp(value, proj(*first))? first: last;} int main(){std::vector data{1,2,2,3,3,3,4,4,4,4,5,5,5,5,5};// ^^^^^^^^^^auto lower= ranges::lower_bound(data,4);auto upper=ranges::upper_bound(data,4); std::cout<<"found a range ["<<ranges::distance(data.cbegin(), lower)<<", "<<ranges::distance(data.cbegin(), upper)<<") = { ";ranges::copy(lower, upper,std::ostream_iterator<int>(std::cout," "));std::cout<<"}\n"; // classic binary search, returning a value only if it is present data={1,2,4,8,16};// ^auto it= binary_find(data.cbegin(), data.cend(),8);// '5' would return end() if(it!= data.cend())std::cout<<*it<<" found at index "<<ranges::distance(data.cbegin(), it); 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 it2= ranges::lower_bound(nums,{2,0}, cmpz);#elseauto it2= ranges::lower_bound(nums, CD{2,0}, cmpz);#endifassert((*it2== CD{2,2}));}
Output:
found a range [6, 10) = { 4 4 4 4 }8 found at index 3(C++20) | returns range of elements matching a specific key (algorithm function object)[edit] |
(C++20) | divides a range of elements into two groups (algorithm function object)[edit] |
(C++20) | locates the partition point of a partitioned range (algorithm function object)[edit] |
(C++20) | returns an iterator to the first elementgreater than a certain value (algorithm function object)[edit] |
| returns an iterator to the first elementnot less than the given value (function template)[edit] |
