Boost logo

Boost :

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

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

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.

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