Re: [boost] Re: Review Request: cyclic_buffer

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2003-06-12 17:43:46

On Thursday, June 12, 2003, at 12:43  PM, Nigel Stewart wrote:

> 	I can see the appeal here in using a circular buffer in
> 	this manner, while at the same time I'm cooling against
> 	the compromise of "insert auto-resizes, while push doesn't"
> 	which seems inconsistant.  Given that we both seem to have
> 	a real-time orientation, we're probably not so far apart
> 	in our thinking.  Perhaps we simply need to make a distinction
> 	between a circular_buffer and a circular_deque which are only
> 	different in terms of resizing semantics.  Each provides different
> 	characteristics, and stand independently as boost containers.
> 	Code re-use by itself doesn't seem to be a good enough reason
> 	to mix the concepts and overload the namespace unnecessarily.

I'm beginning to think you're correct.  An informed process would be to 
create both containers, and adapt both types to the other, and measure 
the results.  I'm afraid I'm asking somebody else to do work here 
though.  I've got a resizing circular buffer (Metrowerks::cdeque has 
shipped with CodeWarrior for years), but I'm not at liberty to share 
the source.  And my schedule is tight enough that even higher priority 
things are slipping right now, so I can't donate cycles to a 
non-resizing variant to compare to.

> 	One idea that came to my mind was to have "forward insertion",
> 	"backward insertion" to resolve the question of semantics
> 	of arbitrary insertion into a circular_buffer.  insert()
> 	pushes rightmost items forwards, overwriting leftmost items
> 	as necessary.  rinsert() pushes leftmost items backwards,
> 	overwriting rightmost items as necessary.  Likewise for the
> 	circular_deque which would reallocate as necessary to
> 	accomodate any kind of insertion - items would never be
> 	implicitly lost by a circular_deque.

This sounds very interesting for the non-resizing version.  I think for 
the resizing version, the insert should simply minimize the elements 
that it is going to move.  Either way, all pointers and iterators must 
be considered invalidated (unlike the non-resizing variant with insert 
and rinsert).  In my mind, when you insert into the middle of a 
resizing circular buffer, the behavior (mental model) is very 
deque-like, except of course for the ability to predict whether it will 
require a reallocation or not.

-Howard