Cómo se implementa vector en C++
Estoy pensando en cómo puedo implementar std::vector desde cero.
¿Cómo cambia el tamaño del vector?
Realloc solo parece funcionar para estucos viejos, o estoy equivocado?
8 answers
Es una simple clase templada que envuelve una matriz nativa. It does not use malloc/realloc. En su lugar, utiliza el asignador pasado (que por defecto es std::allocator).
El redimensionamiento se realiza asignando un nuevo array y copiando la construcción de cada elemento en el nuevo array desde el antiguo (de esta manera es seguro para objetos no POD). Para evitar asignaciones frecuentes, a menudo siguen un patrón de crecimiento no lineal.
UPDATE: en C++11, los elementos se moverán en lugar de copia construida si es posible para el tipo almacenado.
Además de esto, necesitará almacenar el "tamaño" y la "capacidad"actuales. Tamaño es cuántos elementos son realmente en el vector. La capacidad es cuántos podrían estar en el vector.
Así que como punto de partida un vector tendrá que verse algo así:
template <class T, class A = std::allocator<T> >
class vector {
public:
// public member functions
private:
T* data_;
typename A::size_type capacity_;
typename A::size_type size_;
A allocator_;
};
La otra implementación común es almacenar punteros a las diferentes partes de la matriz. Esto abarata el costo de end() (que ya no necesita una suma) muy ligeramente a expensas de una llamada size() marginalmente más cara (que ahora necesita una resta). En cuyo caso podría verse así:
template <class T, class A = std::allocator<T> >
class vector {
public:
// public member functions
private:
T* data_; // points to first element
T* end_capacity_; // points to one past internal storage
T* end_; // points to one past last element
A allocator_;
};
Creo que el libstdc++ de gcc utiliza este último enfoque, pero ambos enfoques son igualmente válidos y conformes.
NOTA: Esto está ignorando una optimización común donde la optimización de la clase base vacía se usa para el asignador. Creo que es un detalle de la calidad de la implementación, y no una cuestión de corrección.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-06-15 06:01:33
Cambiar el tamaño del vector requiere asignar un nuevo trozo de espacio, y copiar los datos existentes en el nuevo espacio (por lo tanto, el requisito de que los elementos colocados en un vector se pueden copiar).
Tenga en cuenta que no usa new []tampoco uses usa el asignador que se pasa, pero que se requiere para asignar memoria raw, no una matriz de objetos como new [] lo hace. Luego necesita usar placement new para construir objetos en su lugar. [Editar: bueno, técnicamente podrías usar new char[size], y usar eso como memoria cruda, pero no puedo imaginar a nadie escribiendo un asignador así.]
Cuando se agota la asignación actual y se necesita asignar un nuevo bloque de memoria, el tamaño debe aumentarse en un factor constante en comparación con el tamaño anterior para cumplir con el requisito de complejidad constante amortizada para push_back. Aunque muchos sitios web (y tales) llaman a esto duplicar el tamaño, un factor alrededor de 1.5 a 1.6 generalmente funciona mejor. En particular, esto generalmente mejora las posibilidades de reutilizar bloques liberados para asignaciones futuras.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-06-17 19:07:47
De Wikipedia, tan buena respuesta como cualquier otra.
Una implementación vectorial típica consiste, internamente, en un puntero a una matriz dinámicamente asignada, [2] y posiblemente miembros de datos la capacidad y el tamaño del vector. El tamaño del vector se refiere a el número real de elementos, mientras que la capacidad se refiere al tamaño de la matriz interna. Cuando se insertan nuevos elementos, si el nuevo tamaño del vector se hace más grande que su capacidad, reasignación ocurrir.[2][4] Esto normalmente hace que el vector asigne un nuevo región de almacenamiento, mueva los elementos previamente retenidos a la nueva región de almacenamiento, y liberar la vieja región. Porque las direcciones de la elementos cambian durante este proceso, cualquier referencia o iteradores a los elementos del vector quedan invalidados.[5] Uso de una invalidada la referencia provoca un comportamiento indefinido
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-04-19 04:35:28
Asigna un nuevo array y copia todo. Por lo tanto, expandirlo es bastante ineficiente si tienes que hacerlo a menudo. Use reserve () si tiene que usar push_back ().
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-06-17 18:44:07
Así: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_vector.h
(espejo oficial del ccg en github)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-08-15 22:41:14
Tendrías que definir lo que quieres decir con "estructuras viejas y simples."
Realloc solo crea un bloque de memoria no inicializada. No hace ninguna asignación de objetos. Para estructuras de C, esto es suficiente, pero para C++ no.
Eso no quiere decir que no puedas usar realloc. Pero si usted fuera a usarlo (tenga en cuenta que no estaría reimplementando std::vector exactamente en este caso!), usted necesita:
- Asegúrate de usar
malloc/realloc/freeconstantemente en toda tu clase. - Uso "placement
new" para inicializar objetos en su fragmento de memoria. - Llama explícitamente a los destructores para limpiar los objetos antes de liberar tu trozo de memoria.
Esto es en realidad bastante cercano a lo que vector hace en mi implementación (GCC / glib), excepto que usa las rutinas de bajo nivel de C++ ::operator new y ::operator delete para hacer la gestión de memoria raw en lugar de malloc y free, reescribe la rutina realloc usando estas primitivas, y delega todo este comportamiento a un objeto asignador que puede ser reemplazado con una implementación personalizada.
Dado que vector es una plantilla, en realidad debería tener su fuente para mirar si desea una referencia: si puede superar la preponderancia de guiones bajos, no debería ser demasiado difícil de leer. Si está en una caja Unix usando GCC, intente buscar /usr/include/c++/version/vector o más o menos.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-06-17 19:22:08
Puede implementarlos con la implementación de redimensionamiento de matrices. Cuando la matriz se llene, cree una matriz con el doble de tamaño y copie todo el contenido a la nueva matriz. No se olvide de eliminar la matriz antigua.
En cuanto a la eliminación de los elementos del vector, redimensionar cuando su matriz se convierte en un cuarto lleno. Esta estrategia evita cualquier fallo de rendimiento cuando se puede intentar la inserción y eliminación repetida a la mitad del tamaño de la matriz.
Se puede demostrar matemáticamente que el tiempo amortizado (Tiempo promedio) para inserciones sigue siendo lineal para n inserciones que es asintóticamente el mismo que obtendrá con una matriz estática normal.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-06-09 14:53:14
Realloc solo funciona en memoria de montón. En C++ normalmente quieres usar la tienda gratuita.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-06-17 18:44:31