This approach is still actually suboptimal from a spatial efficiency standpoint, wasting half or a third, depending on your chosen factor, of memory whenever yo

This approach is still actually suboptimal from a spatial efficiency standpoint, wasting half or a third, depending on your chosen factor, of memory whenever you push that key Nth element on to the back. The real question is, why do people use completely contiguous memory so much when they really don't need to? For I/O we have nice APIs like readv()/writev() which deal with segmented buffers just fine... and you really don't need humongous contiguous vectors to get all of the benefits out of your CPU cache... This paper details another approach that has much of the same benefits if you don't need completely contiguous storage, and only wastes O(sqrt(N)) memory at a time, resulting in much smoother allocation while still maintaining O(1) append operations. https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf