为什么 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。

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

Why is std::rotate faster than this way of doing it?

c++

algorithm

performance

stl