Namespaces
Variants
Views
Actions

std::ranges::rotate

From cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms: std::ranges::copy, std::ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
(C++11)(C++11)(C++11)
(C++17)
Modifying sequence operations
Operations on uninitialized storage
Partitioning operations
Sorting operations
(C++11)
Binary search operations
Set operations (on sorted ranges)
Heap operations
(C++11)
Minimum/maximum operations
(C++11)
(C++17)

Permutations
Numeric operations
C library
 
Constrained algorithms
Non-modifying sequence operations
Modifying sequence operations
Operations on uninitialized storage
Partitioning operations
Sorting operations
Binary search operations
Set operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Permutations
 
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<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.
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:

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<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:

#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

copies and rotate a range of elements
(niebloid) [edit]
reverses the order of elements in a range
(niebloid) [edit]
rotates the order of elements in a range
(function template) [edit]