Deque impl.

[bearophile]

Andrei Alexandrescu:

> You mean this?

Yes, I meant that.


> I'm not sure of the details of the growable circular queue,

I meant something like this (but an optimization about memory 
pages is missing):

http://rosettacode.org/wiki/Queue/Usage#Faster_Version

The power-of-2 growable circular queue doesn't need to be a too 
much complex data structure because it doesn't contain the items, 
it contains the links to the fixed-sized chunks of items, so it 
grows/shrinks much more slowly.

The missing memory optimization:
http://en.wikipedia.org/wiki/Circular_queue#Optimization


> The freelist used to be part of std::deque but was since 
> eliminated.

For some usage patterns a freelist (used with an pointer carved 
out of the chunk itself) that keeps few of the last used chunks 
(it's usually not necessary to keep them all) is handy. For some 
other usages the freelist doesn't give you much, and it's just 
added complexity.

If you keep using the structure as a queue, you keep adding from 
one side and remove from the other. In this case the circular 
queue of pointers to chunks works well, but you risk freeing and 
adding blocks all the time, for no purpose. Even keeping and 
reusing just one free chunk, "moving" it from one end to the 
other, avoids all/most memory allocations during the steady 
length state.

Bye,
bearophile