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> |
(1) | (since C++20) |
| template<ranges::forward_range R> requires std::permutable<ranges::iterator_t<R>> |
(2) | (since C++20) |
1) Performs a left rotation on a range of elements. Specifically,
ranges::rotate swaps the elements in the range [first, last) in such a way that the element middle becomes the first element of the new range and middle - 1 becomes the last element. Precondition of this function is that
[first, middle) and [middle, last) are valid ranges.2) Same as (1), but uses
r as the range, as if using ranges::begin(r) as first and ranges::end(r) as last.The function-like entities described on this page are niebloids, that is:
- Explicit template argument lists may not be specified when calling any of them.
- None of them is visible to argument-dependent lookup.
- When one of them is found by normal unqualified lookup for the name to the left of the function-call operator, it inhibits argument-dependent lookup.
In practice, they may be implemented as function objects, or with special compiler extensions.
Contents |
[edit] Parameters
| first, last | - | the range of elements to rotate |
| r | - | the range of elements to rotate |
| middle | - | the element that should appear at the beginning of the rotated range |
[edit] Return value
An object {iter, last}, where iter compares equal to first + (last - middle) and designates a new location of the element pointed by first.
[edit] Complexity
Linear at worst: last - first swaps.
[edit] Notes
The implementations may improves efficiency of rotate algorithm when the input iterators model std::bidirectional_iterator or std::random_access_iterator.
[edit] Possible implementation
struct rotate_fn { template<std::permutable I, std::sentinel_for<I> S> constexpr ranges::subrange<I> operator() ( I first, I middle, S last ) const { auto last2{ ranges::next(first, last) }; auto first2{ ranges::next(first, ranges::distance(middle, last2)) }; if (!(middle == first && middle == last)) { ranges::reverse(first, middle); ranges::reverse(middle, last); ranges::reverse(first, last); } return {std::move(first2), std::move(last2)}; } 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::end(r)); } }; inline constexpr rotate_fn rotate{}; |
[edit] Example
The rotate algorithm can be used as a common building block in many other algorithms, e.g. 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 << "\n" "Insertion 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!
[edit] See also
| (C++20) |
copies and rotate a range of elements (niebloid) |
| (C++20) |
reverses the order of elements in a range (niebloid) |
| rotates the order of elements in a range (function template) |
