为什么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个向量进行排序。使用std::rotate的排序需要0.376秒，而另一种排序需要8.181秒。

为什么会这样呢？我不打算做一些比STL函数更好的东西，但我仍然很好奇。

Answer 1

编辑：

因为没有给出上下文，所以不清楚您的代码是调用std::swap()还是调用其他swap(a,b)算法

T tmp = a; a = b; b = tmp;

当a和b分别是1000 ints的向量时，这将复制所有向量元素3次。std::vector<T>等容器的专用std::swap()版本改为调用容器a.swap(b)方法，本质上仅交换容器的动态数据指针。

此外，对于不同的迭代器类型，std::rotate()实现可以利用一些优化(参见下面我的旧的、可能具有误导性的答案)。

注意：std::rotate()的实现依赖于实现。对于不同的迭代器类别，可以使用不同的算法(例如，在GNU g++的bits/stl_algo.h头中查找__rotate( )。

要通过m=std::distance(first,middle)来移动n元素，一个简单的(朴素的)算法，比如按一个元素进行m次旋转，需要O(n*m)移动或复制操作。但是，当每个元素被直接放置到它的正确位置时，只需要O(n)移动，这导致了(大致) m倍快的算法。

下面是一个示例:将字符串s = "abcdefg"旋转三个元素：

abcdefg : store 'a' in temporary place
dbcdefg : move s[3] to s[0] (where it belongs in the end, directly)
dbcgefg : move s[6] to s[3]
dbcgefc : move s[9%7] to s[6] (wrapping index modulo container size: 9%7 == 2)
dbfgefc : move s[5] to s[2]
dbfgebc : move s[1] to s[5] (another wrapping around)
defgebc : move s[4] to s[1]
defgabc : move 'a' from temporary place to s[4]

对于最大公约数为1的n和m，现在就完成了。否则，您必须对第一个连续的m元素(此处假设为n > m)重复该方案n/m时间。这个稍微复杂一点的算法要快得多。

对于双向迭代器，可以使用另一个传奇的O(3n)算法，称为“翻转手”。根据Jon Bentley的书Programming Pearls，它在早期的UNIX编辑器中用于移动文本：

把你的手放在你前面，一个放在另一个上面，竖起大拇指。现在

1. 转动一只手。
2. 转动另一只手。
3. 转动两只手，彼此相连。

在代码中：

reverse(first, middle);
reverse(middle, last);
reverse(first, last);

对于随机访问迭代器，可以通过swap_ranges() (或用于POD类型的memmove()操作)重新定位的大块内存。

通过利用汇编器操作进行微优化可以提供少量的额外加速，它可以在快速算法之上完成。

在现代计算机体系结构上，使用连续元素而不是在内存中“跳来跳去”的算法也会导致较少的高速缓存未命中。

Answer 2

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

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

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

TL;DR：相信你的标准库，不要重复发明轮子！