example - ¿Cómo se implementa std:: vector insert? C++

vector insert c++

Question

Recientemente estuve releyendo el estándar ISO C ++ y encontré una nota muy interesante:

Tenga en cuenta que para std::vector , la única restricción en el tipo T de std::vector<T> es que el tipo T debe tener un constructor de copia. En realidad, si la memoria del vector está llena durante la inserción, asigne una nueva memoria de size = 2 * oldSize (esto depende de la implementación) y luego copie los elementos antiguos e inserte ese elemento.

¿¿Pero espera??

Para asignar nueva memoria de tipo, necesitamos algo como esto, ptr = new T[2*size];

1. ¿Cómo se hace esto, porque el tipo T puede no tener un constructor predeterminado?
2. Luego, Asignación, después de asignar la memoria, debemos asignar los valores antiguos a la nueva memoria, ¿verdad?
3. Para tener en cuenta estas 2 cosas, ¿cómo hace std::vector con "SOLO COPY CONSTRUCTOR"? ¿Qué lenguajes de implementación y lenguaje se utilizan?

Answer 1

Como regla general, los contenedores estándar separan la asignación de la inicialización (al igual que cualquier contenedor que escriba también). Los contenedores estándar utilizan un mecanismo muy complejo para permitir la personalización tanto de la asignación como de la inicialización, pero en el caso predeterminado, se reduce a usar las funciones de operator new / operator delete para asignar la memoria, la ubicación nueva para inicializarla y una Llamada explícita al destructor para destruir los objetos. En otras palabras, insteaad de la secuencia:

p = new T[n];
//  ...
delete [] p;

usa:

p = operator new( n * sizeof( T ) );
for ( int i = 0; i != n; ++ i ) {
    new ( p + i ) T( otherValue );
}

//  ...
for ( int i = 0; i != n; ++ i ) {
    p->~T();
}
operator delete( p );

(Esta es una simplificación radical, para mostrar el concepto básico. En la práctica, será más complejo, por ejemplo, por razones de seguridad).

Answer 2

Piense en emplace_back (): lo más probable es que el vector asigne una nueva porción de memoria unificada, luego ejecute una nueva ubicación para copiar y construir los objetos en el lugar.

Answer 3

Se realiza con una llamada a la función de asignador allocate () para obtener memoria en bruto y siguiendo la llamada a la construcción del asignador (iterador, val) para construir un elemento por copia utilizando una ubicación nueva , es decir, algo similar a esto

/* approach similar to std::uninitialized fill taken */
template<typename T, typename A >
vector<T,A>::vector( size_type n, const T& val, const A& a) : alloc( a)  // copy the allocator
{
    /* keep track of which elements have been constructed
     * and destroy those and only those in case of exception */
    v = alloc.allocate( n); // get memory for elements
    iterator p;             // declared before try{} so it is still valid in catch{} block

    try {
        iterator end = v + n;
        for( p = v; p != end; ++p)
            alloc.construct( p, val); /* construct elements (placement new):
                                      e g. void construct( pointer p, const T& val) 
                                      { ::new((void *)p) T( val); } */
        last = space = p;
    } catch( ...) {
        for( iterator q = v; q != p; ++q)
            alloc.destroy( q);       /* destroy constructed elements */
        alloc.deallocate( v, n);     /* free memory */
        throw;                       /* re-throw to signal constructor that failed */
    }
}

En C ++, el asignador se utiliza para aislar a los implementadores de algoritmos y contenedores que deben asignar memoria de los detalles de la memoria física.

También se puede tomar el enfoque utilizando uninitialized_fill directamente:

 std::uninitialized_fill( v, v + n, val); /* copy elements with (placement new):
                                             e g. void construct( pointer p,
                                                                  const T& val) 
                                             { ::new((void *)p) T( val); } */

Esto se describe con más detalles en "C ++ ... 3rd edition" de Bjarne Stroustrup. Here hay una muestra escrita basada en esto.