std::ranges::rotate_copy() algorithm

od C++20

Simplified

// (1)
constexpr rotate_copy_result<I, O>
    rotate_copy( I first, I middle, S last, O result );

// (2)
constexpr rotate_copy_result<ranges::borrowed_iterator_t<R>, O>
    rotate_copy( R&& r, ranges::iterator_t<R> middle, O result );

The type of arguments are generic and have the following constraints:

• I - std::forward_iterator
• S - std::sentinel_for<I>
• O - std::weakly_incrementable
• R - std::forward_range

Additionally, each overload has the following constraints:

• (1) - std::indirectly_copyable<I, O>
• (2) - std::indirectly_copyable<ranges::iterator_t<R>, O>

Detailed

// (1)
template<
  std::forward_iterator I,
  std::sentinel_for<I> S,
  std::weakly_incrementable O
>
  requires std::indirectly_copyable<I, O>
constexpr rotate_copy_result<I, O>
    rotate_copy( I first, I middle, S last, O result );

// (2)
template<
  ranges::forward_range R,
  std::weakly_incrementable O
>
  requires std::indirectly_copyable<ranges::iterator_t<R>, O>
constexpr rotate_copy_result<ranges::borrowed_iterator_t<R>, O>
    rotate_copy( R&& r, ranges::iterator_t<R> middle, O result );

With the helper types defined as follows:

template< class I, class O >
using rotate_copy_result = in_out_result<I, O>;

• (1) Copies the elements from the source range [first; last), to the destination range beginning at result in such a way, that the element *middle becomes the first element of the destination range and *(middle - 1) becomes the last element.

  The result is that the destination range contains a left rotated copy of the source range.

• (2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

Undefined Behaviour

The behavior is undefined

if either [first; middle) or [middle; last) is not a valid range, or the source and destination ranges overlap.

The function-like entities described on this page are niebloids.

Parameters

first last	The range of elements to copy from.
r	The range of elements to copy from.
result	The beginning of the destination range.
middle	The iterator to the element that should appear at the beginning of the destination range.

Return value

{
  last,
  result + N
}

Where N is ranges::distance(first, last).

Complexity

Exactly ranges::distance(first, last) assignments.

Exceptions

(none)

Possible implementation

rotate_copy(1) and rotate_copy(2)

struct rotate_copy_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O>
    requires std::indirectly_copyable<I, O>
    constexpr ranges::rotate_copy_result<I, O>
        operator()(I first, I middle, S last, O result) const
    {
        auto c1 {ranges::copy(middle, std::move(last), std::move(result))};
        auto c2 {ranges::copy(std::move(first), std::move(middle), std::move(c1.out))};
        return {std::move(c1.in), std::move(c2.out)};
    }

    template<ranges::forward_range R, std::weakly_incrementable O>
    requires std::indirectly_copyable<ranges::iterator_t<R>, O>
    constexpr ranges::rotate_copy_result<ranges::borrowed_iterator_t<R>, O>
        operator()(R&& r, ranges::iterator_t<R> middle, O result) const
    {
        return (*this)(ranges::begin(r), std::move(middle),
                       ranges::end(r), std::move(result));
    }
};

inline constexpr rotate_copy_fn rotate_copy {};

Notes

If the value type is TriviallyCopyable and the iterator types satisfy contiguous_iterator, implementations of ranges::rotate_copy usually avoid multiple assignments by using a "bulk copy" function such as std::memmove.

Examples

Main.cpp

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

int main()
{
    std::vector<int> src {1, 2, 3, 4, 5};
    std::vector<int> dest(src.size());
    auto pivot = std::ranges::find(src, 3);

    std::ranges::rotate_copy(src, pivot, dest.begin());
    for (int i : dest)
        std::cout << i << ' ';
    std::cout << '\n';

    // copy the rotation result directly to the std::cout
    pivot = std::ranges::find(dest, 1);
    std::ranges::rotate_copy(dest, pivot, std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

Output

3 4 5 1 2
1 2 3 4 5