Cita:
Iniciado por lareto 
O sea: salvo los vectores de bool, que no lo requieren, el estándar garantiza que un vector almacene sus elementos en posiciones contiguas de memoria.
De hecho los vector<bool> no se consideran como STL.
Kutcher debe haberse confudido con deque, donde el contenedor no te garantiza la continuidad en memoria:
http://www.cplusplus.com/reference/deque/deque/
Y aún así el acceso a una posición aleatoria se hace en tiempo constante al igual que en vector.