tamaño - vector c++

¿Por qué std:: vector reserve no "duplica" su capacidad, mientras que resize hace?

Question

Acabo de descubrir que std::vector<T>::resize "dobla" su capacidad incluso cuando cambia el tamaño de un elemento por encima del tamaño actual:

std::vector<int> v(50);
v.resize(51);
std::cout << v.capacity() << std::endl;

Este programa genera 100 con GCC y Clang, y 75 con Visual C ++. Sin embargo, cuando cambio de resize a reserve :

std::vector<int> v(50);
v.reserve(51);
std::cout << v.capacity() << std::endl;

La salida es 51 con los tres compiladores.

Me pregunto por qué las implementaciones usan una estrategia de expansión diferente para resize y reserve . Parece inconsistente, y esperaría el mismo comportamiento aquí.

Solo estoy agregando un enlace a una motivación para mi pregunta, donde se informa el impacto en el rendimiento: ¿Por qué los vectores C ++ STL son 1000 veces más lentos al hacer muchas reservas?

Agregar una cita de C ++ 11 Standard para aclarar los requisitos de reserve ; §23.3.6.3 (2):

Después de la reserve() , la capacity() es mayor o igual al argumento de reserve si ocurre la reasignación ...

Algunos pensamientos adicionales: desde C ++ 11 Standard:

Complejidad: la complejidad es lineal en la cantidad de elementos insertados más la distancia hasta el final del vector.

Lo que, efectivamente, implica una complejidad constante (amortizada) para insertar un solo elemento al final. Sin embargo, esto se aplica solo a los modificadores vectoriales , como push_back o insert (§23.3.6.5).

resize no está listado entre modificadores. Se enumera en §23.3.6.3 sección de capacidad vector . Y no hay requisitos de complejidad para resize .

Sin embargo, en la sección de resumen de vector (§23.3.6.1), está escrito:

( vector ) soporta (amortigua) operaciones de inserción y borrado de tiempo constante al final

La pregunta es si el resize(size()+1) se considera "inserción al final" .

Answer 1

¿Por qué esperarías que se comportaran de la misma manera? reserve se utiliza para preasignar el espacio que utilizará más adelante, con la expectativa de que el usuario tenga un buen manejo del tamaño final esperado del contenedor. resize es simplemente una asignación normal, por lo que sigue el enfoque normal, eficiente de velocidad, de aumentar geométricamente el espacio asignado al contenedor.

Los contenedores aumentan de tamaño mediante pasos multiplicativos para reducir el número de asignaciones necesarias y así mantener la velocidad y reducir la fragmentación de la memoria. La duplicación es la más común, pero algunas implementaciones usan pasos de 1.5 (por ejemplo, MSVC) que intercambian asignaciones incrementadas para un menor espacio desperdiciado dentro de cada contenedor.

Pero, si el usuario ya le dijo a la biblioteca qué tan grande creen que será el contenedor, al generar reserve , no es necesario asignar espacio en exceso, sino que puede confiar en que el usuario lo haya llamado con el número correcto. Es una reserve que tiene el comportamiento inusual, no el cambio de resize .

Answer 2

Cuando resize más de lo que hay capacidad, ya "demuestras" que no quieres reservar la capacidad adecuada. Por otro lado, si usa la reserve , explícitamente solicita la capacidad correcta. Si la reserve usaría la misma estrategia que resize no habría forma de reservar solo la cantidad correcta.

En este sentido, resize sin reserve es para los flojos o en caso de que no sepas la cantidad exacta para reservar. Llame a reserve si sabe qué capacidad necesita. Eso es dos escenarios diferentes.

PD: como señaló StoryTeller, tampoco se requiere reservar para reservar la cantidad exacta que se solicita según el estándar. Sin embargo, creo que mi principal argumento aún se mantiene: resize (sin reserve ) y reserve están pensados ​​para diferentes escenarios, donde puedes dar una idea de cuánto quieres reservar o no te importa la capacidad real y solo quieres tener el Contenedor del tamaño de lo que pides.

Answer 3

Por lo que puedo decir, no se requiere resize ni reserve para tener el comportamiento demostrado. Sin embargo, ambos tienen permitido dicho comportamiento, aunque ambos podrían asignar la cantidad exacta, y ambos podrían multiplicar la asignación anterior en lo que respecta al estándar.

Cada estrategia de asignación tiene sus ventajas. La ventaja de asignar una cantidad exacta es que no tiene una sobrecarga de memoria cuando se conoce previamente la asignación máxima. La ventaja de multiplicar es que mantiene la propiedad constante amortizada cuando se combina con operaciones de inserción de extremo.

El enfoque elegido por las implementaciones probadas tiene la ventaja de que permite ambas estrategias al redimensionar. Para usar una estrategia, uno puede reservar y luego redimensionar. Para usar el otro, simplemente cambia el tamaño. Por supuesto, uno debe conocer el comportamiento no especificado para aprovechar esto. Esta ventaja puede o no ser el razonamiento detrás de la elección de estas implementaciones.

Se podría considerar una falla de la API vectorial, tal como se especifica en la norma, que no es posible expresar el comportamiento de reasignación previsto (de una manera que esté garantizada por la norma).

Answer 4

reserve cambia la capacidad, mientras que el cambio de resize cambia el size .

capacity es la cantidad de elementos para los que el contenedor ha asignado espacio actualmente.

size es la cantidad de elementos en el contenedor.

Cuando asigna un vector vacío obtiene una capacity predeterminada (espacio AKA). El tamaño sigue siendo 0 y cuando agrega elementos al vector, aumenta su tamaño. Cuando el tamaño es igual a la capacidad y agrega más elementos, la capacidad debe crecer (generalmente duplicarse).

El problema con el vector es que garantiza la memoria secuencial, lo que significa que cada nuevo crecimiento de asignación necesitará también una copia de la asignación anterior a la nueva, en caso de que no haya espacio para el nuevo tamaño de asignación en el área de memoria asignada anterior.

Aquí la reserve puede ayudar, si conoce los elementos máximos en el vector. Cuando use reserve , solo habrá una asignación y ninguna copia de memoria, a menos que pase los artículos reservados.

Cuando dices el recuento reservado exacto, obtienes la memoria exacta que pediste. Cuando acaba de agregar elementos (incluso con el cambio de tamaño, no dice que no agregaría más elementos).

Answer 5

resize es necesario para seguir una estrategia de reasignación exponencial para cumplir con su garantía de complejidad (lineal en la cantidad de elementos insertados ). Esto se puede ver considerando que el resize(size() + 1) se requiere para tener una complejidad constante amortizada, por lo que debe seguir un crecimiento exponencial por la misma razón que push_back (complejidad constante amortizada) debe crecer exponencialmente.

Se permite que una implementación de reserve siga la estrategia de asignación que quiera, ya que su único requisito de complejidad es que sea lineal en la cantidad de elementos presentes . Sin embargo, si una implementación fuera, por ejemplo, redondear a la siguiente potencia de dos, esto sería ineficiente en el espacio (y sorprendente) en el caso de que el usuario sepa exactamente cuánta memoria se requiere y podría complicar la transferencia si el usuario llega a confía en este comportamiento. La latitud en el Estándar se ejerce mejor en los casos en que no hay ineficiencia espacial, por ejemplo, al redondear las asignaciones al tamaño de la palabra, si el asignador opera en esa granularidad.