Boost logo

Boost :

From: Nigel Stewart (nigels_at_[hidden])
Date: 2003-06-12 11:43:07

> deque is more expensive than a resizing circular buffer in both
> performance and code size. One also can not control *when* deque will
> allocate as one can with a resizing circular buffer. In a nutshell, a
> resizing circular buffer is often a better deque than std::deque is.
> ;-( A resizing circular buffer is absolutely awesome when plugged into
> std::queue. If your queue on average doesn't constantly grow, a
> resizing circular buffer is efficient, predictable and safe. A
> std::deque in std::queue will likely continually rellocate buffers as it
> drops one off one end and adds one to the other (and at annoyingly
> unpredictable times if you're doing real-time).


        I can see the appeal here in using a circular buffer in
        this manner, while at the same time I'm cooling against
        the compromise of "insert auto-resizes, while push doesn't"
        which seems inconsistant. Given that we both seem to have
        a real-time orientation, we're probably not so far apart
        in our thinking. Perhaps we simply need to make a distinction
        between a circular_buffer and a circular_deque which are only
        different in terms of resizing semantics. Each provides different
        characteristics, and stand independently as boost containers.
        Code re-use by itself doesn't seem to be a good enough reason
        to mix the concepts and overload the namespace unnecessarily.

        One idea that came to my mind was to have "forward insertion",
        "backward insertion" to resolve the question of semantics
        of arbitrary insertion into a circular_buffer. insert()
        pushes rightmost items forwards, overwriting leftmost items
        as necessary. rinsert() pushes leftmost items backwards,
        overwriting rightmost items as necessary. Likewise for the
        circular_deque which would reallocate as necessary to
        accomodate any kind of insertion - items would never be
        implicitly lost by a circular_deque.


Boost list run by bdawes at, gregod at, cpdaniel at, john at