Usando std::vector::reserve siempre que sea posible

En C++, los vectores son arrays dinámicas. A diferencia de las arrays, no tienen un tamaño fijo. Pueden crecer o encogerse según sea necesario. A los vectores se les asigna memoria en bloques de ubicaciones contiguas. Cuando la memoria asignada para el vector no alcanza para almacenar nuevos elementos, se asigna un nuevo bloque de memoria al vector y todos los elementos se copian desde la ubicación anterior a la nueva ubicación. Esta reasignación de elementos ayuda a que los vectores crezcan cuando sea necesario. Sin embargo, es una operación costosa y la complejidad del tiempo involucrado en este paso es lineal. La clase std::vector proporciona una reserva de función útil que ayuda al usuario a especificar el tamaño mínimo del vector. Indica que el vector se crea de tal manera que puede almacenar al menos el número de elementos especificados sin tener que reasignar la memoria.

estándar::vector::reserva

void reserve(size_type n)
Return Type: none
Arguments: n which denotes the no of elements to be stored in vector

Requests that vector is large enough to store n elements in the least. 
If the current vector capacity is less than n, then reallocation will 
take place. In other cases, reallocation will not happen. Function does
not modify existing elements in the vector

 Cada objeto vectorial tiene dos parámetros: tamaño y capacidad. El tamaño indica el número de elementos almacenados actualmente en el vector, mientras que la capacidad es el número máximo de elementos que el vector puede almacenar sin reasignación. Evidentemente capacidad >= tamaño. Cuando el vector se queda sin espacio para almacenar nuevos elementos, es decir, cuando el tamaño supera la capacidad, la biblioteca en tiempo de ejecución solicitará memoria nueva del montón y, una vez que se haya asignado la memoria, copiará todos los elementos del vector desde sus direcciones anteriores al dirección de memoria recién asignada. Una llamada a la función reserve modifica el parámetro de capacidad del vector y, por lo tanto, el vector solicita suficiente memoria para almacenar el número especificado de elementos. Aquí hay un programa para demostrar la mejora del rendimiento que se puede obtener mediante el uso de la función de reserva. En este programa, llenamos dos vectores con una gran cantidad de elementos y contamos el tiempo necesario para realizar este paso. Para el primer vector, no especificamos la capacidad, mientras que para el segundo vector especificamos la capacidad usando reserve(). 

Complejidad del tiempo: lineal O (N)

// CPP program to demonstrate use of
// std::vector::reserve
#include <chrono>
#include <iostream>
#include <vector>
 
using std::vector;
using std::cout;
using namespace std::chrono;
 
int main()
{
    // No of characters
    int N = (int)1e6;
 
    vector<int> v1, v2;
 
    // Reserve space in v2
    v2.reserve(N);
 
    // Start filling up elements in v1
    // To measure execution time in C++, refer below
    // https://www.geeksforgeeks.org/measure-execution-time-function-cpp/
 
    auto start = high_resolution_clock::now();
    for (int i = 0; i < N; ++i)
        v1.push_back(i);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
 
    cout << "Method I took " << duration.count() << " microseconds\n";
 
    // Start filling up elements in v2
    start = high_resolution_clock::now();
    for (int i = 0; i < N; ++i)
        v2.push_back(i);
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);
 
    cout << "Method II took " << duration.count()
         << " microseconds \n";
 
    return 0;
}

Salida: (dependiente de la máquina)

Method I took 18699 microseconds
Method II took 16276 microseconds 

Nota: Se garantiza que reservar espacio de antemano llevará menos tiempo que intentar insertar los elementos sin especificar el tamaño del vector. Además, agrega utilidad semántica al código y sabemos al menos qué tan grande será el vector.