[boost] Re: Review Request: cyclic_buffer

From: Dave Gomboc (dave_at_[hidden])
Date: 2003-06-11 16:55:47

------------------------------

Date: Thu, 12 Jun 2003 02:36:10 +1000
From: Nigel Stewart <nigels_at_[hidden]>
To: boost_at_[hidden]
Subject: [boost] Re: Review Request: cyclic_buffer
Message-ID: <bc7leg$lhi$1_at_[hidden]>
In-Reply-To: <bc7csv$2er$1_at_[hidden]>
References: <Pine.LNX.4.21L.0210101654480.23754-100000_at_[hidden]>
        <3EDDC088.C966EDF6_at_[hidden]> <bbqbo8$80i$1_at_[hidden]>
        <1054937318.3ee110e6403fd_at_[hidden]>
        <bbrflu$3o4$1_at_[hidden]>
        <3EE45606.DA3C3764_at_[hidden]> <bc1ntm$c5f$1_at_[hidden]>
        <3EE6F8CE.8D4B869C_at_[hidden]> <bc7csv$2er$1_at_[hidden]>
Content-Type: text/plain; charset=us-ascii; format=flowed
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Precedence: list
Message: 15

>     This strikes me as a good compromise.  For one thing, it leaves the 
>     door open to inserting in a manner that resizes the capacity.  (Except 
>     for the problem that if the buffer is full, every insert will require O(n) 
>     time)

        I later realised an important point: insert will be O(n)
        anyway, given the need to make room for the inserted items.
        So, it seems that allowing automatic resizing in this
        case does not cost anything in terms of performence
        implications.

Every insert will *not* require O(n) time, unless the implementation is, 
to quote another poster, "brain-damaged".

Is there a compelling use case for a circular buffer that resizes?  Why is
a deque inadequate?  IME circular buffers are constant-sized.

Dave