Perché std :: deque non è un vettore con memoria riservata prima dell'indice 0?

Question

Per quanto ho capito, la motivazione alla base di deque è quella di fornire un contenitore ad accesso casuale con efficienza push_front.

Vantaggi del vettore comunemente citati rispetto a deque include traversal più veloce e at(), ma soprattutto la sua compatibilità con C, in quanto garantisce memoria contigua. Deque no, dal momento che è una raccolta di blocchi di memoria, ognuno dei quali contiene un numero di valori.

Sono confuso. Perché la deque non è costruita come un vettore ma con la memoria riservata prima dell'indice 0 oltre alla memoria riservata dopo l'indice size-1? Ciò garantirebbe memoria contigua, abilitare l'efficienza push_front ed evitare anche l'indirezione aggiuntiva durante la dereferenziazione degli iteratori.

Per ridurre al minimo lo spostamento durante l'inserimento, i valori contenuti da spostare dipenderanno dal punto di inserimento. Se si inserisce l'indice n prima del size()/2, spostare i valori fino a n a sinistra. Altrimenti spostare i valori a destra dopo n.

Che cosa mi è mancato è così importante che deque è una raccolta di matrici di valori e non un unico grande array?

Answer 1

According to Wikipedia, quello che stai descrivendo è davvero una possibile implementazione, almeno in generale.

Tuttavia, lo standard C++ impone requisiti che lo vietano essenzialmente come implementazione per std::deque; [deque.modifiers] afferma:

Un inserimento alle due estremità del deque ... non ha alcun effetto sulla validità dei riferimenti agli elementi del deque.

(Grazie a @BenjaminLindley!)