[RFC] Re: How does std::deque work currently?

[Dhruv Matani]

On Wed, 2004-01-14 at 15:16, Jonathan Wakely wrote:
> On Wed, Jan 14, 2004 at 03:01:28PM +0530, Dhruv Matani wrote:
> 
> > After reading the source, it seems that something like this is happening
> > in the current version if std::deque:
> [snip]
> > I think that my understanding of erase/insert is incorrect, since the
> > standard says that erase/insert should be constant time (I think)
> > 
> > Please correct me if I'm wrong.
> 
> I can't comment on all your points, but the standard says that deque
> guarantees (amortized) constant time for insert/erase at the beginning or
> end of the sequence. Insertion in the middle is linear in n, where n is
> the minimum of the distance to the beginning and to the end.
> The deque container is a model of Front Insertion Sequence and Back
> Insertion Sequence.

Ok, thanks! So, it's only for the front and back, and that too amortized
conatant time as expected (sorry I did not mention the word amortized
earlier), because obviously, some time the map would need to be
reallocated.

Now, I was wondering if it would be feasible to make the map point to
only 1 element instead of a collection of elements? Obviously, the
implementor of deque must have thought of this, and then only
implemented the current deque, so I woudl like to know what's the
rationale behind having the block. I'm making a few gueses let me know
if they hold and whether there's anything more to it:

Advantages:
1. Number of elemnts in the map array is less.
2. Cache efficiency for access of adjacent elements.

Disadvantages:
1. Moving the elemnts involves copying the actual object instead of only
the pointer in the map.
2. Erase/Insert, which work in the middle of the deque will suffer in
performance.
3. Added complexity of the deque's iterator.
4. Because of (3), runs through deque will be slower compared to those
in vector (I can't comment on how much slower they will be).

It seems that the algorithm for choosing the block/node size is a simple
function that is inversely proportional to the sizeof(_Tp). If that's
correct, then something like std::string when used with std::deque would
yield a decent sized block/node, and then erasing elements from the
middle would involve copying many elements right?


Now, I'm writing the following assuming that my initial assumptions
about the deque's implementation holds.

We could implement an allocator that actually tries to make sense of the
hint parameter passed to it, and return memory that is around that
region? If so, then we can keep the cache intact while implementing the
deque as a map pointing to only one object. This would mean:

1. Get the memory for the block/node, using this specialized allocator.
2. (1) Would try to guarantee that the cache data is preserved when the
user does a straight run on a deque.
3. Reduces the complexity of the iterators.
4. Increases memory consumption in terms of the map.
5. Makes Insert/Erase work faster. Instead of copying whole objects,
copy only the pointers in the map

> jon
-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/