On 1/31/13 12:16 PM, Dmitry Olshansky wrote:
Then the only layout left to propose is an array of blocks. Then indexing is done like: blocks[idx>>N][idx&mask] if block size is power of 2. Not half-bad and still O(1).
Yah that's how C++'s deque is implemented. Blocks are of statically-fixed size.
Andrei
