¿Cómo la adición y eliminación de elementos "reescala" los datos? ¿Cómo se calcula el tamaño del vector (creo que se realiza un seguimiento)? Cualquier otro recurso adicional para aprender sobre vectores sería apreciado.¿Cómo funciona C++ std :: vector?
En términos de tamaño, hay dos valores de interés para un std::vector: size, y capacity (accede a través de .size() y .capacity()).
.size() es la cantidad de elementos que están contenidos en el vector, mientras que .capacity() es la cantidad de elementos que se pueden agregar al vector, antes de que la memoria se reasigne.
Si .push_back() un elemento, el tamaño aumentará en uno, hasta que alcance la capacidad. Una vez que se alcanza la capacidad, la mayoría (¿todas?) Implementan, reasignan la memoria, doblando la capacidad.
Puede reservar una capacidad usando .reserve. Por ejemplo:
std::vector<int> A;
A.reserve(1); // A: size:0, capacity:1 {[],x}
A.push_back(0); // A: size:1, capacity:1 {[0]}
A.push_back(1); // A: size:2, capacity:2 {[0,1]}
A.push_back(2); // A: size:3, capacity:4 {[0,1,2],x}
A.push_back(3); // A: size:4, capacity:4 {[0,1,2,3]}
A.push_back(4); // A: size:5, capacity:8 {[0,1,2,3,4],x,x,x}
reasignaciones de memoria se produciría en las líneas 4, 5 y 7.
Escribí un vector en C++ hace aproximadamente un año. Es una matriz con un tamaño de conjunto (por ejemplo, 16 caracteres) que se expande en esa cantidad cuando sea necesario. Es decir, si el tamaño predeterminado es 16 caracteres y necesita almacenar Hi my name is Bobby, duplicará el tamaño de la matriz a 32 caracteres y luego almacenará la matriz de caracteres allí.
El vector normalmente tiene tres punteros. Si el vector nunca se usó, todos son 0 o NULL.
Cuando se inserta un elemento, el vector asigna un cierto almacenaje y establece sus punteros. Podría asignar 1 elemento, o podría asignar 4 elementos. O 50.
Luego inserta el elemento e incrementa el último puntero del elemento.
Cuando inserta más elementos de los asignados, el vector tiene que obtener más memoria. Sale y recibe algo. Si la ubicación de la memoria cambia, entonces tiene que copiar todos los elementos en el nuevo espacio y liberar el espacio anterior.
Una opción común para cambiar el tamaño es duplicar la asignación cada vez que necesita más memoria.
+1, no solo duplicar la memoria es un patrón común, sino que es "obligatorio" (\ *) cumplir con * la inserción y eliminación de tiempo constante amortizado al final *. (\ *) no es necesario doblar, pero el crecimiento exponencial sí lo es. –
La implementación de std::vector cambió ligeramente con C++ 0x y más tarde con la introducción de la semántica de movimientos (vea What are move semantics? para una introducción).
Al añadir un elemento a un std::vector que ya está completo, entonces el vector se cambia el tamaño consistente en un procedimiento de asignación de un nuevo, área de memoria más grande, moviéndose los datos existentes a la nueva vector, eliminando el antiguo espacio vector, y luego agregando el nuevo elemento.
std::vector es una clase de colección en la Biblioteca de plantillas estándar. Poner objetos en un vector, eliminarlos o vector realizar un cambio de tamaño cuando un elemento se agrega a un vector completo requiere que la clase del objeto sea compatible con un operador de asignación, un constructor de copia y una semántica de movimiento. (Ver type requirements for std::vector, así como std::vector works with classes that are not default constructible? para más detalles.)
Una forma de pensar en std::vector es como un estilo C array de elementos contiguos del tipo especificado cuando el vector se define que tiene algunas funciones adicionales para integrarlo en la Norma Ofertas de Biblioteca de plantillas. Lo que separa un vector de un estándar array es que un vector crecerá dinámicamente a medida que se agreguen los elementos. (Ver std::vector and c-style arrays, así como When would you use an array rather than a vector/string? por alguna discusión sobre las diferencias.)
Usando std::vector permite el uso de otros componentes de la biblioteca de plantillas estándar, tales como algoritmos así que usar std::vector viene con un buen número de ventajas sobre un estilo de C array como se llega a usar la funcionalidad que ya existe
Puede especificar un tamaño inicial si se conoce el máximo antes de tiempo. (Ver Set both elements and initial capacity of std::vector así como Choice between vector::resize() and vector::reserve())
Los fundamentos de std::vector representación física es de un conjunto de punteros utilizando memoria asignada desde el heap. Estos punteros permiten las operaciones reales de acceso a los elementos almacenados en el vector, el borrado de elementos de la vector, iterar sobre la vector, determinando el número de elementos, la determinación de su tamaño, etc.
Desde la representación física es memoria contigua , la eliminación de elementos puede provocar el movimiento de los elementos restantes para cerrar los huecos creados por la operación de eliminación.
Con C moderna ++ mover la semántica, la sobrecarga de std::vector se ha reducido de manera que es normalmente el contenedor predeterminado que se utiliza para la mayoría de las aplicaciones según lo recomendado por Bjarne Stroustrup en su libro The C++ Programming Language cuarta edición que discute C + +11.
Acabo de leer el código en el archivo de encabezado ''. La implementación difiere de una biblioteca a otra. –
Philipp
Cada vez que cambia el tamaño de un vector, Dios mata a un gatito. –
@Philipp: ¿Has intentado hacerlo? Se necesita bastante esfuerzo y dolor para revisar el código allí ... –