c++ - 为什么 std::rotate 这么快？

Question

为什么 std::rotate 比 cplusplus.com 描述的等效函数快这么多？

cplusplus.com 的实现:

template <class ForwardIterator>
  void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
{
  ForwardIterator next= middle;

  while (first != next)
  {
    swap (*first++, *next++);

    if(next == last)
        next= middle;
    else if (first==middle)
        middle= next;
  }
}

我有两种完全相同的插入排序算法，除了一种使用std::rotate，一种使用cplusplus.com 的等效函数。我将它们设置为使用 1000 个 int 元素对 1000 个 vector 进行排序。使用 std::rotate 的排序耗时 0.376 秒，另一个耗时 8.181 秒。

这是为什么？我不打算尝试制作比 STL 函数更好的东西，但我仍然很好奇。

Answer 1

正如评论者已经说过的，这取决于您的标准库实现。但是您发布的代码即使对于 前向迭代器 也是有效的。因此，它的要求非常低(只有这些迭代器可以递增和取消引用)。

斯捷潘诺夫的经典Elements of Programming rotate 花了整整一章 (10)和其他重排算法。对于前向迭代器，代码中的一系列交换给出 O(3N)作业。对于双向迭代器，连续三次调用 reverse产生另一个 O(3N)算法。对于随机访问迭代器，std::rotate可以实现为 O(N)通过定义索引排列 w.r.t.来分配到起始迭代器 first .

上述所有算法都是就地的。使用内存缓冲区，随机访问版本可能会受益于 memcpy() 更大的缓存局部性。或 memmove() (如果基础值类型是 POD)，其中可以交换整个连续内存块。如果您的插入排序是在数组或 std::vector 上完成的，您的标准库很可能会利用此优化。

TL;DR:相信您的标准库，不要重新发明轮子!