From cppreference.com
Defined in header
Call signature
template<std::permutableI,std::sentinel_for<I>S>constexprranges::subrange<I>rotate(Ifirst,Imiddle,Slast); (1) (since C++20)template<ranges::forward_rangeR>requiresstd::permutable<ranges::iterator_t<R>>constexprranges::borrowed_subrange_t<R>rotate(R&&r,ranges::iterator_t<R>middle); (2) (since C++20)template</*execution-policy*/Ep,std::random_access_iteratorI,std::sized_sentinel_for<I>S>requiresstd::permutable<I>ranges::subrange<I>rotate(Ep&&policy,Ifirst,Imiddle,Slast); (3) (since C++26)template</*execution-policy*/Ep,/*sized-random-access-range*/R>requiresstd::permutable<ranges::iterator_t<R>>ranges::borrowed_subrange_t<R>rotaterotate(Ep&&policy,R&&r,ranges::iterator_t<R>middle); (4) (since C++26)For the definition of /*execution-policy*/, see
; for the definition of /*sized-random-access-range*/, see
.
1) Performs a left rotation on the target range [first, last). Elements are swapped in such a way that the elements in [first, middle) are placed after the elements in [middle, last) while the orders of the elements in both ranges are preserved.
2) Same as (1), but uses ranges::begin(r) as first and ranges::end(r) as last.
3) Same as (1), but executed according to policy.
4) Same as (3), but uses ranges::begin(r) as first and ranges::begin(r)+ranges::distance(r) as last.
If [first, middle) or [middle, last) is not a
, the behavior is undefined.
The function-like entities described on this page are
(informally known as niebloids), that is:
Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to
.
When any of them are found by
as the name to the left of the function-call operator,
is inhibited.
Parameters
first, last - the iterator-sentinel pair defining the target
r - the target range middle - the beginning of the part to be moved to the left policy - the
to use Return value
A subrange referring to the part rotated to the right, or:
An empty range, if middle is equal to first.
The entire target range, if middle is equal to last.
Complexity
Given N as ranges::distance(first,last) or ranges::distance(r):
1-4) At most N swaps.
Exceptions
3,4) During the execution process:
If the temporary memory resources required for parallelization are not available,
is thrown.
If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for
,
is invoked).
Notes
ranges::rotate has better efficiency on common implementations if I models
or (better)
.
Implementations (e.g.
) may enable vectorization when the iterator type models
and swapping its value type calls neither non-trivial special member function nor
-found swap.
Possible implementation
See also the implementations in
and
.
structrotate_fn{template<std::permutableI,std::sentinel_for<I>S>constexprranges::subrange<I>operator()(Ifirst,Imiddle,Slast)const{if(first==middle){autolast_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);autolast_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{automid_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_iteratorautonext_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);autonew_first=first;while(middle!=last){// rotate subsequent cyclesnext_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_rangeR>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::next(ranges::begin(r),ranges::end(r)));}};inlineconstexprrotate_fnrotate{};Example
ranges::rotate is a common building block in many algorithms. This example demonstrates
.
Run this code
#include<algorithm>#include<iostream>#include<numeric>#include<string>#include<vector>intmain(){std::strings(16,' ');for(intk{};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(intk{};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(autoi=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): ABCDEFGHIJKLMNOP Rotate left (1): BCDEFGHIJKLMNOPA Rotate left (2): CDEFGHIJKLMNOPAB Rotate left (3): DEFGHIJKLMNOPABC Rotate left (4): EFGHIJKLMNOPABCD Rotate right (0): ABCDEFGHIJKLMNOP Rotate right (1): PABCDEFGHIJKLMNO Rotate right (2): OPABCDEFGHIJKLMN Rotate right (3): NOPABCDEFGHIJKLM Rotate right (4): MNOPABCDEFGHIJKL Insertion sort using “rotate”, step-by-step: i = 0: 2420597371 i = 1: 2420597371 i = 2: 2240597371 i = 3: 0224597371 i = 4: 0224597371 i = 5: 0224597371 i = 6: 0224579371 i = 7: 0223457971 i = 8: 0223457791 i = 9: 0122345779 Sorted! See also