| 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 I1,std::sentinel_for<I1> S1, std::forward_iterator I2,std::sentinel_for<I2> S2, | (1) | (since C++20) |
template<ranges::forward_range R1,ranges::forward_range R2, class Proj1=std::identity,class Proj2=std::identity, | (2) | (since C++20) |
[first1, last1) that makes the rangeequal to[first2, last2) (after application of corresponding projectionsProj1,Proj2, and using the binary predicatePred as a comparator). Otherwise returnsfalse.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 firstrange of elements |
| first2, last2 | - | the iterator-sentinel pair defining the secondrange of elements |
| r1 | - | the firstrange of the elements |
| r2 | - | the secondrange of the elements |
| pred | - | predicate 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 the range[first1, last1) is a permutation of the range[first2, last2).
At most\(\scriptsize \mathcal{O}(N^2)\)O(N2) applications of the predicate and each projection, or exactly\(\scriptsize N\)N if the sequences are already equal, where\(\scriptsize N\)N isranges::distance(first1, last1).However ifranges::distance(first1, last1)!=ranges::distance(first2, last2), no applications of the predicate and projections are made.
Thepermutation relation is anequivalence relation.
Theranges::is_permutation can be used in testing, e.g. to check the correctness of rearranging algorithms such as sorting, shuffling, partitioning. Ifp is an original sequence andq is a "mutated" sequence, thenranges::is_permutation(p, q)==true means thatq consist of "the same" elements (maybe permuted) asp.
struct is_permutation_fn{template<std::forward_iterator I1,std::sentinel_for<I1> S1,std::forward_iterator I2,std::sentinel_for<I2> S2,class Proj1=std::identity,class Proj2=std::identity,std::indirect_equivalence_relation<std::projected<I1, Proj1>, std::projected<I2, Proj2>> Pred=ranges::equal_to>constexprbool operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred={}, Proj1 proj1={}, Proj2 proj2={})const{// skip common prefixauto ret= std::ranges::mismatch(first1, last1, first2, last2,std::ref(pred),std::ref(proj1),std::ref(proj2)); first1= ret.in1, first2= ret.in2; // iterate over the rest, counting how many times each element// from [first1, last1) appears in [first2, last2)for(auto i{first1}; i!= last1;++i){constauto i_proj{std::invoke(proj1,*i)};auto i_cmp=[&]<typename T>(T&& t){returnstd::invoke(pred, i_proj,std::forward<T>(t));}; if(i!=ranges::find_if(first1, i, i_cmp, proj1))continue;// this *i has been checked if(constauto m{ranges::count_if(first2, last2, i_cmp, proj2)}; m==0 or m!=ranges::count_if(i, last1, i_cmp, proj1))returnfalse;}returntrue;} template<ranges::forward_range R1,ranges::forward_range R2,class Proj1=std::identity,class Proj2=std::identity,std::indirect_equivalence_relation< std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>> Pred=ranges::equal_to>constexprbool operator()(R1&& r1, R2&& r2, Pred pred={}, Proj1 proj1={}, Proj2 proj2={})const{return(*this)(ranges::begin(r1),ranges::end(r1),ranges::begin(r2),ranges::end(r2), std::move(pred), std::move(proj1), std::move(proj2));}}; inlineconstexpr is_permutation_fn is_permutation{}; |
#include <algorithm>#include <array>#include <cmath>#include <iostream>#include <ranges> auto& operator<<(auto& os, std::ranges::forward_rangeautoconst& v){ os<<"{ ";for(constauto& e: v) os<< e<<' ';return os<<"}";} int main(){staticconstexprauto r1={1,2,3,4,5};staticconstexprauto r2={3,5,4,1,2};staticconstexprauto r3={3,5,4,1,1}; static_assert( std::ranges::is_permutation(r1, r1)&& std::ranges::is_permutation(r1, r2)&& std::ranges::is_permutation(r2, r1)&& std::ranges::is_permutation(r1.begin(), r1.end(), r2.begin(), r2.end())); std::cout<<std::boolalpha<<"is_permutation("<< r1<<", "<< r2<<"): "<< std::ranges::is_permutation(r1, r2)<<'\n'<<"is_permutation("<< r1<<", "<< r3<<"): "<< std::ranges::is_permutation(r1, r3)<<'\n' <<"is_permutation with custom predicate and projections: "<< std::ranges::is_permutation(std::array{-14,-11,-13,-15,-12},// 1st rangestd::array{'F','E','C','B','D'},// 2nd range[](int x,int y){return abs(x)== abs(y);},// predicate[](int x){return x+10;},// projection for 1st range[](char y){returnint(y-'A');})// projection for 2nd range<<'\n';}
Output:
is_permutation({ 1 2 3 4 5 }, { 3 5 4 1 2 }): trueis_permutation({ 1 2 3 4 5 }, { 3 5 4 1 1 }): falseis_permutation with custom predicate and projections: true(C++20) | generates the next greater lexicographic permutation of a range of elements (algorithm function object)[edit] |
(C++20) | generates the next smaller lexicographic permutation of a range of elements (algorithm function object)[edit] |
(C++11) | determines if a sequence is a permutation of another sequence (function template)[edit] |
| generates the next greater lexicographic permutation of a range of elements (function template)[edit] | |
| generates the next smaller lexicographic permutation of a range of elements (function template)[edit] | |
(C++20) | specifies that arelation imposes an equivalence relation(concept)[edit] |
