From: Nigel Stewart (nigels_at_[hidden])
Date: 2003-06-10 20:03:27
>> 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.
> 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.
The "generally accepted" concept of a circular buffer
is a fixed size contiguous memory buffer. Following
the principle of "least surprise" a circular_buffer
should not decide to resize itself. To overwrite
items at the opposite end seems to bother some,
(it is a feature, or a bug?) it certainly seems to be
the "generlly accepted" concept of what a circular
buffer does. (Unless the insertion fails, or the thread
is blocked until space becomes available)
Another reason against reallocation is the
possibility that two threads could utilise a
circular_buffer from each end in a
"producer/consumer model", without the need
for explicit locking. Having one thread decide
to move everything elsewhere in memory would
appear to exclude this style of use.
Another reason against reallocation is that
except for resize() and reserve() circular buffer
manipulation is _guaranteed_ to succeed, no
memory allocations occur which could possibly
> My opinion is that it is much easier to adapt a reallocating circular
> buffer to a non-reallocating one than vice-versa.
I don't agree, apart from the reasoning above.
What is the problem with intercepting push and insert
and reserving larger amounts of memory as necessary?
> 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.
We should aim to capture the "true" concept of a
circular buffer, perhaps.
(It will be interesting to see where all this leads
to, in the end...)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk