[boost] Re: Review Request: cyclic_buffer

From: Nigel Stewart (nigels_at_[hidden])
Date: 2003-06-10 20:03:27

        Hi Howard,

>>     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
        fail.

> 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...)

        Cheers,

        Nigel Stewart