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

NAME
     std::rotate - std::rotate

Synopsis
	Defined in header <algorithm>
	template< class ForwardIt >
	ForwardIt  rotate( ForwardIt first, ForwardIt middle,	  (1) (constexpr
     since C++20)
	ForwardIt last );
	template< class ExecutionPolicy, class ForwardIt >

	ForwardIt  rotate(  ExecutionPolicy&&  policy,		     (2)  (since
     C++17)

			  ForwardIt first, ForwardIt middle,
	ForwardIt last );

	1) Performs a left rotation on a range of elements.
	Specifically,  std::rotate swaps the elements in the range [first, last)
     in such a
	way that the elements in [first, middle) are placed after  the	elements
     in
	[middle,  last) while the orders of the elements in both ranges are pre-
     served.
	2) Same as (1), but executed according to policy.
	This overload participates in overload resolution only if

	std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>    is    true.
     (until
										  C++20)
	std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>      is
     true. (since
										  C++20)

	If any of the following conditions is satisfied, the behavior  is  unde-
     fined:

	  * [first, middle) or [middle, last) is not a valid range.

	  * The type of *first is not Swappable.	   (until C++11)
	  * ForwardIt is not ValueSwappable.
	  * The type of *first is not MoveConstructible.   (since C++11)
	  * The type of *first is not MoveAssignable.

Parameters
	first	-  the beginning of the original range
	middle	 -   the  element that should appear at the beginning of the ro-
     tated range
	last	-  the end of the original range
	policy	-  the execution policy to use. See  execution	policy	for  de-
     tails.

Type requirements
	-
	ForwardIt must meet the requirements of LegacyForwardIterator.

Return value
	The iterator to the element originally referenced by *first, i.e. the
	std::distance(middle, last)
	th next iterator of first.

Complexity
	At most std::distance(first, last) swaps.

Exceptions
	The overload with a template parameter named ExecutionPolicy reports er-
     rors as
	follows:

	  *  If  execution of a function invoked as part of the algorithm throws
     an exception
	    and ExecutionPolicy is one of the standard policies,  std::terminate
     is called.
	    For  any  other  ExecutionPolicy, the behavior is implementation-de-
     fined.
	  * If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation
	See also the implementations in libstdc++, libc++, and MSVC STL.

	template<class ForwardIt>
	constexpr // since C++20
	ForwardIt rotate(ForwardIt first, ForwardIt middle, ForwardIt last)
	{
	    if (first == middle)
		return last;

	    if (middle == last)
		return first;

	    ForwardIt write = first;
	    ForwardIt next_read = first; // read position for when  areada  hits
     alasta

	    for (ForwardIt read = middle; read != last; ++write, ++read)
	    {
		if (write == next_read)
		    next_read = read; // track where afirsta went
		std::iter_swap(write, read);
	    }

	    // rotate the remaining sequence into place
	    rotate(write, next_read, last);
	    return write;
	}

Notes
	std::rotate has better efficiency on common implementations if ForwardIt
     satisfies
	LegacyBidirectionalIterator or (better) LegacyRandomAccessIterator.

	Implementations (e.g. MSVC STL) may enable vectorization when the itera-
     tor type
	satisfies  LegacyContiguousIterator  and  swapping  its value type calls
     neither
	non-trivial special member function nor ADL-found swap.

Example
	std::rotate is a common building block in many algorithms. This  example
     demonstrates
	insertion sort.

     // Run this code

      #include <algorithm>
      #include <iostream>
      #include <vector>

      auto print = [](const auto remark, const auto& v)
      {
	  std::cout << remark;
	  for (auto n : v)
	      std::cout << n << ' ';
	  std::cout << '\n';
      };

      int main()
      {
	  std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1};
	  print("before sort:\t\t", v);

	  // insertion sort
	  for (auto i = v.begin(); i != v.end(); ++i)
	      std::rotate(std::upper_bound(v.begin(), i, *i), i, i + 1);
	  print("after sort:\t\t", v);

	  // simple rotation to the left
	  std::rotate(v.begin(), v.begin() + 1, v.end());
	  print("simple rotate left:\t", v);

	  // simple rotation to the right
	  std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());
	  print("simple rotate right:\t", v);
      }

Output:
      before sort:	      2 4 2 0 5 10 7 3 7 1
      after sort:	      0 1 2 2 3 4 5 7 7 10
      simple rotate left:     1 2 2 3 4 5 7 7 10 0
      simple rotate right:    0 1 2 2 3 4 5 7 7 10

	Defect reports

	The  following	behavior-changing  defect  reports were applied retroac-
     tively to
	previously published C++ standards.

	  DR	Applied to		Behavior as published		    Cor-
     rect behavior
	LWG 488 C++98	   the new location of the element pointed by first  re-
     turned
			   was not returned

See also
	rotate_copy    copies and rotate a range of elements
		       (function template)
	ranges::rotate rotates the order of elements in a range
	(C++20)        (niebloid)

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