Shifting/aligning/rotating a circular buffer to zero in-place
algorithm, arrays, circular-buffer, list
Solution
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/
Problem
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. So I have my circular `list` with capacity `N`, it has `n` elements starting at arbitrary index `f`. What's the fastest way to shift/rotate all the elements such that `f = 0`? 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.