arrays - 将循环缓冲区移位/对齐/旋转到原地零

Question

我正在使用循环缓冲区将数据推送到列表的任一端。完成后，我想对齐缓冲区，使列表中的第一个元素位于位置零，并且可以像常规数组一样使用，没有任何花哨的索引开销。

所以我有容量为 N 的循环 list，它有 n 个元素，从任意索引 f 开始.

移动/旋转所有元素以使 f = 0 的最快方法是什么？

问题是我想就地执行此操作(当然需要一些寄存器/临时文件)。缓冲区可能已满 (n = N)，[EDIT] 但我也有兴趣有效地处理它几乎是空的。

Answer 1

这个算法取自 cplusplus.com 上的 std::rotate 实现非常好:

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;
  }
}

http://www.cplusplus.com/reference/algorithm/rotate/