C++如何实现高效的数组元素原位循环移动(零辅助空间)-C++-PHP中文网

std::rotate是原位循环移动的首选方案，因其o(n)时间、o(1)空间、三步翻转实现、无需移动构造且高度优化；手动实现应优先采用三步翻转法并注意模运算与边界处理。

c++如何实现高效的数组元素原位循环移动(零辅助空间)

为什么`std::rotate`是首选方案

标准库的 std::rotate 就是为原位循环移动设计的，时间复杂度 O(n)，空间复杂度 O(1)，且经过高度优化（通常用三步翻转法实现）。它不分配额外内存，也不依赖元素可赋值以外的强约束（比如不需要移动构造），比手写更可靠。

常见错误是自己实现“逐个挪位”——看似省空间，实则 O(n²) 时间，尤其在大数组上卡顿明显；或者误用 std::swap 链式交换但没处理好环，导致部分元素被跳过或重复移动。

实操建议：

头文件必须包含 <algorithm></algorithm>
调用形式：std::rotate(first, middle, last)，其中 [first, middle) 是要移到末尾的部分，[middle, last) 移到前面
例如把长度为 7 的数组右移 2 位：等价于 std::rotate(v.begin(), v.begin() + 5, v.end())（因为前 5 个元素变成新开头）
若需左移 k 位，等价于右移 n - k % n 位，或直接用 std::rotate(v.begin(), v.begin() + k % n, v.end())

手动实现三步翻转法时的关键细节

当不能用 STL（如嵌入式环境、自定义容器、或需完全控制逻辑），三步翻转是最稳妥的手写方案：先翻转前 n−k 个，再翻转后 k 个，最后翻转整个数组。它严格保证每个元素只访问两次，无分支预测失败风险。

容易踩的坑是边界计算错误，尤其 k 超出数组长度或为 0 时未归一化。

实操建议：

务必先做模运算：k = k % n，且处理 k == 0 的短路退出
翻转函数必须支持半开区间：reverse(first, first + len)，避免 off-by-one
使用 std::iter_swap 或手动交换，别依赖 T 支持移动语义——基础翻转只靠拷贝/交换

示例片段：

void rotate_left(int* a, size_t n, size_t k) {
    if (n == 0 || (k %= n) == 0) return;
    reverse(a, a + k);
    reverse(a + k, a + n);
    reverse(a, a + n);
}