c++如何使用std::rotate_c++容器元素循环移动【入门】

4次阅读

std::rotate是将[first, middle)与[middle, last)两段交换位置的确定性切割拼接操作,不是动画式旋转;要求middle∈[first,last)且不可为last(除非first==last),支持所有可赋值迭代器,时间复杂度o(n),对move-only类型安全使用move语义。

c++如何使用std::rotate_c++容器元素循环移动【入门】

std::rotate 是什么,不是什么

std::rotate 不是“把容器转个圈”那种直观的旋转动画,它干的是一个确定的切割+拼接操作:把迭代器范围 [first, middle)[middle, last) 两段内容交换位置。结果上看起来像“循环左移”,但本质是三段内存的重排——中间点 middle 决定了哪部分被“移到前面”。

常见错误现象:std::rotate(v.begin(), v.begin() + 2, v.end()) 想左移 2 位,却因 middle 超出范围崩溃;或误以为它支持负偏移(实际不支持,得自己算等效正 offset)。

  • 使用场景:实现数组/向量的循环位移、轮转调度、滑动窗口重置
  • 参数差异:middle 必须在 [first, last] 范围内,且不能是 last(除非 first == last
  • 性能影响:平均时间复杂度 O(n),内部用 swap 或 move,对 std::vector<int></int> 很快,但对大对象可能触发多次移动构造

怎么写一个安全的循环左移函数

直接裸用 std::rotate 容易越界或逻辑反向。封装一层能规避多数坑:

template <typename It> void rotate_left(It first, It last, size_t k) {     if (first == last) return;     const auto n = std::distance(first, last);     if (n <= 1) return;     k = k % n; // 防止 k 大于长度     if (k == 0) return;     std::rotate(first, first + k, last); // 左移 k 位 = 把前 k 个挪到后面 }

关键点:

立即学习C++免费学习笔记(深入)”;

  • 必须先算 std::distance,不能依赖容器 size()(比如传入 list::iterator 时)
  • k % n 不可省——否则 k > n 会令 first + k 越界
  • std::liststd::rotate 仍可用,但 first + k 无效(不支持随机访问),得改用 std::next(first, k)

std::rotate 和手写 for 循环比,差在哪

有人觉得“不就移几个数?我自己 swap 就行”,但忽略了几点:

  • 兼容性:std::rotate 对所有符合要求的迭代器都有效(vectordequelist、甚至 std::Array 的原始指针),手写循环往往只适配 vector
  • 异常安全:标准库实现保证强异常安全(移动失败时状态不变),手写容易漏掉中间异常点
  • 优化空间:libc++ / libstdc++std::rotate 有特化,比如对 POD 类型可能用 memmove,比逐个 swap 快得多
  • 边界陷阱:手写左移常错把 v[i] = v[(i+k)%n] 当成原地操作,实际需要额外空间或反向遍历,而 std::rotate 原生就是原地、稳定、无额外分配

容易被忽略的 const_iterator 和 move-only 类型

std::rotate 要求迭代器可 dereference 并能赋值,所以:

  • 不能传 const_iterator —— 因为无法修改元素(报错类似 assignment of read-only location
  • 对 move-only 类型(如 std::unique_ptr),std::rotate 用 move 而非 copy,没问题;但若自己写 swap,得确保类型支持 std::move,否则编译失败
  • 如果容器元素是 const 修饰的(比如 std::vector<const int></const>),根本无法编译——这不是 std::rotate 的问题,而是设计错误,const 元素容器本身几乎无实用价值

真正麻烦的是调试时看到 Error: use of deleted function 'std::unique_ptr<...>& std::unique_ptr<...>::operator=(const std::unique_ptr<...>&)'</...></...></...>,其实只是你传了 const_iterator,而不是类型本身不支持。

text=ZqhQzanResources