[boost] Re: Review Request: cyclic_buffer

From: Nigel Stewart (nigels_at_[hidden])
Date: 2003-06-10 10:33:40

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

        So as a proposed design criteria:

        circular_buffer

        - provides guaranteed O(1) push/pop
        - provides O(n) arbitrary insertion
        - provides O(n) manual capacity and size management

        in contrast to vector

        - provides (amortized) O(1) push_back/pop_back
          O(n) in reallocation case
        - provides O(n) arbitrary insertion
        - provides O(n) manual capacity and size management
        
        (The implication for real-time uses of circular_buffer is that
         only push and pop are allowed in time-critical code.)

        This I think is a resounding case against re-allocation,
        and reflected in the broader understanding of what circular
        buffers are commonly used for.

        A re-allocating circular_buffer should therefore only be
        an adaptor or variant, but can not provide "proper" O(1)
        push/pop, so is missing this critical feature of a "true"
        circular_buffer.