The annoying thing about "reallocating" is that it's mostly the price of having the flat address space (and not dealing with 128-wide fat pointers). The virtual memory subsystem already juggles around physical pages to allow two non-overlapping virtual address ranges to transparently map to overlapping physical address ranges. The implementations of std::deque() from C++ standard library usually use the similar technique but it's arguably a bit silly since it essentially pushes a MMU-like system on top of an existing hardware one!
I don't think are current memory architecture is fundamental incompatible with a paging based vector. Doubling the size of pointers is expensive. However, given current RAM sizes, our existing 48-bit effective pointer size is already large enough. It isn't enough to give every allocation a massive amount of virtual address space to grow into. But it should be more than enough to seperate out actual memory allocation from virtual address space allocation.
This would mean a more complicated malloc, where you ask for both an actual memory allocation, and an amount of address space to be allocated. And will still require you to have some sense of the maximum size you might need in a given vector.
Also, it forces memory allocations to be multiples of the page size, which isn't always ideal.
