the input can grow to infinity (again partially due to it being user driven). And sparatic growths in a vector trigger reallocation. Although granted this can be minimized with clever calls to reserve().
In a list, every single insertion triggers allocation. vector does not need to allocate memory each time the user has requested to insert an element (in fact, reallocations are not as frequent as one could think). vector wins.
And since random access is pretty much the only advantageous reason to use vector over, say, list or deque, there's not much point to using vector.
It's not the only vector's advantage over other containers.
My question would be why did you recommend vector?
Perhaps because of one thing constantly overlooked by people who "care" about performance, but never measure it - vectors (arrays in general) have the best possible cache locality. Lists (unless unrolled) don't have any. Sometimes this can have tremendous impact on performance, so it could be - and sometimes actually is - faster to use vector rather than list, even though the computational complexity will be worse.
