std::rotate
| Defined in header <algorithm>
|
||
template< class ForwardIt >
ForwardIt rotate( ForwardIt first, ForwardIt middle, ForwardIt last );
|
(1) | (constexpr since C++20) |
template< class ExecutionPolicy, class ForwardIt >
ForwardIt rotate( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt middle, ForwardIt last );
|
(2) | (since C++17) |
[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.policy.true:
|
|
(until C++20) |
|
|
(since C++20) |
If any of the following conditions is satisfied, the behavior is undefined:
[first,middle)or[middle,last)is not a valid range.
|
(until C++11) |
|
(since C++11) |
Parameters
| first, last | - | the pair of iterators defining the target range |
| middle | - | the beginning of the part to be moved to the left |
| policy | - | the execution policy to use |
| Type requirements | ||
-ForwardIt must meet the requirements of LegacyForwardIterator.
| ||
Return value
The iterator to the element originally pointed to by first, or last if middle is equal to first.
Complexity
At most std::distance(first, last) swaps.
Exceptions
- 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
std::rotate has better efficiency on common implementations if ForwardIt satisfies LegacyBidirectionalIterator or (better) LegacyRandomAccessIterator.
Implementations (e.g. MSVC STL) may enable vectorization when the iterator type satisfies LegacyContiguousIterator and swapping its value type calls neither non-trivial special member function nor ADL-found swap.
Possible implementation
See also the implementations in libstdc++, libc++, and MSVC STL.
template<class ForwardIt>
constexpr // since C++20
ForwardIt rotate(ForwardIt first, ForwardIt middle, ForwardIt last)
{
if (first == middle)
return last;
if (middle == last)
return first;
ForwardIt write = first;
ForwardIt next_read = first; // read position for when read hits last
for (ForwardIt read = middle; read != last; ++write, ++read)
{
if (write == next_read)
next_read = read; // track where first went
std::iter_swap(write, read);
}
// rotate the remaining sequence into place
rotate(write, next_read, last);
return write;
}
|
Example
std::rotate is a common building block in many algorithms. This example demonstrates insertion sort.
#include <algorithm>
#include <print>
#include <string_view>
#include <vector>
template<typename ForwardIt>
void rotate_left(ForwardIt it_begin, ForwardIt it_end, std::size_t offset)
{
std::rotate(it_begin, it_begin + offset, it_end);
}
template<typename ForwardIt>
void rotate_right(ForwardIt it_begin, ForwardIt it_end, std::size_t offset)
{
std::rotate(it_begin, it_end - offset, it_end);
}
int main()
{
constexpr std::string_view fmt = "{:21}{}\n";
std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1};
std::print(fmt, "before sort:", v);
// insertion sort
for (auto it = v.begin(); it != v.end(); ++it)
rotate_right(std::upper_bound(v.begin(), it, *it), it + 1, 1);
std::print(fmt, "after sort:", v);
// simple rotation to the left
rotate_left(v.begin(), v.end(), 1);
std::print(fmt, "simple rotate left:", v);
// simple rotation to the right
rotate_right(v.begin(), v.end(), 1);
std::print(fmt, "simple rotate right:", v);
}
Output:
before sort: [2, 4, 2, 0, 5, 10, 7, 3, 7, 1]
after sort: [0, 1, 2, 2, 3, 4, 5, 7, 7, 10]
simple rotate left: [1, 2, 2, 3, 4, 5, 7, 7, 10, 0]
simple rotate right: [0, 1, 2, 2, 3, 4, 5, 7, 7, 10]
Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
| DR | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| LWG 488 | C++98 | the new location of the element pointed by first was not returned
|
returned |
See also
(C++20) |
rotates the order of elements in a range (algorithm function object) |
| copies and rotate a range of elements (function template & algorithm function object) | |
(C++20) |