std::ranges::rotate

在标头 `<algorithm>` 定义

调用签名
template< std::permutable I, std::sentinel_for<I> S > constexpr ranges::subrange<I> rotate( I first, I middle, S last );	(1)	(C++20 起)
template< ranges::forward_range R > requires std::permutable<ranges::iterator_t<R>> constexpr ranges::borrowed_subrange_t<R> rotate( R&& r, ranges::iterator_t<R> middle );	(2)	(C++20 起)

1) 在元素范围上进行左旋。具体而言， ranges::rotate 交换范围 [first, last) 中的元素使得元素 *middle 成为新范围的起始，而 *(middle - 1) 成为新的末元素。

若 [first, last) 不是合法范围或 middle 不在 [first, last) 中则行为未定义。

2) 同 (1) ，但以 r 为范围，如同以 ranges::begin(r) 为 first 并以 ranges::end(r) 为 last 。

此页面上描述的仿函数实体是 niebloid，即：

调用它们中的任何一个时不能显式指定模板实参。
它们都不对实参依赖查找可见。
在通过函数调用运算符左侧的名字进行无限定查找，找到它们之一时，禁止实参依赖查找。

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

参数

first, last	-	要旋转的元素范围
r	-	要旋转的元素范围
middle	-	指向要出现在旋转后范围起始的元素的迭代器

返回值

{new_first, last} ，其中 new_first 与 ranges::next(first, ranges::distance(middle, last)) 比较相等，并指代 first 所指向的元素的新位置。

复杂度

最坏为线性： ranges::distance(first, last) 次交换。

注解

在常见实现上，若 I 实现 bidirectional_iterator 或（更好的） random_access_iterator 则 ranges::rotate 有更高的效率。

实现（例如 MSVC STL ）可能在迭代器类型实现 contiguous_iterator ，并且交换其值类型不调用非平凡的特殊成员函数或 ADL 所找到的 swap 时启用向量化。

可能的实现

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

struct rotate_fn
{
    template<std::permutable I, std::sentinel_for<I> S>
    constexpr ranges::subrange<I>
        operator()(I first, I middle, S last) const
    {
        if (first == middle)
        {
            auto last_it = ranges::next(first, last);
            return {last_it, last_it};
        }
        if (middle == last)
            return {std::move(first), std::move(middle)};
 
        if constexpr (std::bidirectional_iterator<I>)
        {
            ranges::reverse(first, middle);
            auto last_it = ranges::next(first, last);
            ranges::reverse(middle, last_it);
 
            if constexpr (std::random_access_iterator<I>)
            {
              ranges::reverse(first, last_it);
              return {first + (last_it - middle), std::move(last_it)};
            }
            else
            {
                auto mid_last = last_it;
                do
                {
                    ranges::iter_swap(first, --mid_last);
                    ++first;
                }
                while (first != middle && mid_last != middle);
                ranges::reverse(first, mid_last);
 
                if (first == middle)
                    return {std::move(mid_last), std::move(last_it)};
                else
                    return {std::move(first), std::move(last_it)};
            }
        }
        else
        { // I 仅为 forward_iterator
            auto next_it = middle;
            do
            { // rotate 第一循环
                ranges::iter_swap(first, next_it);
                ++first;
                ++next_it;
                if (first == middle)
                    middle = next_it;
            }
            while (next_it != last);
 
            auto new_first = first;
            while (middle != last)
            { // rotate 后继循环
                next_it = middle;
                do
                {
                    ranges::iter_swap(first, next_it);
                    ++first;
                    ++next_it;
                    if (first == middle)
                        middle = next_it;
                }
                while (next_it != last);
            }
 
            return {std::move(new_first), std::move(middle)};
        }
    }
 
    template<ranges::forward_range R>
    requires std::permutable<ranges::iterator_t<R>>
    constexpr ranges::borrowed_subrange_t<R>
        operator()(R&& r, ranges::iterator_t<R> middle) const
    {
        return (*this)(ranges::begin(r), std::move(middle), ranges::end(r));
    }
};
 
inline constexpr rotate_fn rotate {};

示例

rotate 算法能用作许多其他算法的公共构建块，例如插入排序：

运行此代码

#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
 
int main()
{
    std::string s(16, ' ');
 
    for (int k{}; k != 5; ++k) {
        std::iota(s.begin(), s.end(), 'A');
        std::ranges::rotate(s, s.begin() + k);
        std::cout << "Rotate left (" << k << "): " << s << '\n';
    }
 
    std::cout << '\n';
 
    for (int k{}; k != 5; ++k) {
        std::iota(s.begin(), s.end(), 'A');
        std::ranges::rotate(s, s.end() - k);
        std::cout << "Rotate right (" << k << "): " << s << '\n';
    }
 
    std::cout << "\n" "Insertion sort using `rotate`, step-by-step:\n";
 
    s = {'2', '4', '2', '0', '5', '9', '7', '3', '7', '1'};
 
    for (auto i = s.begin(); i != s.end(); ++i) {
        std::cout << "i = " << std::ranges::distance(s.begin(), i) << ": ";
        std::ranges::rotate(std::ranges::upper_bound(s.begin(), i, *i), i, i + 1);
        std::cout << s << '\n';
    }
    std::cout << (std::ranges::is_sorted(s) ? "Sorted!" : "Not sorted.") << '\n';
}

输出：

Rotate left (0): ABCDEFGHIJKLMNOP
Rotate left (1): BCDEFGHIJKLMNOPA
Rotate left (2): CDEFGHIJKLMNOPAB
Rotate left (3): DEFGHIJKLMNOPABC
Rotate left (4): EFGHIJKLMNOPABCD
 
Rotate right (0): ABCDEFGHIJKLMNOP
Rotate right (1): PABCDEFGHIJKLMNO
Rotate right (2): OPABCDEFGHIJKLMN
Rotate right (3): NOPABCDEFGHIJKLM
Rotate right (4): MNOPABCDEFGHIJKL
 
Insertion sort using `rotate`, step-by-step:
i = 0: 2420597371
i = 1: 2420597371
i = 2: 2240597371
i = 3: 0224597371
i = 4: 0224597371
i = 5: 0224597371
i = 6: 0224579371
i = 7: 0223457971
i = 8: 0223457791
i = 9: 0122345779
Sorted!

参阅

ranges::rotate_copy (C++20)	复制并旋转元素范围 (niebloid)
ranges::reverse (C++20)	逆转范围中的元素顺序 (niebloid)
rotate	旋转范围中的元素顺序 (函数模板)

编译器支持
自立实现与有宿主实现
语言
标准库
标准库标头
具名要求
功能特性测试宏 (C++20)
语言支持库
概念库 (C++20)
元编程库 (C++11)
诊断库
通用工具库
字符串库
容器库
迭代器库
范围库 (C++20)
算法库
数值库
本地化库
输入/输出库
文件系统库 (C++17)
正则表达式库 (C++11)
并发支持库 (C++11)
技术规范
符号索引
外部库

std::ranges::rotate

参数

返回值

复杂度

注解

可能的实现

示例

参阅

导航