home | help 
std::ranges::rotate(3)	       C++ Standard Libary	  std::ranges::rotate(3)

NAME
     std::ranges::rotate - std::ranges::rotate

Synopsis
	Defined in header <algorithm>
	Call signature
	template< std::permutable I, std::sentinel_for<I> S >

	constexpr ranges::subrange<I>			      (1) (since C++20)

	    rotate( I first, I middle, S last );
	template< ranges::forward_range R >

	requires std::permutable<ranges::iterator_t<R>>       (2) (since C++20)
	constexpr ranges::borrowed_subrange_t<R>

	    rotate( R&& r, ranges::iterator_t<R> middle );

	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 el-
     ement *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  mid-
     dle 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 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  inhib-
     ited.

	In  practice,  they may be implemented as function objects, or with spe-
     cial compiler
	extensions.

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  be-
     ginning 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 el-
     ement pointed
	by first.

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

Notes
	ranges::rotate has better efficiency on common implementations if I mod-
     els
	bidirectional_iterator or (better) random_access_iterator.

	Implementations (e.g. MSVC STL) may enable vectorization when the itera-
     tor 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 exam-
     ple
	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 copies and rotate a range of elements
	(C++20) 	    (niebloid)
	ranges::reverse     reverses the order of elements in a range
	(C++20) 	    (niebloid)
	rotate		    rotates the order of elements in a range
			    (function template)

http://cppreference.com 	   2024.06.10		  std::ranges::rotate(3)
home | help