C++如何实现高效的数组元素原位循环移动（避免占用额外辅助内存开销）

不能直接用 std::rotate 是因为自定义类型可能不满足可移动/可复制要求，或某些 STL 实现未优化为环形置换；此时需手写环形置换法，用 gcd(n,k) 确定循环组数，仅靠三个指针和一个临时变量完成原位旋转。

先说一个核心判断：很多人第一反应是调用 std::rotate——它确实原位、标准、简洁。但实际项目中常遇到两种情况，让它直接“失效”：自定义类型不满足可移动/可复制要求（比如含非 trivial 析构或禁用拷贝的类），或者编译器对 std::rotate 的实现未做优化（某些嵌入式 STL 版本仍用三段拷贝而非环形置换）。这时候必须手写逻辑，而且不能依赖 std::move 或临时对象。

为什么不能直接用 std::rotate 就完事？

多数人第一反应是调用 std::rotate —— 它确实原位、标准、简洁。但实际项目中常遇到两种情况让它失效：自定义类型不满足可移动/可复制要求（比如含非 trivial 析构或禁用拷贝的类），或者编译器对 std::rotate 的实现未做优化（某些嵌入式 STL 版本仍用三段拷贝而非环形置换）。此时必须手写逻辑，且不能依赖 std::move 或临时对象。

环形置换法：三个指针搞定任意步长移动

核心思路是把数组看作若干不相交的循环链，每个元素按步长 k 跳转，直到回到起点。关键在于计算循环节个数：gcd(n, k)，它决定了要启动几个独立循环。每轮循环内只用一个临时变量暂存值，其余靠赋值链完成。

实操要点：

• 先对 k 取模：k = k % n，避免无效整圈移动
• 用 std::gcd（C++17+）或手写欧几里得算法求循环组数
• 外层循环执行 gcd(n,k) 次，每次从索引 i 开始；内层循环直到回到 i
• 注意边界：当 n == 0 或 k == 0 直接返回，避免除零或空操作

示例（右移 2 位）：

void rotate_right(int* arr, int n, int k) {
    if (n <= 1 || k == 0) return;
    k = k % n;
    int cycles = std::gcd(n, k);
    for (int i = 0; i < cycles; ++i) {
        int temp = arr[i];
        int j = i;
        do {
            int next = (j + k) % n;
            std::swap(arr[j], arr[next]); // 或直接赋值：arr[j] = arr[next]
            j = next;
        } while (j != i);
        arr[i] = temp; // 补回起点
    }
}

反转三次法：更易写对、且对缓存友好

比环形置换更少出错，原理简单：右移 k 等价于「整体反转 → 前 k 反转 → 后 n-k 反转」。所有操作都是对半交换，无取模、无循环计数，CPU 预取友好，尤其适合大数组。

使用场景与细节：

• 适用于任意整型、POD 类型；若类型含构造/析构，需确保 swap 是 noexcept 且廉价
• k 必须先规约：k = k % n，否则反转区间越界
• 三次反转总交换次数恒为 n/2，而环形置换最坏也是 n 次赋值，性能接近
• 代码更短，边界处理直观（比如 reverse(arr, arr + k) 不会越界只要 k < n）

简明实现：

void rotate_right(int* arr, int n, int k) {
    if (n <= 1 || k == 0) return;
    k = k % n;
    std::reverse(arr, arr + n);
    std::reverse(arr, arr + k);
    std::reverse(arr + k, arr + n);
}

左移 vs 右移：别硬套公式，统一转成右移处理

左移 k 等价于右移 n - k，但直接算 n - k 有风险：若 k > n 且未先取模，n - k 会变成负数。正确做法始终先做 k %= n，再根据方向决定用 k 还是 n - k。

容易踩的坑：

• 误写 k = n - k % n —— 应该是 k = (n - (k % n)) % n，但更安全的是统一规约后分支处理
• 用 sizeof 算数组长度？传参只能拿到指针，n 必须显式传入
• 模板泛化时忘记约束：若支持任意迭代器，需检查是否为 RandomAccessIterator，否则 + 和 - 不合法

真正难的不是算法本身，而是让这段代码在 constexpr 上下文、无异常保证、或内存受限环境下依然成立——这时候连 std::gcd 都得自己写，且不能递归。