¿Cuál es el beneficio de usar la reserva cuando se trata de vectores? ¿Cuándo debería usarlos? No pude encontrar una respuesta clara sobre esto, pero supongo que es más rápido cuando se reserva por adelantado antes de usarlos.Beneficios del uso de la reserva() en un vector - C++
¿Qué dicen ustedes, gente más inteligente que yo?
Es útil si tiene una idea de cuántos elementos conservará finalmente el vector; puede ayudar al vector a evitar la asignación repetida de memoria (y tener que mover los datos a la nueva memoria).
En general, es probable que sea una optimización potencial de la que no deba preocuparse, pero tampoco es dañina (en el peor de los casos, usted perderá memoria si hace una estimación excesiva).
Un área donde puede ser más que una optimización es cuando desea asegurarse de que los iteradores existentes no se invaliden agregando nuevos elementos.
Por ejemplo, una llamada push_back() puede invalidar los iteradores existentes en el vector (si se produce una reasignación). Sin embargo, si ha reservado suficientes elementos, puede asegurarse de que no se produzca la reasignación. Esta es una técnica que no necesita ser utilizada con mucha frecuencia.
... y hacer repetidas secuencias de asignar/copiar/mover cuando el espacio disponible actualmente se agota puede llevar a la fragmentación del montón. –
"... asegúrese de que los iteradores existentes no se invaliden agregando nuevos elementos". esto es cierto para tipos * específicos de adiciones (el ejemplo push_back es uno de esos). Pero un 'insert()' invalidará todos los iteradores desde el punto de inserción, incluso con una amplia capacidad disponible (y, por supuesto, si la capacidad requiere un cambio de tamaño, todo se cae de la tabla). La versión extrema es, por supuesto, un 'insert (v.begin(), ...)' que invalida * todos * iterators * always *. Afortunadamente, hay mejores contenedores que vector para manejar eso si es un funcionamiento frecuente por el código de uno. – WhozCraig
Puede ser ... especialmente si va a agregar muchos elementos a su vector en el tiempo, y desea evitar la expansión de memoria automática que el contenedor hará cuando se agote el espacio disponible.
por ejemplo, copias de inserciones (es decir, std::vector::push_back) se consideran una ammortized O (1) o de constante de tiempo de proceso, pero eso es porque si se realiza una inserción en la parte posterior de un vector, y el vector está fuera del espacio, debe reasignar memoria para una nueva matriz de elementos, copiar los elementos antiguos en la nueva matriz y luego copiar el elemento que intenta insertar en el contenedor. Ese proceso es O (N), o complejidad de tiempo lineal, y para un vector grande, podría tomar bastante tiempo. El uso del método reserve() le permite preasignar la memoria para el vector si sabe que va a tener al menos cierto tamaño, y evita reasignar la memoria cada vez que se agota el espacio, especialmente si va a hacer una inserción hacia atrás dentro de algún código de rendimiento crítico en el que desea asegurarse de que el tiempo para realizar la inserción siga siendo un proceso de complejidad O (1) real y no incurra en una reasignación de memoria oculta para la matriz. De acuerdo, tu constructor de copia tendría que ser O (1) también complejo para obtener una verdadera complejidad O (1) para todo el proceso de inserción posterior, pero con respecto al algoritmo real para la inserción posterior en el vector por el propio contenedor , puede mantener una complejidad conocida si la memoria de la ranura ya está preasignada.
más rápido y ahorra memoria
Si push_back otro elemento, a continuación, un vector completo se suele asignar el doble de memoria que está utilizando actualmente - ya asignar + copia es caro
No sabe acerca de las personas más inteligentes que usted, pero yo diría que debe llamar al reserve con anticipación si va a realizar muchos trabajos en operaciones de inserción y ya sabe o puede estimar el número total de elementos, al menos en el orden de magnitud. Puede ahorrarte muchas reasignaciones en buenas circunstancias.
Si conoces el tamaño final del vector, entonces vale la pena usar la reserva.
De lo contrario, siempre que el vector se quede sin espacio interno, se volverá a dimensionar el almacenamiento intermedio. Esto generalmente implica doblar (o 1.5 * tamaño actual) el tamaño del búfer interno (puede ser costoso si haces esto mucho).
El bit caro real invoca el constructor de copia de cada elemento para copiarlo del búfer antiguo al búfer nuevo, y luego llama al destructor en cada elemento del búfer antiguo.
Si el constructor de copia es caro, puede ser un problema.
Si el constructor de copia es costoso, usar 'std :: deque' puede ser una mejor opción. http://www.gotw.ca/gotw/054.htm –
This excellent article explica en profundidad las diferencias entre los contenedores deque y vector. La sección "Experimento 2" muestra los beneficios de vector::reserve().
Aunque es una vieja pregunta, aquí está mi implementación para las diferencias.
#include <iostream>
#include <chrono>
#include <vector>
using namespace std;
int main(){
vector<int> v1;
chrono::steady_clock::time_point t1 = chrono::steady_clock::now();
for(int i = 0; i < 1000000; ++i){
v1.push_back(1);
}
chrono::steady_clock::time_point t2 = chrono::steady_clock::now();
chrono::duration<double> time_first = chrono::duration_cast<chrono::duration<double>>(t2-t1);
cout << "Time for 1000000 insertion without reserve: " << time_first.count() * 1000 << " miliseconds." << endl;
vector<int> v2;
v2.reserve(1000000);
chrono::steady_clock::time_point t3 = chrono::steady_clock::now();
for(int i = 0; i < 1000000; ++i){
v2.push_back(1);
}
chrono::steady_clock::time_point t4 = chrono::steady_clock::now();
chrono::duration<double> time_second = chrono::duration_cast<chrono::duration<double>>(t4-t3);
cout << "Time for 1000000 insertion with reserve: " << time_second.count() * 1000 << " miliseconds." << endl;
return 0;
}
Al compilar y ejecutar este programa, se da salida:
Time for 1000000 insertion without reserve: 24.5573 miliseconds.
Time for 1000000 insertion with reserve: 17.1771 miliseconds.
parece ser una cierta mejora con la reserva, pero no que el exceso de mejora. Creo que habrá más mejoras para los objetos complejos, no estoy seguro. Cualquier sugerencia, cambio y comentario son bienvenidos.
Gracias a todos por la respuesta. Además, ¿usar la reserva (20) significa que ahora hay 20 elementos o solo que se ha asignado la memoria para 20 elementos? –
Solo se ha asignado la memoria. La memoria no está inicializada. – Jason
'reserva()' agrega capacidad, pero no agrega elementos. Lo que devuelve 'size()' no cambiará (sin embargo, 'capacity()' devolverá al menos 20 en tu ejemplo). –