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::permutable I,std::sentinel_for<I> S> constexprranges::subrange<I> | (1) | (since C++20) |
template<ranges::forward_range R> requiresstd::permutable<ranges::iterator_t<R>> | (2) | (since C++20) |
ranges::rotate
swaps the elements in the range[
first,
last)
in such a way that the element*middle becomes the first element of the new range and*(middle-1) becomes the last element.[
first,
last)
is not a valid range ormiddle is not in[
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 rotate |
r | - | the range of elements to rotate |
middle | - | the iterator to the element that should appear at the beginning of the rotated range |
{new_first, last}, wherenew_first
compares equal toranges::next(first,ranges::distance(middle, last)) and designates a new location of the element pointed byfirst.
Linear at worst:ranges::distance(first, last) swaps.
ranges::rotate
has better efficiency on common implementations ifI
modelsbidirectional_iterator
or (better)random_access_iterator
.
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
.
See also the implementations inlibstdc++ andMSVC STL.
struct rotate_fn{template<std::permutable I,std::sentinel_for<I> S>constexprranges::subrange<I> operator()(I first, I middle, S last)const{if(first== middle){auto last_it=ranges::next(first, last);return{last_it, last_it};}if(middle== last)return{std::move(first), std::move(middle)}; ifconstexpr(std::bidirectional_iterator<I>){ranges::reverse(first, middle);auto last_it=ranges::next(first, last);ranges::reverse(middle, last_it); ifconstexpr(std::random_access_iterator<I>){ranges::reverse(first, last_it);return{first+(last_it- middle), std::move(last_it)};}else{auto mid_last= last_it;do{ranges::iter_swap(first,--mid_last);++first;}while(first!= middle&& mid_last!= middle);ranges::reverse(first, mid_last); if(first== middle)return{std::move(mid_last), std::move(last_it)};elsereturn{std::move(first), std::move(last_it)};}}else{// I is merely a forward_iteratorauto next_it= middle;do{// rotate the first cycleranges::iter_swap(first, next_it);++first;++next_it;if(first== middle) middle= next_it;}while(next_it!= last); auto new_first= first;while(middle!= last){// rotate subsequent cycles next_it= middle;do{ranges::iter_swap(first, next_it);++first;++next_it;if(first== middle) middle= next_it;}while(next_it!= last);} return{std::move(new_first), std::move(middle)};}} template<ranges::forward_range R> requiresstd::permutable<ranges::iterator_t<R>>constexprranges::borrowed_subrange_t<R> operator()(R&& r,ranges::iterator_t<R> middle)const{return(*this)(ranges::begin(r), std::move(middle),ranges::end(r));}}; inlineconstexpr rotate_fn rotate{}; |
ranges::rotate
is a common building block in many algorithms. This example demonstratesinsertion sort.
#include <algorithm>#include <iostream>#include <numeric>#include <string>#include <vector> int main(){std::string s(16,' '); for(int k{}; k!=5;++k){std::iota(s.begin(), s.end(),'A'); std::ranges::rotate(s, s.begin()+ k);std::cout<<"Rotate left ("<< k<<"): "<< s<<'\n';}std::cout<<'\n'; for(int k{}; k!=5;++k){std::iota(s.begin(), s.end(),'A'); std::ranges::rotate(s, s.end()- k);std::cout<<"Rotate right ("<< k<<"): "<< s<<'\n';} std::cout<<"\nInsertion sort using `rotate`, step-by-step:\n"; s={'2','4','2','0','5','9','7','3','7','1'}; for(auto i= s.begin(); i!= s.end();++i){std::cout<<"i = "<< std::ranges::distance(s.begin(), i)<<": "; std::ranges::rotate(std::ranges::upper_bound(s.begin(), i,*i), i, i+1);std::cout<< s<<'\n';}std::cout<<(std::ranges::is_sorted(s)?"Sorted!":"Not sorted.")<<'\n';}
Output:
Rotate left (0): ABCDEFGHIJKLMNOPRotate left (1): BCDEFGHIJKLMNOPARotate left (2): CDEFGHIJKLMNOPABRotate left (3): DEFGHIJKLMNOPABCRotate left (4): EFGHIJKLMNOPABCD Rotate right (0): ABCDEFGHIJKLMNOPRotate right (1): PABCDEFGHIJKLMNORotate right (2): OPABCDEFGHIJKLMNRotate right (3): NOPABCDEFGHIJKLMRotate right (4): MNOPABCDEFGHIJKL Insertion sort using `rotate`, step-by-step:i = 0: 2420597371i = 1: 2420597371i = 2: 2240597371i = 3: 0224597371i = 4: 0224597371i = 5: 0224597371i = 6: 0224579371i = 7: 0223457971i = 8: 0223457791i = 9: 0122345779Sorted!
(C++20) | copies and rotate a range of elements (algorithm function object)[edit] |
(C++20) | reverses the order of elements in a range (algorithm function object)[edit] |
rotates the order of elements in a range (function template)[edit] |