two dimensional circular buffer?

[siegel14159265]

Hello everyone, I am trying to implement a circular fifo buffer that handles a column of numbers. At regular intervals, a column of numbers must be read into the buffer (from a socket), continuing till the buffer is filled with a fixed number of columns, then the oldest column must be replaced by the second oldest column and so forth.

There are tons of examples of circular buffers out there, but my question is the most efficient way to code a two dimensional cylinder version. This is not a homework question. So far I am thinking of using a single circular buffer, the elements of which are one dimensional arrays, but I have concerns about speed. Alternatively I am thinking about creating a structure of circular buffers, the elements of which are integers. If anyone has a more elegant idea I would be thrilled, and I would appreciate any hints about how to move forward.

[jsmith]

I would make use of STL containers such as std::deque for your "single circular buffer"
and maybe std::vector or boost::array for the elements.

The _really_ elegant way to do this would be to wrap this into your own container and
provide iterators and such for it so that all the STL algorithms work on it.

[hamsterman]

Firstly, ignore the 2d-ness of the container. It's just a 1d container of some object which happens to be another array.
Since the container is of static maximum size, you won't need to reallocate anything.

You need a head and tail marker.
Let's see how this would behave:
h - head
t - tail
size = 3;

At first,

h
???
 t

After pushing 2 elements,

h
ab?
  t

Then,

h
abc
t

and after that

 h
dbc
 t

From here head and tail will point to the same object.

First step would be a function int wrap(int i){ return (i%size+size)%size; }
Then you could define

void push(object o){
   array[tail] = o;
   if(head == tail) head = wrap(head+1);
   tail = wrap(tail+1);
}
void pop(){
   tail = wrap(tail-1);
}

I think that should work.

[siegel14159265]

Thanks guys, that gives me a lot to work with.