C++ std::vector如何高效将尾部指定元素段移动到头部？

你的现有实现可以正确完成功能，但存在额外内存开销大的问题，确实有更高效的实现方式。

现有实现的问题 #

你当前的方案需要申请和原vector等大小的临时内存，所有元素都需要完成一次拷贝，额外内存开销为O(n)，如果存储的是大对象、非可平凡拷贝的对象，额外的拷贝和内存分配/释放开销会非常明显。

最优方案：直接使用STL标准库std::rotate #

STL的std::rotate算法就是专门用来处理「将区间内[middle, last)的元素移动到区间头部」的场景，和你的需求完全匹配，不需要额外申请堆内存，空间复杂度为O(1)，时间复杂度仍然是*O(n)*但常数项远低于手写循环，标准库对vector这类连续内存容器做了专门的性能优化，对于支持移动语义的元素类型还会优先调用移动构造替代拷贝，性能提升非常明显。

优化后的代码如下：

#include <algorithm> // 需引入algorithm头文件

template <class ElementType>
void endToStart(std::vector<ElementType>& vect, size_t startPos)
{
    // 增加边界检查，避免非法输入
    if (startPos == 0 || startPos >= vect.size()) {
        return;
    }
    std::rotate(vect.begin(), vect.begin() + startPos, vect.end());
}

你给出的示例vect = {1,2,3,4,5,6,7}，移动最后2个元素到头部对应startPos = 5，调用上述函数后得到的结果完全符合预期：{6,7,1,2,3,4,5}。

手动实现可选方案：三次反转法 #

如果你不想依赖STL算法，也可以用经典的三次反转法实现，效率和std::rotate基本一致，同样不需要额外内存：

template <class ElementType>
void endToStart(std::vector<ElementType>& vect, size_t startPos)
{
    if (startPos == 0 || startPos >= vect.size()) {
        return;
    }
    // 反转前半段 [0, startPos)
    std::reverse(vect.begin(), vect.begin() + startPos);
    // 反转后半段 [startPos, vect.size())
    std::reverse(vect.begin() + startPos, vect.end());
    // 反转整个容器
    std::reverse(vect.begin(), vect.end());
}

内容的提问来源于stack exchange，提问作者Wballer3