I'd look at GCC's deque and see what what's going on there. LibC++ takes employs a similar heuristic.
i suppose, i is implemented as a linked list of nodes of a certain size?
Linked segments of contiguous memory. The number of objects per segment depend on object size.
also it may be better to remove any notion about `cache line size' or `page size' but replace it with `memory locality', which is a broader term and implies that experimenting with different `objects_per_group<>' may be interesting. although my feeling says me, that the default value of 8 will be the first and the last answer for 99% of all use cases ...
How would you specify locality? A metafunction on the object size and other configuration parameters (page size, cache line width, etc?). I'm won't doubt that you're right about 8 being a good default value, but I think you need to empirically demonstrate that the choice is right for a variety of reasonable object sizes (say, up to 32 bytes) and on both 32b and 64b systems. Andrew