The performance of vectors comes from iterating through them and letting the cpu prefetch items before you need them. Random access in a vector doesn’t really get you that if the vector is larger than your L1/L2 caches, which linked lists would be in anyway if you used them recently enough.

Interesting idea but how does C++ guarantee contiguous memory for a vector? I just don’t see how a data structure with an arbitrary, dynamic size can also reside in a contiguous range of address space.

When the array is resized, it’s moved to a new contiguous block of memory: everything is copied or moved over. See: https://stackoverflow.com/questions/8261037/what-happen-to-p...

Simple, you just allocate a bigger contiguous chunk of memory and copy the entire vector over when the current chunk maxes out.