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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk