Originariamente inviato da MItaly
Se sai in anticipo quanti dati ci andrai a mettere dentro ti basta usare vector.reserve prima di richiamare i vari push_back, oppure vector.resize e poi direttamente l'operatore [].

È un'operazione che viene ammortizzata nel tempo, man mano che si va avanti con i push_back tra l'altro le dimensioni del blocco allocato aumentano (da quanto ho visto in genere si va raddoppiando). Prendiamo pure il caso estremo di un vector che parta con capacità 1; il numero delle riallocazioni va con il logaritmo delle dimensioni finali. In ogni caso, come detto, basta un reserve all'inizio e il problema non si pone più.

Mi pare una pessima idea. Le liste vanno bene se si devono inserire elementi a metà, nel semplice accodamento hai solo svantaggi: costo delle allocazioni per i singoli elementi, spreco di memoria per i puntatori al precedente e successivo elemento; una lista di interi finirebbe con prendere più del triplo dello spazio di memoria rispetto ad un equivalente vettore (assumendo sizeof(void*)==sizeof(int)).
In realtà non è proprio un raddoppio delle dimensioni, ma anche fosse ciò non toglie che più cerchi rapidità più ti dovresti allontanare dall'utilizzo di un vector. Senza considerare se se le dimensioni sono piuttosto considerevoli reallocare uno spazio simile richiede risorse davvero eccessive per qualsiasi operazione direi. Ovvio che se conosci a priori il numero di elementi ridimensionare il vettore all'inizio è una valida alternativa, ma anche in questo caso una resize è più dispendiosa di un'allocazione "standard" con new/malloc (inizializzando anche gli elementi del vettore a 0, operazione che se necessaria viene svolta molto più velocemente dalla memset).

In definitiva i vector vanno molto bene per compiti per i quali sono stati pensati, ossia per i casi più generali possibili quindi niente a che vedere con operazioni specifiche e volutamente performanti.

Stack, queue e strutture dati analoghe implementate attraverso l'utilizzo di liste concatenate richiedono una maggior analisi precedente per verificare se effettivamente possono avere vantaggi rispetto all'utilizzo di un vettore. Quindi dipende sempre da cosa si deve effettivamente fare, come sempre d'altronde.