Come viene implementato l'inserimento di std :: vector? C++

Question

Recentemente Stavo rileggendo norma ISO C++, e l'ho trovato molto interessante nota:

Si noti che per std::vector, l'unico vincolo del tipo di Tstd::vector<T> è quel tipo T deve avere costruttore di copia. In realtà, se la memoria del vettore è piena durante l'inserimento, viene allocata una nuova memoria di size = 2 * oldSize (dipende dall'implementazione), quindi copia i vecchi elementi in essa contenuti e inserisce quell'elemento.

Ma aspetta ??

Per allocare nuova memoria di tipo l'abbiamo bisogno di qualcosa di simile, ptr = new T[2*size];

1. come questo viene fatto, perché il tipo di T non può avere un costruttore di default?
2. Quindi assegnazione, dopo l'allocazione della memoria dobbiamo assegnare vecchi valori alla nuova memoria, giusto?
3. Per tenere conto di queste 2 cose, come fa std::vector a fare questo con "SOLO COSTRUTTORE DI COPIA?" Quali sono gli idiomi di implementazione e lingua utilizzati?

Answer 1

Come regola generale, i contenitori standard separano l'allocazione dall'inizializzazione (come qualsiasi contenitore che si scrive anche). I contenitori standard utilizzano un meccanismo molto complesso per consentire la personalizzazione sia assegnazione e l'inizializzazione, ma nel caso di default, si riduce a base alle operator new/operator deletefunzioni per allocare la memoria, nuova collocazione a inizializzarlo e una chiamata esplicita al distruttore per distruggere gli oggetti.In altre parole, insteaad di sequenza:

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

utilizza:.

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); 

(Questa è una radicale semplificazione, per mostrare il concetto di base In pratica, sarà più complesso, per motivi di sicurezza , ad esempio.)

Answer 2

Pensa a emplace_back(): molto probabilmente il vettore assegna un nuovo blocco di memoria unititializzata, quindi esegue il posizionamento nuovo per copiare-costruire gli oggetti sul posto.

Answer 3

Si esegue con una chiamata a allocatore funzione allocare() per ottenere memoria crudo e seguente chiamata allocatore costruzione (iterator, val) per costruire un elemento copiando utilizzando nuova collocazione, cioè qualcosa di simile a questo:

/* 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 */ 
    } 
} 

In C++ allocatore viene usato per isolare gli esecutori di algoritmi e contenitori che devono allocare memoria dai dettagli della memoria fisica.

avvicinamento con impiego uninitialized_fill direttamente può anche essere preso:

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); } */ 

Questo è descritto con maggiori dettagli in Bjarne Stroustrup di "C++ ... 3 ° edizione". Here è un esempio scritto in base a questo.