Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

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) (const-
       expr 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 ele-
       ments in
	  [middle, last) while the orders of the elements in both  ranges  are
       preserved.
	  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 un-
       defined:

	    * [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
       rotated 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
       errors 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::termi-
       nate is called.
	      For any other ExecutionPolicy, the behavior  is  implementation-
       defined.
	    *  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 read hits
       last

	      for (ForwardIt read = middle; read != last; ++write, ++read)
	      {
		  if (write == next_read)
		      next_read	= read;	// track where first 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  For-
       wardIt satisfies
	  LegacyBidirectionalIterator or (better) LegacyRandomAccessIterator.

	  Implementations  (e.g.  MSVC	STL) may enable	vectorization when the
       iterator	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  ex-
       ample 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
       Correct behavior
	  LWG 488 C++98	     the new location of the element pointed by	 first
       returned
			     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)

Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::rotate&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>

home | help