| 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 | ||
template<std::forward_iterator I,std::sentinel_for<I> S, class Proj=std::identity, | (1) | (since C++20) |
template<std::forward_range R,class Proj=std::identity, std::indirect_strict_weak_order< | (2) | (since C++20) |
Examines the range[first, last) and finds the largest range beginning atfirst in which the elements are sorted in non-descending order.
A sequence is sorted with respect to a comparatorcomp if for any iteratorit pointing to the sequence and any non-negative integern such thatit + n is a valid iterator pointing to an element of the sequence,std::invoke(comp,std::invoke(proj,*(it+ n)),std::invoke(proj,*it)) evaluates tofalse.
The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:
Contents |
| first, last | - | the iterator-sentinel pair defining therange of elements to find its sorted upper bound |
| r | - | the range to find its sorted upper bound |
| comp | - | comparison function to apply to the projected elements |
| proj | - | projection to apply to the elements |
The upper bound of the largest range beginning atfirst in which the elements are sorted in non-descending order. That is, the last iteratorit for which range[first, it) is sorted.
Linear in the distance betweenfirst andlast.
struct is_sorted_until_fn{template<std::forward_iterator I,std::sentinel_for<I> S,class Proj=std::identity,std::indirect_strict_weak_order<std::projected<I, Proj>> Comp=ranges::less>constexpr I operator()(I first, S last, Comp comp={}, Proj proj={})const{if(first== last)return first; for(auto next= first;++next!= last; first= next)if(std::invoke(comp,std::invoke(proj,*next),std::invoke(proj,*first)))return next; return first;} template<ranges::forward_range R,class Proj=std::identity,std::indirect_strict_weak_order< std::projected<ranges::iterator_t<R>, Proj>> Comp=ranges::less>constexprranges::borrowed_iterator_t<R> operator()(R&& r, Comp comp={}, Proj proj={})const{return(*this)(ranges::begin(r),ranges::end(r),std::ref(comp),std::ref(proj));}}; inlineconstexpr is_sorted_until_fn is_sorted_until; |
ranges::is_sorted_until returns an iterator equal tolast for empty ranges and ranges of length one.
#include <array>#include <algorithm>#include <iostream>#include <iterator>#include <random> int main(){std::random_device rd;std::mt19937 g{rd()};std::array nums{3,1,4,1,5,9}; constexprint min_sorted_size=4;int sorted_size=0;do{ std::ranges::shuffle(nums, g);constauto sorted_end= std::ranges::is_sorted_until(nums); sorted_size= std::ranges::distance(nums.begin(), sorted_end); std::ranges::copy(nums,std::ostream_iterator<int>(std::cout," "));std::cout<<" : "<< sorted_size<<" leading sorted element(s)\n";}while(sorted_size< min_sorted_size);}
Possible output:
4 1 9 5 1 3 : 1 leading sorted element(s)4 5 9 3 1 1 : 3 leading sorted element(s)9 3 1 4 5 1 : 1 leading sorted element(s)1 3 5 4 1 9 : 3 leading sorted element(s)5 9 1 1 3 4 : 2 leading sorted element(s)4 9 1 5 1 3 : 2 leading sorted element(s)1 1 4 9 5 3 : 4 leading sorted element(s)
(C++20) | checks whether a range is sorted into ascending order (algorithm function object)[edit] |
(C++11) | finds the largest sorted subrange (function template)[edit] |
