std::rotate
From cppreference.com
Defined in header
<algorithm>
|
||
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) | |
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.
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 |
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] Possible implementation
template <class ForwardIt> ForwardIt 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; } } return next; } |
[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) |