paquetes - ¿Cómo se implementa C++ std:: vector?
r packages list (9)
Creo que el STL usa la opción n. ° 2 (o algo similar) porque se garantiza que std :: vector <> almacena los elementos en la memoria contigua.
Si está buscando una estructura de memoria que no necesite usar memoria contigua, mire std :: deque.
He estado usando std::vector mucho, y recientemente me hice esta pregunta: "¿Cómo se implementa std::vector ?"
Tenía dos alternativas:
1) Lista enlazada, y luego hacer que la API parezca tener acceso aleatorio (es decir, operator[] sobrecarga operator[] ).
2) Usar new , por ejemplo, Foo* temp = new Foo[20] : creo que hacen algo como esto, pero luego surge una pregunta más. ¿Siempre asignan un almacenamiento máximo ( uint32_t ) para dar acceso aleatorio? (Esto es ineficiente en términos de memoria).
¿O hay algo más que deba tener en cuenta?
Creo que es la tercera opción. No puede simplemente usar una new T[n] porque entonces tendría que construir tantos objetos como asigna. P.ej
std::vector<Foo> v;
v.reserve(10);
Si su implementación simplemente terminó haciendo un new Foo[10] entonces habría construido 10 instancias de Foo.
En su lugar, utiliza su asignador para asignar y desasignar memoria sin push_back (sin construir objetos), y según sea necesario (por ejemplo, cuando realmente push_back objetos) coloca instancias push_back en las ubicaciones de memoria correctas en su reserva utilizando colocación nueva y las elimina con explicito llama al destructor (algo que solo harías en combinación con la ubicación nueva). La clase de asignador proporciona los siguientes métodos para lo que supongo que las implementaciones de vectores usan
void construct(pointer p, const_reference val);
Returns:
new((void *)p) T(val)
void destroy(pointer p);
Returns:
((T*)p)->~T()
(El "retorno" probablemente debería decir "efecto" o similar).
Más sobre la colocación nueva
De lo que he leído en libros y de la funcionalidad de reserva y el requisito de que los elementos de vectores sean contiguos, esto es lo que creo que podría ser una posible forma de implementar Vector.
1) Los elementos de los vectores deben ser contiguos, admitiendo O (1) acceso aleatorio y los vectores deben ser compatibles con las matrices C. Esto solo implica que no hay listas enlazadas.
2) Cuando llamas a reserva, reserva memoria adicional. Pero la reserva sí llama
new T[newSize]
para reservar más memoria. De lo contrario, llamará al constructor predeterminado. Como uncleben explicó cuando se llama reserva, la clase vector simplemente asigna más memoria no inicializada usando su asignador (si es necesario) y copia construye nuevos objetos en esa memoria usando la colocación nueva (si se ha asignado más memoria)
3) Inicialmente, el vector tiene alguna capacidad predeterminada. para el cual se asigna memoria no inicializada cuando se construye el objeto vector
4) push_back copy construye el objeto en la primera ubicación disponible. Si es necesario, se debe asignar más memoria de manera similar a reservar
La Sección 23.2.4, ¶1 de la norma requiere que la aritmética de los punteros en un vector funcione de la misma manera que con los punteros en una matriz.
Los elementos de un vector se almacenan contiguamente, lo que significa que si v es un vector donde T es un tipo distinto de bool, entonces obedece a la identidad & v [n] == & v [0] + n para todos 0 <= n <v .tamaño().
Esto garantiza que el almacenamiento está en una matriz. Por supuesto, si cambia el tamaño de la matriz para que sea más grande, es posible que se mueva en la memoria.
No existe una matriz real en ninguna implementación decente (si es que no se puede usar ningún objeto sin un constructor predeterminado), sino solo la memoria bruta que se asigna. Se asigna de una manera que suele ser similar a duplicar cada vez que necesita expandirlo.
Luego, el vector usa la asignación in situ para llamar a los constructores de la clase en la ubicación correcta una vez que se usa realmente cada ranura.
Cuando hay una expansión intentará reasignarse en su lugar (pero esto es un poco tonto y normalmente no funciona, piense en la compactación de montón de Windows 98) pero generalmente terminará haciendo una nueva asignación y copiando todo.
Un vector stl estándar siempre está todo junto, pero no todas las implementaciones funcionan así (lo sé, habiendo escrito algunos de ellos). Probablemente ninguno sea exactamente una lista vinculada, sin embargo, tampoco.
No hay una sola forma en que se implemente. Las diferentes implementaciones pueden ser diferentes, siempre que se preserve la semántica y se satisfagan los requisitos.
En un momento dado, tiene que haber una matriz primitiva de T para satisfacer los requisitos de contigüidad. Sin embargo, cómo se asigna, crece, reduce y libera depende del implementador.
Puede leer la implementación usted mismo, está ahí en el archivo de encabezado.
Puedo decirte que ninguna implementación usa listas enlazadas. No son consistentes con los requisitos del estándar.
Se implementa mediante el uso de una matriz subyacente.
No es posible implementar un std::vector<T> con una lista vinculada porque el estándar garantiza que los elementos en la lista se mantendrán en la memoria contigua.
Una versión pedagógica (y por lo tanto simplificada) de un contenedor llamado "Vec" se trata en el Capítulo 11 del maravilloso libro (introductorio) "C ++ acelerado". Lo que describen es una versión simplificada de std :: vector, pero creo que vale la pena señalar que:
1) implementan su clase de plantilla en términos de una matriz,
2) discuten push_back en términos del truco (mencionado anteriormente) de asignar más espacio de almacenamiento de lo que es necesario, y volver para obtener más cuando se agoten, y
3) usan el asignador <T > para la gestión de la memoria. El nuevo operador no es lo suficientemente flexible en este contexto, ya que asigna e inicializa la memoria.
Repito, sin embargo, que esto no significa que las implementaciones actuales sean tan simples. Pero dado que "Accelerated C ++" está bastante extendido, los interesados pueden encontrar en el capítulo correspondiente una forma en que los objetos tipo vector se pueden crear, copiar, asignar y destruir.
EDITAR: en una nota relacionada, acabo de encontrar la siguiente publicación de blog de Herb Sutter en la que comenta una publicación anterior de Andrew Koenig, sobre si uno debería estar preocupado por si los elementos del vector son contiguos en la memoria: Cringe no: Vectores están garantizados para ser contiguos .
Usan una matriz dinámicamente asignada que se vuelve a generar según sea necesario. Es necesario utilizar algo así como una matriz para que los elementos queden contiguos en la memoria y garantizados por la norma.
Por cierto, una forma común de volver a crecer una matriz es duplicar el tamaño según sea necesario. Esto es así, si está insertando n ítems como máximo, solo se realizan recrecimientos O(log n) y como máximo se desperdicia O(n) espacio.
Puede leer una implementación para usted en SGI (donde STL se concibió originalmente).