[Someone]

'All the data' most of the time are references to all the data.

Also, I would not reallocate, but allocate at max size or, possibly, half size and grow if needed.

With that change, once you access the array, you likely have all pointers to shift in your level 1 cache.

Because of that, I expect it to be plenty fast enough.

(Hm, are there CPUs that have instructions for shifting parts of cache lines around?)