std::ranges::rotate
From cppreference.com
C++
Feature test macros (C++20)
Concepts library (C++20)
Metaprogramming library (C++11)
Ranges library (C++20)
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Algorithm library
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
(C++17)
(C++17) (C++17)(C++17)(C++20)
(C++17)
(C++11)
(until C++17)(C++11)
(C++20)(C++20)
(C++17)
(C++17)
(C++17)
(C++17)
Constrained algorithms
All names in this menu belong to namespace
std::ranges
(C++23)
(C++23)
(C++23)
(C++23)
(C++23)
(C++23)
(C++23)
Defined in header
<algorithm>
Call signature
template< std::permutable I, std::sentinel_for <I> S >
(1)
(since C++20)
constexpr ranges::subrange <I>
template< ranges::forward_range R >
(2)
(since C++20)
requires std::permutable <ranges::iterator_t <R>>
constexpr ranges::borrowed_subrange_t <R>
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. The behavior is undefined if
[first, last) is not a valid range or middle is not in [first, last).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 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.
Contents
[edit] Parameters
first, last
-
the iterator-sentinel pair defining the range of elements to rotate
r
-
the range of elements to rotate
middle
-
the iterator to the element that should appear at the beginning of the rotated range
[edit] Return value
{new_first, last}, where new_first compares equal to ranges::next (first, ranges::distance (middle, last)) and designates a new location of the element pointed by first.
[edit] Complexity
Linear at worst: ranges::distance (first, last) swaps.
[edit] 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.
[edit] 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::end (r)); } }; inline constexpr rotate_fn rotate {};
[edit] 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!