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 >
	  void	 rotate(   ForwardIt   first,	ForwardIt  n_first,  ForwardIt
       (until C++11)
	  last );
	  template<		 class		     ForwardIt		     >
       (since C++11)
	  ForwardIt    rotate(	  ForwardIt    first,	 ForwardIt    n_first,
       (until C++20)
	  ForwardIt last );
	  template< class ForwardIt >					 (1)
	  constexpr   ForwardIt	   rotate(    ForwardIt	   first,    ForwardIt
       (since C++20)
	  n_first, ForwardIt last );
	  template< class ExecutionPolicy, class ForwardIt >

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

	  ForwardIt first, ForwardIt n_first, 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  element n_first becomes the first element of the new
       range and n_first
	  - 1 becomes the last element.
	  A precondition  of  this  function  is  that	[first,	 n_first)  and
       [n_first, last) are
	  valid	ranges.
	  2) Same as (1), but executed according to policy. This overload does
       not participate
	  in overload resolution unless
	  std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
	  (until C++20)
	  std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
	  (since C++20)	is true.

Parameters
	  first		  -	  the beginning	of the original	range
	  n_first	  -	  the element that should appear at the	begin-
       ning of the
				  rotated range
	  last		  -	  the end of the original range
	  policy	   -	    the	execution policy to use. See execution
       policy for
				  details.

Type requirements
	  -
	  ForwardIt must meet the requirements of ValueSwappable  and  Legacy-
       ForwardIterator.
	  -
	  The  type  of	 dereferenced  ForwardIt must meet the requirements of
       MoveAssignable and
	  MoveConstructible.

Return value
	  (none)
       (until C++11)
	  Iterator to the new location of the element pointed by first.	 Equal
       to (since C++11)
	  first	+ (last	- n_first)

Complexity
	  Linear in the	distance between first and last.

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.

Notes
	  std::rotate has better efficiency on common implementations if  For-
       wardIt statisfies
	  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.

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

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

	     ForwardIt read	 = n_first;
	     ForwardIt write	 = first;
	     ForwardIt next_read = first; // read  position  for  when	"read"
       hits "last"

	     while(read	!= last) {
		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;
	  }

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

       // Run this code

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

	auto print = [](auto const& remark, auto const&	v) {
	    std::cout << remark;
	    for	(int 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

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		  2022.07.31			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.0>

home | help