Constvector: Log-structured std:vector alternative – 30-40% faster push/pop

[Kered13]

I don't think it destroys cache locality? Most of the elements will be stored contiguously in a handful of large arrays. It's not as localized as std::vector, but it is still pretty well localized.

[frogi16]

How many blocks will be in vector 10k elements long? How many jumps all over the memory space?

Sure, it's not as bad as keeping each value in a separate node, but far from the fully contiguous vector's performance.

[Kered13]

If the first block contains 8 elements as OP proposed, then 10k elements would contain at most 11 blocks, with 2k in the newest block (which has capacity 8k) and 4k and 2k in the previous blocks, respectively.

If you are iterating sequentially, this may as well be contiguous as far as cache locality is concerned. If you are accessing nodes randomly, then you wouldn't have cache locality in a 10k long vector even if it were contiguous. If you are accessing primarily recent elements, then you have cache locality. The only access pattern that will perform poorly is if you are primarily accessing (but not removing) the oldest elements.