Capacidad inicial del vector en C ++

¿Cuál es la capacity() de un std::vector que se crea utilizando el constructor predeterminado? Sé que el size() es cero. ¿Podemos decir que un vector construido por defecto no llama a la asignación de memoria de stack?

De esta forma, sería posible crear una matriz con una reserva arbitraria utilizando una única asignación, como std::vector iv; iv.reserve(2345); std::vector iv; iv.reserve(2345); . Digamos que por alguna razón, no quiero comenzar el size() en 2345.

Por ejemplo, en Linux (g ++ 4.4.5, kernel 2.6.32 amd64)

 #include  #include  int main() { using namespace std; cout << vector().capacity() << "," << vector(10).capacity() << endl; return 0; } 

impreso 0,10 . ¿Es una regla o depende del proveedor de STL?

El estándar no especifica cuál debe ser la capacity inicial de un contenedor, por lo que confía en la implementación. Una implementación común iniciará la capacidad en cero, pero no hay garantía. Por otro lado, no hay forma de mejorar su estrategia de std::vector iv; iv.reserve(2345); std::vector iv; iv.reserve(2345); así que quédate con eso

Las implementaciones de almacenamiento de std :: vector varían significativamente, pero todas las que he encontrado comienzan desde 0.

El siguiente código:

 #include  #include  int main() { using namespace std; vector normal; cout << normal.capacity() << endl; for (unsigned int loop = 0; loop != 10; ++loop) { normal.push_back(1); cout << normal.capacity() << endl; } std::cin.get(); return 0; } 

Da el siguiente resultado:

 0 1 2 4 4 8 8 8 8 16 16 

bajo GCC 5.1 y:

 0 1 2 3 4 6 6 9 9 9 13 

bajo MSVC 2013.

Como pequeña adición a las otras respuestas, encontré que cuando se ejecuta bajo condiciones de depuración con Visual Studio, un vector construido por defecto aún se asignará en el montón aunque la capacidad comience en cero.

Específicamente, si _ITERATOR_DEBUG_LEVEL! = 0, el vector asignará un espacio para ayudar con la comprobación del iterador.

https://docs.microsoft.com/en-gb/cpp/standard-library/iterator-debug-level

Acabo de encontrar esto un poco molesto ya que estaba usando un asignador personalizado en ese momento y no esperaba la asignación adicional.

Por lo que entendí el estándar (aunque en realidad no podía nombrar una referencia), la instanciación del contenedor y la asignación de memoria se han desacoplado intencionalmente por una buena razón. Por lo tanto, tiene llamadas separadas y separadas para

  • constructor para crear el contenedor
  • reserve() para asignar previamente un bloque de memoria adecuadamente grande para acomodar al menos (!) un número dado de objetos

Y esto tiene mucho sentido. El único derecho de existir para la reserve() es darle la oportunidad de codificar posibles reasignaciones costosas al crecer el vector. Para ser útil, debes saber la cantidad de objetos que quieres almacenar o, al menos, debes saber adivinar. Si esto no le es más conveniente, manténgase alejado de la reserve() ya que simplemente cambiará la reasignación de la memoria desperdiciada.

Así que poner todo junto:

  • El estándar intencionalmente no especifica un constructor que le permita preasignar un bloque de memoria para un número específico de objetos (que sería al menos más deseable que asignar un “algo” fijo específico de implementación bajo el capó).
  • La asignación no debe ser implícita. Por lo tanto, para preasignar un bloque necesita hacer una llamada separada para reserve() y esto no tiene que ser en el mismo lugar de construcción (podría / debería ser, por supuesto, más tarde, después de que se dio cuenta del tamaño requerido para acomodar)
  • Por lo tanto, si un vector siempre preasignara un bloque de memoria de tamaño definido de implementación, esto frustraría el trabajo previsto de reserve() , ¿no es así?
  • ¿Cuál sería la ventaja de preasignar un bloque si el STL, naturalmente, no puede conocer el propósito previsto y el tamaño esperado de un vector? Sería bastante absurdo, si no contraproducente.
  • En su lugar, la solución adecuada es asignar e implementar un bloque específico con el primer push_back() ; si no lo ha sido previamente asignado explícitamente por reserve() .
  • En caso de una reasignación necesaria, el aumento en el tamaño del bloque también es específico de la implementación. Las implementaciones de vectores que conozco comienzan con un aumento exponencial de tamaño, pero limitarán la velocidad de incremento a un cierto máximo para evitar desperdiciar grandes cantidades de memoria o incluso soplarla.

Todo esto llega a su pleno funcionamiento y ventaja solo si no es perturbado por un constructor de asignación. Tiene valores predeterminados razonables para los escenarios comunes que pueden ser anulados a petición por reserve() (y shrink_to_fit() ). Entonces, incluso si el estándar no lo dice explícitamente, estoy bastante seguro de que asumir que un vector recién construido no preasigna es una apuesta bastante segura para todas las implementaciones actuales.

El estándar no especifica el valor inicial para la capacidad, pero el contenedor STL crece automáticamente para acomodar tantos datos como usted ingresa, siempre que no exceda el tamaño máximo (use la función de miembro max_size para saber). Para vector y cadena, el crecimiento se maneja con realloc cada vez que se necesita más espacio. Supongamos que desea crear un vector que contenga el valor 1-1000. Sin utilizar la reserva, el código típicamente dará como resultado entre 2 y 18 reasignaciones durante el ciclo siguiente:

 vector v; for ( int i = 1; i <= 1000; i++) v.push_back(i); 

Modificar el código para usar la reserva podría resultar en 0 asignaciones durante el ciclo:

 vector v; v.reserve(1000); for ( int i = 1; i <= 1000; i++) v.push_back(i); 

A grandes rasgos, las capacidades de vectores y cuerdas crecen en un factor de entre 1,5 y 2 cada vez.