Boost logo

Boost :

From: Jan Gaspar (jga_at_[hidden])
Date: 2002-10-11 02:18:37

Hi Thomas!

Thank you very much for your effort. Your review is very helpful to me.

Thomas Wenisch wrote:

> (cc'd to boost mailing list)
> Hi Jan,
> Sorry for the delay in getting back to you on your circular buffer.
> Thanks for sending me the code! (For anyone else interested, I beleive
> the code is in the files area on Yahoo - Jan, correct me if I am wrong).

Yes, the code is on Yahoo.

> First, some general comments:
> 1)
> For me, the essential feature I require of a cyclic buffer is that
> insertion/removal at the head or the tail DOES NOT invalidate iterators
> that point into the middle. In your documentation, I see that this is not
> guaranteed, and I assume this follows from the fact that it is not
> guaranteed by the underlying deque. However, I do think it is very good
> that you documented the invalidation rules clearly in your HOWTO.
> 2) I am a big fan of Doxygen, so I like your documentation ;)
> 3)
> The current behavior of your implementation is that a write that
> "overflows" the buffer removes the tail element. An alternative
> implementation would throw an exception - adding to a full circular buffer
> is an error. Both are very useful behaviors, for different use cases, and
> most of the code would be the same. I think it would be really cool if
> policy parameters could be used to select between the behaviors. A
> similar choice exists for underflow (ie error or return a
> default-constructed value_type).

Good point!

> 4)
> Your implementation basically constrains a deque to a specific
> capacity, and thus, provides the interface of a circular buffer.
> However, the performance characteristics are identical to a deque. The
> main reason I choose to use a circular buffer over a deque is performance:
> I expect that a circular buffer will not perform allocations when it is
> being used.
> This gives me a number of things: first, the push_front(), and
> push_back() methods could truly be constant time operations, rather than
> amortized constant time (ie you pay the allocation penalty at
> construction, but never again). Second, I am guaranteed that allocations
> won't fail.
> With a deque-backed implementation as you have implemented, the
> "circular buffer" is really marching forward in memory - when you allocate
> an element, you attach it at the end of the deque, which means after all
> previously allocated elements, and could mean that the deque has been
> relocated to a different address. Then, you remove the head.
> What I would really like to see is an implementation that is backed by
> a vector, with head and tail pointers used to know where the top and
> bottom of the buffer are. In such a design, the hard part is writing a
> random-access iterator - the vector iterator will do the wrong
> thing. With that, you get no invalidation of iterators on push or pops at
> either end (use vector assignment, not vector push/pop); constant time
> pushes and pops; no possibility of allocation failures; and you still have
> constant time random access.
> But, it takes a lot more code to do it...

You are right. First I was considering implement the cyclic buffer as a vector
adaptor, but I was too lazy. I just wanted to create any cyclic buffer. Later
if someone would be interested in I would optimize the implementation.
Probably now is the time to do it.

> Comments on the Code:
> 1) Overall, it is very good and very readable.
> 2) There are several missing typename keywords. Basically, everytime you
> have Container::xxx, it should read typename Container::xxx
> Regards,
> -Tom Wenisch
> Computer Architecture Lab
> Carnegie Mellon University

Jan Gaspar | jga_at_[hidden]
Whitestein Technologies |
Panenska 28 | SK-81103 Bratislava | Slovak Republic
Tel +421(2)5443-5502 | Fax +421(2)5443-5512

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