| 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::input_iterator I1,std::sentinel_for<I1> S1, std::input_iterator I2,std::sentinel_for<I2> S2, | (1) | (since C++20) |
template<ranges::input_range R1,ranges::input_range R2, class Proj1=std::identity,class Proj2=std::identity, | (2) | (since C++20) |
[first2, last2) is asubsequence of the projections of the sorted range[first1, last1).Both ranges must be sorted with the given comparison functioncomp. A subsequence need not be contiguous.
The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:
Contents |
| first1, last1 | - | the iterator-sentinel pair defining the sortedrange of elements to examine |
| r1 | - | the sorted range of elements to examine |
| first2, last2 | - | the iterator-sentinel pair defining the sortedrange of elements to search for |
| r2 | - | the sorted range of elements to search for |
| comp | - | comparison function to apply to the projected elements |
| proj1 | - | projection to apply to the elements in the first range |
| proj2 | - | projection to apply to the elements in the second range |
true if[first2, last2) is a subsequence of[first1, last1); otherwisefalse.
At most\(\scriptsize 2 \cdot (N_1+N_2-1)\)2·(N1+N2-1) comparisons, where\(\scriptsize N_1\)N1 isranges::distance(r1) and\(\scriptsize N_2\)N2 isranges::distance(r2).
struct includes_fn{template<std::input_iterator I1,std::sentinel_for<I1> S1,std::input_iterator I2,std::sentinel_for<I2> S2,class Proj1=std::identity,class Proj2=std::identity,std::indirect_strict_weak_order< std::projected<I1, Proj1>, std::projected<I2, Proj2>> Comp=ranges::less>constexprbool operator()(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp={}, Proj1 proj1={}, Proj2 proj2={})const{for(; first2!= last2;++first1){if(first1== last1|| comp(*first2,*first1))returnfalse;if(!comp(*first1,*first2))++first2;}returntrue;} template<ranges::input_range R1,ranges::input_range R2,class Proj1=std::identity,class Proj2=std::identity,std::indirect_strict_weak_order< std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>> Comp=ranges::less>constexprbool operator()(R1&& r1, R2&& r2, Comp comp={}, Proj1 proj1={}, Proj2 proj2={})const{return(*this)(ranges::begin(r1),ranges::end(r1),ranges::begin(r2),ranges::end(r2),std::ref(comp),std::ref(proj1),std::ref(proj2));}}; inlineconstexprauto includes= includes_fn{}; |
#include <algorithm>#include <cctype>#include <initializer_list>#include <iomanip>#include <iostream>#include <locale>#include <string> template<class T>std::ostream& operator<<(std::ostream& os,std::initializer_list<T>const& list){for(os<<"{ ";autoconst& elem: list) os<< elem<<' ';return os<<"} ";} struct true_false:std::numpunct<char>{std::string do_truename()const{return"? Yes\n";}std::string do_falsename()const{return"? No\n";}}; int main(){std::cout.imbue(std::locale(std::cout.getloc(), new true_false)); auto ignore_case=[](char a,char b){returnstd::tolower(a)<std::tolower(b);}; constauto a={'a','b','c'}, b={'a','c'}, c={'a','a','b'}, d={'g'}, e={'a','c','g'}, f={'A','B','C'}, z={'a','b','c','f','h','x'}; std::cout<< z<<"includes\n"<<std::boolalpha<< a<< std::ranges::includes(z.begin(), z.end(), a.begin(), a.end())<< b<< std::ranges::includes(z, b)<< c<< std::ranges::includes(z, c)<< d<< std::ranges::includes(z, d)<< e<< std::ranges::includes(z, e)<< f<< std::ranges::includes(z, f, ignore_case);}
Output:
{ a b c f h x } includes{ a b c } ? Yes{ a c } ? Yes{ a a b } ? No{ g } ? No{ a c g } ? No{ A B C } ? Yes(C++20) | computes the difference between two sets (algorithm function object)[edit] |
(C++20) | searches for the first occurrence of a range of elements (algorithm function object)[edit] |
(C++23)(C++23) | checks if the range contains the given element or subrange (algorithm function object)[edit] |
| returnstrue if one sequence is a subsequence of another (function template)[edit] |
