# std::ranges::rotate

From cppreference.com
< cpp‎ | algorithm‎ | ranges

Defined in header `<algorithm>` |  |
Call signature |  |
template< std::permutable I, std::sentinel_for<I> S > constexpr ranges::subrange<I> rotate( I first, I middle, S last ); | (1) | (since C++20)
template< ranges::forward_range R > requires std::permutable<ranges::iterator_t<R>> constexpr ranges::borrowed_subrange_t<R> rotate( R&& r, ranges::iterator_t<R> middle ); | (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.
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.

### Parameters

first, last | - | 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

### 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.

### Complexity

Linear at worst: ranges::distance(first, last) swaps.

### 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`.

### 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 {};

### 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!

### See also

ranges::rotate_copy (C++20) | copies and rotate a range of elements (algorithm function object)
ranges::reverse (C++20) | reverses the order of elements in a range (algorithm function object)
rotate | rotates the order of elements in a range (function template)

Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/ranges/rotate&oldid=151697"