std::ranges::rotate_copy, std::ranges::rotate_copy_result

来自cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
算法库
受约束算法及范围上的算法 (C++20)
受约束算法: std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
二分搜索操作
集合操作(在已排序范围上)
堆操作
(C++11)
最小/最大操作
(C++11)
(C++17)

排列
数值运算
C 库
 
受约束算法
不修改序列的操作
修改序列的操作
划分操作
排序操作
二分搜索操作
集合操作(在已排序范围上)
堆操作
最小/最大操作
排列
未初始化存储上的操作
返回类型
 
定义于头文件 <algorithm>
调用签名
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 );
(1) (C++20 起)
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 );
(2) (C++20 起)
辅助类型
template< class I, class O >
  using rotate_copy_result = in_out_result<I, O>;
(3) (C++20 起)
1) 从源范围 [first, last) 复制元素到始于 result 的目标范围,使得元素 *middle 称为目标范围的首个元素,而 *(middle - 1) 成为末元素。结果为目标范围含有源范围的左旋转副本。
[first, middle)[middle, last) 不是合法范围,或若源与目标范围重叠,则行为未定义。
2)(1) ,但以 r 为源范围,如同以 ranges::begin(r)first 并以 ranges::end(r)last

此页面上描述的仿函数实体是 niebloid ,即:

实际上,它们能以函数对象,或以某些特殊编译器扩展实现。

参数

first, last - 要复制的源元素范围
r - 要复制的源元素范围
middle - 指向应该出现在目标范围起始的元素的迭代器
result - 目标范围的起始

返回值

{last, result + N} ,其中 N = ranges::distance(first, last)

复杂度

线性:准确赋值 N 次。

注解

若值类型为可平凡复制 (TriviallyCopyable) 且迭代器类型满足 contiguous_iterator ,则 ranges::rotate_copy 的实现通常通过使用如 std::memmove 的“大块复制”函数避免多次赋值。

可能的实现

参阅 libstdc++MSVC STL 中的实现。

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{};

示例

#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';
 
    // 直接复制旋转结果到 std::cout
    pivot = std::ranges::find(dest, 1);
    std::ranges::rotate_copy(dest, pivot, std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

输出:

3 4 5 1 2
1 2 3 4 5

参阅

旋转范围中的元素顺序
(niebloid)
将某一范围的元素复制到一个新的位置
(niebloid)
复制并旋转元素范围
(函数模板)