Re: [boost] cyclic buffer

From: Thomas Wenisch (twenisch_at_[hidden])
Date: 2002-10-10 17:03:25

(cc'd to boost mailing list)

Hi Jan,

Sorry for the delay in getting back to you on your circular buffer.  
Thanks for sending me the code!  (For anyone else interested, I beleive
the code is in the files area on Yahoo - Jan, correct me if I am wrong).

First, some general comments:

1) 
    For me, the essential feature I require of a cyclic buffer is that
insertion/removal at the head or the tail DOES NOT invalidate iterators
that point into the middle.  In your documentation, I see that this is not
guaranteed, and I assume this follows from the fact that it is not
guaranteed by the underlying deque.  However, I do think it is very good
that you documented the invalidation rules clearly in your HOWTO.

2)  I am a big fan of Doxygen, so I like your documentation ;)

3)
    The current behavior of your implementation is that a write that
"overflows" the buffer removes the tail element.  An alternative
implementation would throw an exception - adding to a full circular buffer
is an error.  Both are very useful behaviors, for different use cases, and
most of the code would be the same.  I think it would be really cool if
policy parameters could be used to select between the behaviors.  A
similar choice exists for underflow (ie error or return a
default-constructed value_type).

4)
   Your implementation basically constrains a deque to a specific
capacity, and thus, provides the interface of a circular buffer.  
However, the performance characteristics are identical to a deque.  The
main reason I choose to use a circular buffer over a deque is performance:
I expect that a circular buffer will not perform allocations when it is
being used.
  This gives me a number of things: first, the push_front(), and
push_back() methods could truly be constant time operations, rather than
amortized constant time (ie you pay the allocation penalty at
construction, but never again).  Second, I am guaranteed that allocations
won't fail.  
  With a deque-backed implementation as you have implemented, the
"circular buffer" is really marching forward in memory - when you allocate
an element, you attach it at the end of the deque, which means after all
previously allocated elements, and could mean that the deque has been
relocated to a different address.  Then, you remove the head.

   What I would really like to see is an implementation that is backed by
a vector, with head and tail pointers used to know where the top and
bottom of the buffer are.  In such a design, the hard part is writing a
random-access iterator - the vector iterator will do the wrong
thing.  With that, you get no invalidation of iterators on push or pops at
either end (use vector assignment, not vector push/pop); constant time
pushes and pops; no possibility of allocation failures; and you still have
constant time random access.
   But, it takes a lot more code to do it...

Comments on the Code:

1) Overall, it is very good and very readable.

2) There are several missing typename keywords.  Basically, everytime you
have Container::xxx, it should read typename Container::xxx

Regards,
-Tom Wenisch
Computer Architecture Lab
Carnegie Mellon University