将圆形缓冲区移位/对齐/旋转到原位为零 [英] Shifting/aligning/rotating a circular buffer to zero in-place

问题描述

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

I'm using a circular buffer to push data onto either end of a list. After I'm done I want to align the buffer so the first element in the list is at position zero and can be used like a regular array without any fancy indexing overhead.

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

So I have my circular list with capacity N, it has n elements starting at arbitrary index f.

移动/旋转所有元素(例如f = 0)的最快方法是什么?

What's the fastest way to shift/rotate all the elements such that f = 0?

问题是我想就地进行此操作(虽然当然需要一些寄存器/临时器).缓冲区可能已满(n = N)，[ EDIT ]，但我也对有效处理几乎为空的情况感兴趣

The catch is I want to do this in-place (though of course some registers/temporaries will be needed). The buffer may be full (n = N), [EDIT] but I'm also interested in efficiently handling the cases where it's nearly empty.

推荐答案

从cplusplus.com的std::rotate实现中采用的这种算法非常好:

This algorithm taken from the std::rotate implementation on cplusplus.com is quite nice:

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/

这篇关于将圆形缓冲区移位/对齐/旋转到原位为零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！