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.