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
