Complessità del STL deque :: insert()

Question

ho imparato la complessità del deque::insert() dallo standard 2003 (capitolo 23.2.1.3) C++ come segue:

Nel peggiore dei casi, l'inserimento di un singolo elemento in un deque richiede tempo lineare nel minimo della distanza dal punto di inserimento all'inizio della deque e la distanza dal punto di inserimento alla fine della deque.

Ho sempre compreso l'implementazione di stl deque come una raccolta di blocchi di memoria. Quindi un inserimento interesserà solo gli elementi nello stesso blocco di memoria della posizione di inserimento. La mia domanda è: cosa significa lo standard per "lineare nel minimo della distanza dal punto di inserimento all'inizio della deque e la distanza dal punto di inserimento alla fine della deque"?

La mia comprensione è perché lo standard C++ non applica una determinata implementazione di deque. La complessità è solo in generale per il caso peggiore. Tuttavia, nell'attuale implementazione nei compilatori, è lineare rispetto al numero di elementi in un blocco di memoria, che può variare a seconda delle dimensioni degli elementi.

Un'altra ipotesi potrebbe essere che, dal momento che insert() invaliderà tutti gli iteratori, deque deve aggiornare tutti gli iteratori. Quindi è lineare.

Answer 1

std :: deque è normalmente (sempre?) Implementato come una raccolta di blocchi di memoria, ma normalmente non inserirà un blocco completamente nuovo solo per poter inserire un nuovo elemento nel mezzo della raccolta . In quanto tale, scoprirà se il punto di inserimento è più vicino all'inizio o alla fine e mescola gli elementi esistenti per creare spazio per il nuovo elemento in un blocco esistente. Aggiungerà solo un nuovo blocco di memoria all'inizio o alla fine della raccolta.

Answer 2

Lineare sul numero di elementi inseriti (copia costruzione). Inoltre, a seconda della particolare implementazione della libreria, tempo lineare aggiuntivo fino al numero di elementi tra la posizione e una delle estremità della deque. Reference...

Answer 3

Le tue congetture sono ... 99,9% vero. Tutto dipende da cosa è l'effettiva implementazione. Quello che lo standard specifica è il requisito minimo per entrambi gli implementatori (che non possono pretendere di essere standard se non si adattano alle specifiche) e gli utenti (che non devono aspettarsi "prestazioni migliori" se scrivono codice indipendente dall'implementazione).

L'idea alla base della specifica, è un blocco (a == uno) di memoria non inizializzata in cui gli elementi sono allocati attorno al centro ... finché non c'è spazio per loro. L'inserimento nel mezzo significa spostamento. L'inserimento davanti o alla fine significa semplicemente costruire in posizione. (quando non c'è spazio, viene effettuata una riallocazione) Gli indici e gli iteratori non possono essere considerati attendibili dopo una modifica, poiché non possiamo assumere ciò che è stato spostato e in quale direzione.

Un'implementazione più efficiente non utilizza un singolo blocco, ma un blocco multiplo per ridistribuire il problema "spostamento" e allocare memoria a dimensione costante dal sistema sottostante (limitando così la riallocazione e la frammentazione). Se stai prendendo di mira uno di questi puoi aspettarti prestazioni migliori, altrimenti dovresti fare meglio a non ipotizzare alcuna ottimizzazione della struttura.

Answer 4

Penso che faresti meglio a servirti di uno schema ... giochiamo con l'arte ASCII!

Una deque è in genere una serie di blocchi di memoria, ma tutti a parte i blocchi di memoria anteriore e posteriore sono pieni.Ciò è necessario perché una deque è una RandomAccessContainer, e per ottenere O (1) l'accesso a qualsiasi contenitore, non si può avere un numero illimitato di contenitori da cui leggere le dimensioni:

bool size() const { return first.size + (buckets.size()- 2) * SIZE + last.size; } 

T& operator[](size_t i) { 
    if (i < first.size) { return first[SIZE - i]; } 

    size_t const correctedIndex = i - first.size; 
    return buckets[correctedIndex/SIZE][correctedIndex % SIZE]; 
} 

Tali operazioni sono O (1) a causa della moltiplicazione/divisione!

Nel mio esempio, suppongo che un blocco di memoria sia pieno quando contiene 8 elementi. In pratica nessuno ha detto che le dimensioni dovrebbero essere fissate, solo che tutti i secchi interni devono avere le stesse dimensioni.

// Deque 
0:  ++ 
1: ++++++++ 
2: ++++++++ 
3: ++++++++ 
4: +++++ 

Ora dicono che vogliamo inserire in corrispondenza dell'indice 13. Essa rientra da qualche parte nel secchio con l'etichetta 2. Ci sono diverse strategie che possiamo pensare:

• estendere secchio 2 (solo)
• introdurre un nuovo secchio prima o dopo 2 e shuffle solo pochi elementi

Ma quei due strategie violerebbe l'invariante che tutti i secchi "interni" hanno lo stesso num b di elementi.

quindi ci ritroviamo con mischiare gli elementi intorno, sia verso l'inizio o la fine (a seconda di quale è più conveniente), nel nostro caso:

// Deque 
0:  +++ 
1: ++++++++ 
2: +O++++++ 
3: ++++++++ 
4: +++++ 

Si noti come secchio 0 cresciuto.

Questo shuffle implica che, nel peggiore dei casi, si muoveranno metà degli elementi: O (N/2).

deque ha O (1) inserto all'inizio o alla fine, perché è solo questione di aggiungere l'elemento nel posto giusto o (se il bucket è pieno) creando un nuovo bucket.

Esistono altri contenitori che presentano un comportamento di inserimento/cancellazione migliore a indici casuali, in base a B+ Trees. In un albero B + indicizzato puoi, invece di una "chiave" (o in parallelo) mantenere internamente un conteggio degli elementi prima di una determinata posizione. Ci sono varie tecniche per farlo in modo efficiente. Alla fine si ottiene un contenitore con:

• O (1): vuoto, dimensioni
• O (log N): a, inserire, cancellare

È possibile controllare il modulo blist in Python che implementa un elemento di tipo Python supportato da una tale struttura.