std::ranges::rotate
From cppreference.com
| Defined in header <algorithm>
|
||
| Call signature |
||
template< std::permutable I, std::sentinel_for<I> S >
constexpr ranges::subrange<I>
rotate( I first, I middle, S last );
|
(1) | (since C++20) |
template< ranges::forward_range R >
requires std::permutable<ranges::iterator_t<R>>
constexpr ranges::borrowed_subrange_t<R>
rotate( R&& r, ranges::iterator_t<R> middle );
|
(2) | (since C++20) |
template< /*execution-policy*/ Ep,
std::random_access_iterator I, std::sized_sentinel_for<I> S >
requires std::permutable<I>
ranges::subrange<I>
rotate( Ep&& policy, I first, I middle, S last );
|
(3) | (since C++26) |
template< /*execution-policy*/ Ep, /*sized-random-access-range*/ R >
requires std::permutable<ranges::iterator_t<R>>
ranges::borrowed_subrange_t<R> rotate
rotate( Ep&& policy, R&& r, ranges::iterator_t<R> middle );
|
(4) | (since C++26) |
For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.
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 valid range, the behavior is undefined.
The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:
- Explicit template argument lists cannot be specified when calling any of them.
- None of them are visible to argument-dependent lookup.
- When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.
Parameters
| first, last | - | the iterator-sentinel pair defining the target range |
| r | - | the target range |
| middle | - | the beginning of the part to be moved to the left |
| policy | - | the execution policy to use |
Return value
A subrange referring to the part rotated to the right, or:
- An empty range, if
middleis equal tofirst. - The entire target range, if
middleis equal tolast.
Complexity
Given \(\scriptsize N\)N as ranges::distance(first, last) or ranges::distance(r):
1-4) At most \(\scriptsize N\)N swaps.
Exceptions
3,4) During the execution process:
- If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
- If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).
Notes
ranges::rotate has better efficiency on common implementations if I models bidirectional_iterator or (better) random_access_iterator.
Implementations (e.g. MSVC STL) may enable vectorization when the iterator type models contiguous_iterator and swapping its value type calls neither non-trivial special member function nor ADL-found swap.
Possible implementation
See also the implementations in libstdc++ and MSVC STL.
struct rotate_fn
{
template<std::permutable I, std::sentinel_for<I> S>
constexpr ranges::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)};
if constexpr (std::bidirectional_iterator<I>)
{
ranges::reverse(first, middle);
auto last_it = ranges::next(first, last);
ranges::reverse(middle, last_it);
if constexpr (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)};
else
return {std::move(first), std::move(last_it)};
}
}
else
{ // I is merely a forward_iterator
auto next_it = middle;
do
{ // rotate the first cycle
ranges::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>
requires std::permutable<ranges::iterator_t<R>>
constexpr ranges::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)));
}
};
inline constexpr rotate_fn rotate{};
|
Example
ranges::rotate is a common building block in many algorithms. This example demonstrates insertion sort.
Run this code
#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): 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
| rotates the order of elements in a range (function template) | |
(C++20) |
copies and rotate a range of elements (algorithm function object) |
(C++20) |
reverses the order of elements in a range (algorithm function object) |