Deque impl.

[Andrei Alexandrescu]

On 1/31/13 1:01 PM, bearophile wrote:
> Andrei Alexandrescu:
>
>> Yah that's how C++'s deque is implemented. Blocks are of
>> statically-fixed size.
>
> I think I have suggested a better solution.

You mean this?

> I'd like a deque implemented as a growable circular queue
> (implemented with a dynamic array) of pointers to fixed-sized
> chunks, plus a "intrusive-like" freelist that keeps some of the
> last removed chunks.

The freelist used to be part of std::deque but was since eliminated. I'm 
not sure of the details of the growable circular queue, but probably the 
most awesome thing would be if you set out to implement it.


Andrei