From: Howard Hinnant (hinnant_at_[hidden])
Date: 2003-06-12 17:43:46
On Thursday, June 12, 2003, at 12:43 PM, Nigel Stewart wrote:
> 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.
I'm beginning to think you're correct. An informed process would be to
create both containers, and adapt both types to the other, and measure
the results. I'm afraid I'm asking somebody else to do work here
though. I've got a resizing circular buffer (Metrowerks::cdeque has
shipped with CodeWarrior for years), but I'm not at liberty to share
the source. And my schedule is tight enough that even higher priority
things are slipping right now, so I can't donate cycles to a
non-resizing variant to compare to.
> 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.
This sounds very interesting for the non-resizing version. I think for
the resizing version, the insert should simply minimize the elements
that it is going to move. Either way, all pointers and iterators must
be considered invalidated (unlike the non-resizing variant with insert
and rinsert). In my mind, when you insert into the middle of a
resizing circular buffer, the behavior (mental model) is very
deque-like, except of course for the ability to predict whether it will
require a reallocation or not.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk