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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk