[alg.rotate]

# 26 Algorithms library [[algorithms]](./#algorithms)

## 26.7 Mutating sequence operations [[alg.modifying.operations]](alg.modifying.operations#alg.rotate)

### 26.7.11 Rotate [alg.rotate]

[ð](#lib:rotate)

`template<class ForwardIterator>
  constexpr ForwardIterator
    rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
  ForwardIterator
    rotate(ExecutionPolicy&& exec,
           ForwardIterator first, ForwardIterator middle, ForwardIterator last);

template<[permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
  constexpr subrange<I> ranges::rotate(I first, I middle, S last);
template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<I> S>
  requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<I>
  subrange<I> ranges::rotate(Ep&& exec, I first, I middle, S last);
`

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8198)

*Preconditions*: [first, middle) and [middle, last) are valid ranges[.](#1.sentence-1)

For the overloads in namespace std,ForwardIterator meets
the [*Cpp17ValueSwappable*](swappable.requirements#:Cpp17ValueSwappable "16.4.4.3 Swappable requirements [swappable.requirements]") requirements ([[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")), and
the type of *first meets
the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) and[*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements")) requirements[.](#1.sentence-2)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8208)

*Effects*: For each non-negative integer i < (last - first),
places the element from the position first + i into position first + (i + (last - middle)) % (last - first)[.](#2.sentence-1)

[*Note [1](#note-1)*:

This is a left rotate[.](#2.sentence-2)

â *end note*]

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8217)

*Returns*: 

- [(3.1)](#3.1)

  first + (last - middle) for the overloads in namespace std[.](#3.1.sentence-1)

- [(3.2)](#3.2)

  {first + (last - middle), last} for the overload in namespace ranges[.](#3.2.sentence-1)

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8228)

*Complexity*: At most last - first swaps[.](#4.sentence-1)

[ð](#itemdecl:2)

`template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R>
  requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<iterator_t<R>>
  constexpr borrowed_subrange_t<R> ranges::rotate(R&& r, iterator_t<R> middle);
`

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8240)

*Effects*: Equivalent to:return ranges​::​rotate(ranges​::​begin(r), middle, ranges​::​end(r));

[ð](#itemdecl:3)

`template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R>
  requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<iterator_t<R>>
  borrowed_subrange_t<R> ranges::rotate(Ep&& exec, R&& r, iterator_t<R> middle);
`

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8253)

*Effects*: Equivalent to:return ranges::rotate(std::forward<Ep>(exec), ranges::begin(r), middle, ranges::end(r));

[ð](#lib:rotate_copy)

`template<class ForwardIterator, class OutputIterator>
  constexpr OutputIterator
    rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last,
                OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
  ForwardIterator2
    rotate_copy(ExecutionPolicy&& exec,
                ForwardIterator1 first, ForwardIterator1 middle, ForwardIterator1 last,
                ForwardIterator2 result);

  template<[forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_­iterator [iterator.concept.forward]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O>
    requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I, O>
    constexpr ranges::rotate_copy_result<I, O>
      ranges::rotate_copy(I first, I middle, S last, O result);
`

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8280)

Let N be last - first[.](#7.sentence-1)

[8](#8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8283)

*Preconditions*: [first, middle) and [middle, last) are valid ranges[.](#8.sentence-1)

The ranges [first, last) and [result, result + N)
do not overlap[.](#8.sentence-2)

[9](#9)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8289)

*Effects*: Copies the range [first, last) to the range [result, result + N)
such that for each non-negative integer i<N the following assignment takes place:*(result + i) = *(first + (i + (middle - first)) % N)[.](#9.sentence-1)

[10](#10)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8296)

*Returns*: 

- [(10.1)](#10.1)

  result + N for the overloads in namespace std[.](#10.1.sentence-1)

- [(10.2)](#10.2)

  {last, result + N} for the overload in namespace ranges[.](#10.2.sentence-1)

[11](#11)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8305)

*Complexity*: Exactly N assignments[.](#11.sentence-1)

[ð](#itemdecl:5)

`template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<I> S,
         [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") O, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<O> OutS>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I, O>
  ranges::rotate_copy_truncated_result<I, O>
    ranges::rotate_copy(Ep&& exec, I first, I middle, S last, O result, OutS result_last);
`

[12](#12)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8319)

Let M be last - first and N be min(M, result_last - result)[.](#12.sentence-1)

[13](#13)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8323)

*Preconditions*: [first, middle) and [middle, last)
are valid ranges[.](#13.sentence-1)

The ranges [first, last) and [result, result + N)
do not overlap[.](#13.sentence-2)

[14](#14)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8330)

*Effects*: Copies the range [first, last)
to the range [result, result + N)
such that for each non-negative integer i<N the following assignment takes place:*(result + i) = *(first + (i + (middle - first)) % M)[.](#14.sentence-1)

[15](#15)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8338)

*Returns*: 

- [(15.1)](#15.1)

  {middle + N, first, result + N} if N is less than last - middle[.](#15.1.sentence-1)

- [(15.2)](#15.2)

  Otherwise, {last, first + (N + (middle - first)) % M, result + N}[.](#15.2.sentence-1)

[16](#16)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8349)

*Complexity*: Exactly N assignments[.](#16.sentence-1)

[ð](#itemdecl:6)

`template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") O>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<iterator_t<R>, O>
  constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O>
    ranges::rotate_copy(R&& r, iterator_t<R> middle, O result);
`

[17](#17)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8362)

*Effects*: Equivalent to:return ranges::rotate_copy(ranges::begin(r), middle, ranges::end(r), std::move(result));

[ð](#itemdecl:7)

`template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR>
  requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<iterator_t<R>, iterator_t<OutR>>
  ranges::rotate_copy_truncated_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
    ranges::rotate_copy(Ep&& exec, R&& r, iterator_t<R> middle, OutR&& result_r);
`

[18](#18)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8378)

*Effects*: Equivalent to:return ranges::rotate_copy(std::forward<Ep>(exec), ranges::begin(r), middle, ranges::end(r),
 ranges::begin(result_r), ranges::end(result_r));
