std:: rotate

若满足以下任一条件，则行为未定义：

• [ first , middle ) 或 [ middle , last ) 不是有效的 范围 。

参数

返回值

指向最初由 * first 所引用元素的迭代器，即 first 的第 std:: distance ( middle, last ) th 个后继迭代器。

复杂度

最多进行 std:: distance ( first, last ) 次交换。

异常

带有名为 ExecutionPolicy 模板参数的重载按以下方式报告错误：

• 如果作为算法一部分调用的函数执行抛出异常，且 ExecutionPolicy 是某个 标准策略 ，则调用 std::terminate 。对于其他任何 ExecutionPolicy ，其行为由实现定义。
• 如果算法无法分配内存，则抛出 std::bad_alloc 。

可能的实现

另请参阅以下实现： libstdc++ 、 libc++ 和 MSVC STL 。

template<class ForwardIt>
constexpr // 自 C++20 起
ForwardIt rotate(ForwardIt first, ForwardIt middle, ForwardIt last)
{
    if (first == middle)
        return last;
    if (middle == last)
        return first;
    ForwardIt write = first;
    ForwardIt next_read = first; // 当 "read" 到达 "last" 时的读取位置
    for (ForwardIt read = middle; read != last; ++write, ++read)
    {
        if (write == next_read)
            next_read = read; // 跟踪 "first" 移动后的位置
        std::iter_swap(write, read);
    }
    // 将剩余序列旋转到正确位置
    rotate(write, next_read, last);
    return write;
}

注释

当 ForwardIt 满足 LegacyBidirectionalIterator 或（更优情况下） LegacyRandomAccessIterator 时， std::rotate 在常见实现中具有更优效率。

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

示例

#include <algorithm>
#include <iostream>
#include <vector>
auto print = [](const auto remark, const auto& v)
{
    std::cout << remark;
    for (auto 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);
}

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

缺陷报告

下列行为变更缺陷报告被追溯应用于先前发布的 C++ 标准。

参见