| 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::bidirectional_iterator I,std::sentinel_for<I> S, class Comp=ranges::less,class Proj=std::identity> | (1) | (since C++20) |
template<ranges::bidirectional_range R,class Comp=ranges::less, class Proj=std::identity> | (2) | (since C++20) |
Helper type | ||
template<class I> using next_permutation_result=ranges::in_found_result<I>; | (3) | (since C++20) |
[first, last) into the nextpermutation, where the set of all permutations is orderedlexicographically with respect to binary comparison function objectcomp and projection function objectproj. Returns{last,true} if such a"next permutation" exists; otherwise transforms the range into the lexicographically first permutation as if byranges::sort(first, last, comp, proj), and returns{last,false}.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 topermute |
| r | - | therange of elements topermute |
| comp | - | comparisonFunctionObject which returnstrue if the first argument isless than the second |
| proj | - | projection to apply to the elements |
Any exceptions thrown from iterator operations or the element swap.
At most\(\scriptsize N/2\)N / 2 swaps, where\(\scriptsize N\)N isranges::distance(first, last) in case(1) orranges::distance(r) in case(2). Averaged over the entire sequence of permutations, typical implementations use about 3 comparisons and 1.5 swaps per call.
Implementations (e.g.MSVC STL) may enable vectorization when the iterator type modelscontiguous_iterator and swapping its value type calls neither non-trivial special member function norADL-foundswap.
struct next_permutation_fn{template<std::bidirectional_iterator I,std::sentinel_for<I> S,class Comp=ranges::less,class Proj=std::identity> requiresstd::sortable<I, Comp, Proj>constexpr ranges::next_permutation_result<I> operator()(I first, S last, Comp comp={}, Proj proj={})const{// check that the sequence has at least two elementsif(first== last)return{std::move(first),false}; I i_last{ranges::next(first, last)}; I i{i_last};if(first==--i)return{std::move(i_last),false};// main "permutating" loopfor(;;){ I i1{i};if(std::invoke(comp,std::invoke(proj,*--i),std::invoke(proj,*i1))){ I j{i_last};while(!std::invoke(comp,std::invoke(proj,*i),std::invoke(proj,*--j))){}std::iter_swap(i, j);std::reverse(i1, i_last);return{std::move(i_last),true};}// permutation "space" is exhaustedif(i== first){std::reverse(first, i_last);return{std::move(i_last),false};}}} template<ranges::bidirectional_range R,class Comp=ranges::less,class Proj=std::identity> requiresstd::sortable<ranges::iterator_t<R>, Comp, Proj>constexpr ranges::next_permutation_result<ranges::borrowed_iterator_t<R>> operator()(R&& r, Comp comp={}, Proj proj={})const{return(*this)(ranges::begin(r),ranges::end(r), std::move(comp), std::move(proj));}}; inlineconstexpr next_permutation_fn next_permutation{}; |
#include <algorithm>#include <array>#include <compare>#include <functional>#include <iostream>#include <string> struct S{char c;int i;auto operator<=>(const S&)const=default;friendstd::ostream& operator<<(std::ostream& os,const S& s){return os<<"{'"<< s.c<<"', "<< s.i<<"}";}}; auto print=[](autoconst& v,char term=' '){std::cout<<"{ ";for(constauto& e: v)std::cout<< e<<' ';std::cout<<'}'<< term;}; int main(){std::cout<<"Generate all permutations (iterators case):\n";std::string s{"abc"};do{ print(s);}while(std::ranges::next_permutation(s.begin(), s.end()).found); std::cout<<"\n""Generate all permutations (range case):\n";std::array a{'a','b','c'};do{ print(a);}while(std::ranges::next_permutation(a).found); std::cout<<"\n""Generate all permutations using comparator:\n";usingnamespace std::literals;std::array z{"█"s,"▄"s,"▁"s};do{ print(z);}while(std::ranges::next_permutation(z,std::greater()).found); std::cout<<"\n""Generate all permutations using projection:\n";std::array<S,3> r{S{'A',3}, S{'B',2}, S{'C',1}};do{ print(r,'\n');}while(std::ranges::next_permutation(r,{},&S::c).found);}
Output:
Generate all permutations (iterators case):{ a b c } { a c b } { b a c } { b c a } { c a b } { c b a }Generate all permutations (range case):{ a b c } { a c b } { b a c } { b c a } { c a b } { c b a }Generate all permutations using comparator:{ █ ▄ ▁ } { █ ▁ ▄ } { ▄ █ ▁ } { ▄ ▁ █ } { ▁ █ ▄ } { ▁ ▄ █ }Generate all permutations using projection:{ {'A', 3} {'B', 2} {'C', 1} }{ {'A', 3} {'C', 1} {'B', 2} }{ {'B', 2} {'A', 3} {'C', 1} }{ {'B', 2} {'C', 1} {'A', 3} }{ {'C', 1} {'A', 3} {'B', 2} }{ {'C', 1} {'B', 2} {'A', 3} }(C++20) | generates the next smaller lexicographic permutation of a range of elements (algorithm function object)[edit] |
(C++20) | determines if a sequence is a permutation of another sequence (algorithm function object)[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++11) | determines if a sequence is a permutation of another sequence (function template)[edit] |
