Deque impl.

[bearophile]

Timon Gehr:

> As far as I can see, this just gets rid of a handful bitwise 
> and machine instructions and in return at least doubles the 
> address space requirements, also taking up cache-space (for 
> virtually indexed caches.)
>
> Does this actually improve performance?

I have not tried it (that linked code on Rosettacode doesn't have 
that "optimization"). When you try to create a data structure 
some benchmarking is required.

Regarding the memory requirements, that circular queue doesn't 
hold the items, only pointers to chunks of items (one chunk is 
like 2^16 bytes or 2^20 bytes long), so usually it uses only some 
kilobytes of memory. So wasting a bit of memory here is OK.

Bye,
bearophile