Re: [boost] Re: Review Request: cyclic_buffer

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2003-06-10 11:40:11

On Tuesday, June 10, 2003, at 11:33  AM, Nigel Stewart wrote:

>> Constant time push/pop_front, constant time push/pop_back.  When begin
>> and end collide, reallocation automatically happens vector-like.
>
> 	Another point to consider:
>
> 	Constant time push/pop can not be combined with std::vector
> 	automatic re-allocation due to the linear cost of copying
> 	into the realloc'd buffer.  Given that circular buffers
> 	are often used in the context of real-time applications,
> 	it seems to be consistant that push/pop from each end
> 	should be truely constant time, and as a consequence the
> 	the capacity is never implicitly changed unless explicitly
> 	requested via reserve() or resize().

Clearly there is a need for what you are describing.  And clearly there 
is a need for what I am describing.  And clearly there are a few more 
closely related needs.

My opinion is that it is much easier to adapt a reallocating circular 
buffer to a non-reallocating one than vice-versa.  It is non-trivial to 
get a reallocating circular buffer correct with respect to exception 
safety, iterator/pointer invalidation, possible optimizations for types 
with trivial assign and copy, etc.  I would rather get the detailed, 
complicated work encapsulated in the container, and then have 
relatively simple adaptors a-la std::stack and std::queue.

An adapted construct-time-fixed-capacity circular buffer is no more 
inefficient or dangerous than a "native container" version.  And the 
adaptor is simple to write.  And because the adaptor is simple to 
write, there can be a different adaptor for every different need.

insert doesn't make sense?  Hide it.  It will never even be 
instantiated.  Don't want to reallocate?  Override push_back to check 
for size()==capacity() and then perform your favorite action (overwrite 
front, throw an exception, burn the toast, whatever).  Can only afford 
a reallocation if not at interrupt time?  Not a problem.  etc.

-Howard