| 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 prev_permutation_result=ranges::in_found_result<I>; | (3) | (since C++20) |
[first, last) into the previouspermutation, where the set of all permutations is orderedlexicographically with respect to binary comparison function objectcomp and projection function objectproj.ranges::sort(first, last, comp, proj);ranges::reverse(first, last);
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 "permute" |
| r | - | therange of elements to "permute" |
| comp | - | comparisonFunctionObject which returnstrue if the first argument is less 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 prev_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::prev_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};auto i{first};++i;if(i== last)return{std::move(i),false};auto i_last{ranges::next(first, last)}; i= i_last;--i;// main "permutating" loopfor(;;){auto i1{i};--i;if(std::invoke(comp,std::invoke(proj,*i1),std::invoke(proj,*i))){auto j{i_last};while(!std::invoke(comp,std::invoke(proj,*--j),std::invoke(proj,*i)));ranges::iter_swap(i, j);ranges::reverse(i1, last);return{std::move(i_last),true};}// permutation "space" is exhaustedif(i== first){ranges::reverse(first, 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::prev_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 prev_permutation_fn prev_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{"cba"};do print(s);while(std::ranges::prev_permutation(s.begin(), s.end()).found); std::cout<<"\nGenerate all permutations (range case):\n";std::array a{'c','b','a'};do print(a);while(std::ranges::prev_permutation(a).found); std::cout<<"\nGenerate all permutations using comparator:\n";usingnamespace std::literals;std::array z{"▁"s,"▄"s,"█"s};do print(z);while(std::ranges::prev_permutation(z,std::greater()).found); std::cout<<"\nGenerate all permutations using projection:\n";std::array<S,3> r{S{'C',1}, S{'B',2}, S{'A',3}};do print(r,'\n');while(std::ranges::prev_permutation(r,{},&S::c).found);}
Output:
Generate all permutations (iterators case):{ c b a } { c a b } { b c a } { b a c } { a c b } { a b c }Generate all permutations (range case):{ c b a } { c a b } { b c a } { b a c } { a c b } { a b c }Generate all permutations using comparator:{ ▁ ▄ █ } { ▁ █ ▄ } { ▄ ▁ █ } { ▄ █ ▁ } { █ ▁ ▄ } { █ ▄ ▁ }Generate all permutations using projection:{ {'C', 1} {'B', 2} {'A', 3} }{ {'C', 1} {'A', 3} {'B', 2} }{ {'B', 2} {'C', 1} {'A', 3} }{ {'B', 2} {'A', 3} {'C', 1} }{ {'A', 3} {'C', 1} {'B', 2} }{ {'A', 3} {'B', 2} {'C', 1} }(C++20) | generates the next greater 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] |
