Perché il libC++ std :: vector internamente mantiene tre puntatori invece di un puntatore e due dimensioni?

Question

Sto osservando l'implementazione di std::vector in libC++ e ho notato che mantiene internamente tre puntatori (uno per l'inizio, uno alla fine e uno alla fine della memoria allocata) invece di quello che farei istintivamente , cioè un puntatore all'inizio e due membri size e capacity.

Ecco il codice da libca ++ <vector> (ignorare la coppia compressa, so cosa significa).

pointer         __begin_; 
pointer         __end_; 
__compressed_pair<pointer, allocator_type> __end_cap_; 

Ho notato che anche altre librerie standard fanno lo stesso (ad esempio Visual C++). Non vedo alcun motivo particolare per cui questa soluzione dovrebbe essere più veloce dell'altra, ma potrei sbagliarmi.

Quindi c'è una ragione particolare per cui la soluzione "tre puntatori" è preferita alla "puntatore + dimensioni"?

Answer 1

È perché la logica è che le prestazioni devono essere ottimizzate per gli iteratori, non per gli indici.
(In altre parole, le prestazioni dovrebbe essere ottimizzato per begin()/end(), non size()/operator[].)
Perché? Perché gli iteratori sono puntatori generalizzati, e quindi C++ ne incoraggia l'uso, e in cambio assicura che le loro prestazioni corrispondano a quelle dei puntatori raw quando i due sono equivalenti.

capire perché si tratta di un problema di prestazioni, notare che il tipico for ciclo è il seguente:

for (It i = items.begin(); i != items.end(); ++i) 
    ... 

Tranne nei casi più banali, se abbiamo mantenuto traccia di dimensioni, invece di puntatori, ciò che sarebbe accaduto è che il confronto i != items.end() si trasformi in i != items.begin() + items.size(), prendendo più istruzioni di quanto ci si aspetterebbe. (In molti casi, l'ottimizzatore ha difficoltà a scomporre il codice.) Questo rallenta drasticamente le cose in un ciclo stretto, e quindi questo design viene evitato.

(Ho verificato che si tratta di un problema di prestazioni durante il tentativo di scrivere la mia sostituzione per std::vector.)

---

Edit: Come Yakk indicate nei commenti, utilizzando gli indici invece di puntatori possono anche causare la generazione di un moltiplicazione istruzione quando la dimensione degli elementi non sono potenze di 2, che è piuttosto costoso e notevole in un ciclo stretto. Non ho pensato a questo quando ho scritto questa risposta, ma è un fenomeno che mi ha morso prima (ad esempio vedi here) ... la linea di fondo è, in un ciclo stretto, tutto ciò che conta.

Answer 2

Immagino che sia principalmente una questione di velocità. Durante l'iterazione sul set, le istruzioni generate per il controllo dei limiti sarebbero semplicemente un'istruzione di confronto con il puntatore finale (e forse un carico), piuttosto che un carico, un add e un confronto (e forse anche un altro carico).

Quando genera iteratori per end() e begin(), il codice sarebbe anche essere solo return pointer;, piuttosto che return pointer + offset; per end().

Queste sono ottimizzazioni molto minori, ma la libreria di modelli standard è concepita per essere utilizzata nel codice di produzione in cui ogni ciclo conta.

PS: per quanto riguarda i diversi compilatori che lo implementano nello stesso modo: esiste un'implementazione di riferimento che la maggior parte (tutti?) Dei produttori di compilatori basano sulle loro implementazioni STL. È probabile che questa particolare decisione progettuale sia parte dell'implementazione di riferimento, ed è per questo che tutte le implementazioni che hai guardato gestiscono i vettori in questo modo.

Answer 3

È più conveniente per gli implementatori.

dimensioni Memorizzazione fa esattamente un'operazione più facile da implementare: size()

size_t size() { return size_; } 

d'altra parte, fa altro più difficile da scrivere e rende il riutilizzo di codice più difficile:

iterator end() { return iterator(end_); } // range version 
iterator end() { return iterator(begin_ + size_); } // pointer + size version 

void push_back(const T& v) // range version 
{ 
    // assume only the case where there is enough capacity 
    ::new(static_cast<void*>(end_)) T(v); 
    ++end_; 
} 

void push_back(const T& v) // pointer + size version 
{ 
    // assume only the case where there is enough capacity 
    ::new(static_cast<void*>(begin_ + size_)) T(v); 
    // it could use some internal `get_end` function, but the point stil stands: 
    // we need to get to the end 
    ++size_; 
} 

Se dobbiamo trovare la fine comunque, potremmo salvarla direttamente - è comunque più utile della taglia.