[boost] Re: Cyclic Queue Requirements and Description

From: Sasha Goldshtein (goldshtn_at_[hidden])
Date: 2004-02-21 12:32:38

> this sounds like a solution in search of a problem.
> I like the O(logn) find, insert, and delete.
> I'm baffled by the insert "either at the end if no deletions have 
> occurred recently, or somewhere in the middle". (what problem generates 
> this requirement)

My intent wasn't clear.  What I meant is that if there is a gap in the 
middle, then it should be filled (there may be some consideration of 
resizing efficiency, or none) - it's not a question of whether or not a 
delete has "ever" occurred.  So if there is no gap - then the insert is 
at the end, and if there is a gap - it should be filled.

> Do the indexes for an element AFTER (2) above change when the delete 
> occurs? how about pointers, references and iterators?

The indexes DO change, but iterators and references should probably 
remain unchanged...

I've looked at the implementation of the circular buffer that Pavel has 
posted a reference to - and it does not fulfill the above requirements...

Thanks again for the comments.