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

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

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

为什么不能直接用 `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 <h3>反转三次法：更易写对、且对缓存友好</h3><p>比环形置换更少出错，原理简单：右移 <code>k</code> 等价于「整体反转 → 前 <code>k</code> 反转 → 后 <code>n-k</code> 反转」。所有操作都是对半交换，无取模、无循环计数，CPU 预取友好，尤其适合大数组。</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架"><img
														src="https://img.php.cn/upload/skill/000/000/081/178988956499722.jpg" alt="C++ 算法竞赛自动化测试数据生成与校验框架" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="overflowclass">C++ 算法竞赛自动化测试数据生成与校验框架</a>
													<p class="overflowclass">根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。</p>
												</div>
												<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div><p>使用场景与细节：</p>

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

简明实现：

void rotate_right(int* arr, int n, int k) {
    if (n <h3>左移 vs 右移：别硬套公式，统一转成右移处理</h3><p>左移 <code>k</code> 等价于右移 <code>n - k</code>，但直接算 <code>n - k</code> 有风险：若 <code>k > n</code> 且未先取模，<code>n - k</code> 会变成负数。正确做法始终先做 <code>k %= n</code>，再根据方向决定用 <code>k</code> 还是 <code>n - k</code>。</p><p>容易踩的坑：</p>