std::rotate
From cppreference.com
Defined in header
<algorithm>
|
||
(1) | ||
template< class ForwardIt >
void rotate( ForwardIt first, ForwardIt n_first, ForwardIt last ); |
(until C++11) | |
template< class ForwardIt >
ForwardIt rotate( ForwardIt first, ForwardIt n_first, ForwardIt last ); |
(since C++11) | |
template< class ExecutionPolicy, class ForwardIt >
ForwardIt rotate( ExecutionPolicy&& policy, ForwardIt first, ForwardIt n_first, ForwardIt last ); |
(2) | (since C++17) |
1) Performs a left rotation on a range of elements.
Specifically,
std::rotate
swaps the elements in the range [first, last)
in such a way that the element n_first
becomes the first element of the new range and n_first - 1
becomes the last element.
A precondition of this function is that
[first, n_first)
and [n_first, last)
are valid ranges.
2) Same as (1), but executed according to
policy
. This overload does not participate in overload resolution unless std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true
Contents |
[edit] Parameters
first | - | the beginning of the original range |
n_first | - | the element that should appear at the beginning of the rotated range |
last | - | the end of the original range |
policy | - | the execution policy to use. See execution policy for details. |
Type requirements | ||
-
ForwardIt must meet the requirements of ValueSwappable and ForwardIterator .
|
||
-The type of dereferenced ForwardIt must meet the requirements of MoveAssignable and MoveConstructible .
|
[edit] Return value
(none) |
(until C++11) |
The iterator equal to |
(since C++11) |
[edit] Complexity
Linear in the distance between first
and last
[edit] Exceptions
The overload with a template parameter named ExecutionPolicy
reports errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception,
-
- if
policy
is std::parallel_vector_execution_policy, std::terminate is called - if
policy
is std::sequential_execution_policy or std::parallel_execution_policy, the algorithm exits with an std::exception_list containing all uncaught exceptions. If there was only one uncaught exception, the algorithm may rethrow it without wrapping in std::exception_list. It is unspecified how much work the algorithm will perform before returning after the first exception was encountered. - if
policy
is some other type, the behavior is implementation-defined
- if
- If the algorithm fails to allocate memory (either for itself or to construct an std::exception_list when handling a user exception), std::bad_alloc is thrown.
[edit] Possible implementation
template <class ForwardIt> void rotate(ForwardIt first, ForwardIt n_first, ForwardIt last) { ForwardIt next = n_first; while (first != next) { std::iter_swap(first++, next++); if (next == last) { next = n_first; } else if (first == n_first) { n_first = next; } } } |
This section is incomplete Reason: implement C++11 signature |
[edit] Example
std::rotate
is a common building block in many algorithms. This example demonstrates insertion sort:
Run this code
#include <vector> #include <iostream> #include <algorithm> int main() { std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1}; std::cout << "before sort: "; for (int n: v) std::cout << n << ' '; std::cout << '\n'; // insertion sort for (auto i = v.begin(); i != v.end(); ++i) { std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1); } std::cout << "after sort: "; for (int n: v) std::cout << n << ' '; std::cout << '\n'; // simple rotation to the left std::rotate(v.begin(), v.begin() + 1, v.end()); std::cout << "simple rotate left : "; for (int n: v) std::cout << n << ' '; std::cout << '\n'; // simple rotation to the right std::rotate(v.rbegin(), v.rbegin() + 1, v.rend()); std::cout << "simple rotate right : "; for (int n: v) std::cout << n << ' '; std::cout << '\n'; }
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
[edit] See also
copies and rotate a range of elements (function template) |
|
(parallelism TS)
|
parallelized version of std::rotate (function template) |