为什么std::rotate比这种方式更快呢？

Question

void rotate(vector <int> &a)
{
    int lastElem = a[a.size()-1];
    
    for(int i=a.size()-1;i>0;i--){
       a[i] = a[i-1];
    }
    
    a[0] = lastElem;
}

对比

rotate(a.begin(),a.end()-1,a.end());

据我所知，上面的算法是O(n)，那么为什么STL的速度更快(我以为它也是线性时间)。

Answer 1

std::rotate的标准库实现很可能使用对memmove()的调用来进行批量数据复制。这就是它比手写循环更快的原因之一。

因为您只旋转单个元素，所以可以用调用std::copy_backward替换您的循环。这也将编译成memmove()，并提供更好的性能。

void rotate(std::vector<int> &a)
{
    int lastElem = a.back();
    std::copy_backward(a.begin(), a.end() - 1, a.end()); // memmove()
    a.front() = lastElem;
}

您可以检查生成的程序集here on Compiler Explorer。