Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk