Come fa deque hanno un ammortamento costante complessità temporale

Question

ho letto here dalla risposta accettata che una std :: deque ha la seguente caratteristica

1- Random access - constant O(1) 
2- Insertion or removal of elements at the end or beginning - amortized constant O(1) 
3- Insertion or removal of elements - linear O(n) 

La mia domanda riguarda il punto 2. Come può un deque avere un ammortizzato inserimento costante alla fine o all'inizio?

Capisco che uno std::vector ha una complessità a tempo costante ammortizzato per gli inserimenti alla fine. Questo perché un vettore è continguente ed è un array dinamico. Quindi, quando esaurisce la memoria per uno push_back alla fine, allocherà un intero nuovo blocco di memoria, copierà gli elementi esistenti dalla vecchia posizione alla nuova posizione e quindi eliminerà gli elementi dalla vecchia posizione. Questa operazione capisco è ammortizzata costante. Come si applica a un deque? Come possono essere ammortizzate le inserzioni nella parte superiore e inferiore di una deque. Avevo l'impressione che doveva essere costante O (1). So che una deque è composta da blocchi di memoria.

Answer 1

La normale implementazione di un deque è fondamentalmente un vettore di puntatori a nodi di dimensioni fisse.

Assegnazione chiaramente il nodo di dimensione fissa ha costante complessità, quindi è abbastanza facile da gestire - basta ammortizzare il costo di assegnazione di un singolo nodo attraverso il numero di elementi in quel nodo per ottenere una complessità costante per ogni.

Il vettore della parte dei puntatori è ciò che è (marginalmente) più interessante. Quando allociamo un numero sufficiente di nodi a dimensione fissa che il vettore dei puntatori è pieno, è necessario aumentare la dimensione del vettore. Come std::vector, dobbiamo copiare i suoi contenuti nel vettore appena assegnato, quindi la sua crescita deve seguire una progressione geometrica (piuttosto che aritmetica). Ciò significa che abbiamo più indicazioni per copiare la copia in modo sempre meno frequente, quindi il tempo totale dedicato ai puntatori di copia rimane costante.

Come nota a margine: la parte "vettoriale" viene normalmente trattata come un buffer circolare, quindi se si utilizza la coda come coda, l'aggiunta costante a un'estremità e la rimozione dall'altra non risultano in allocare il vettore - significa semplicemente spostare i puntatori testa e coda che tengono traccia di quale dei puntatori sono "attivi" in un dato momento.

Answer 2

L'(profano) risposta sta nel containers.requirements.general, 23.2.1/2:

Tutti i requisiti di complessità in questa clausola sono iscritti solo in termini di numero di operazioni sul oggetti contenuti.

riassegnazione della matrice di puntatori non è quindi coperto dalla garanzia complessità dello standard e possono prendere arbitrariamente lungo. Come accennato in precedenza, è probabile che aggiunga un overhead costante ammortizzato a ciascuna chiamata push_front()/push_back() (oa un modificatore equivalente) in qualsiasi implementazione "sana". Non raccomanderei comunque di usare deque nel codice RT-critical. In genere, in uno scenario RT, non si desidera avere code o stack illimitati (che in C++ utilizza per default deque come contenitore sottostante), né allocazioni di memoria che potrebbero non riuscire, quindi sarà molto probabile che si utilizzi un anello preallocato buffer (es. Boost's circular_buffer).