[boost] Cyclic Queue Requirements and Description

From: Sasha Goldshtein (goldshtn_at_[hidden])
Date: 2004-02-17 12:59:29

Good day,

Assume the following requirements from a container:
- O(logn) find operation
- O(1) random access operation
- O(logn) insert, O(logn) delete of a block of SEVERAL elements at a 
random position in the container

This container can be described as a cyclic queue - a queue that you 
push items at its back and remove items from its front, but retaining 
the ability to randomly access any element in the container according to 
its index.  The cyclic nature of the queue is in that if gaps are 
created due to element removal, then the inserts will first attempt 
filling those gaps (and expanding the queue IN THE MIDDLE if necessary) 
prior to moving to the back of the queue, enlarging it and copying the 
elements.

The following 'diagram' demonstrates the idea:

x x x x x x x     x x x x x x x x x x x x
(1)	      (2)			(3)

(1) - elements are normally removed from here.
(2) - a gap that was created due to removal of two elements from the 
middle of the container.
(3) - elements are normally inserted here, unless there are gaps in the 
container.

Now if we want to insert two elements, we can just put them instead of 
(2) and we're done.  But what if we want three?  The requirement is to 
expand the queue to fill the gap and make room for the elements - i.e. 
insert at (2) but make room, at (2), for another element.

I hope the requirements are clear :)

Anyhow, I've had an idea of implementing this as a linked list of 
blocks, each being moved to the free pool when fully deallocated and 
pushed at the end of the queue from the free pool if all end blocks are 
full, if needed.

Is there any interest in this sort of container?
Is there any existing / pending library in Boost or elsewhere that 
provides an implementation of a similar concept?
Have you any ideas that can make the whole problem go away by using some 
combination of the standard containers?

Thanks in advance to all,
Sasha Goldshtein.