La deque di accesso STL per indice è O (1)?

Question

Ho letto che gli elementi di accesso per indice di posizione possono essere eseguiti in tempo costante in un deque STL. Per quanto ne so, gli elementi di una deque possono essere memorizzati in diverse posizioni non contigue, eliminando l'accesso sicuro tramite l'aritmetica del puntatore. Ad esempio:

ABC-> defghi-> jkl-> mnop

Gli elementi del deque sopra è costituito da un singolo carattere. L'insieme di caratteri in un gruppo indica che è allocato in memoria contigua (ad esempio abc si trova in un singolo blocco di memoria, defhi si trova in un altro blocco di memoria, ecc.). Qualcuno può spiegare in che modo l'accesso tramite l'indice di posizione può essere eseguito in un tempo costante, specialmente se l'elemento a cui si accede si trova nel secondo blocco? O un deque ha un puntatore al gruppo di blocchi?

Aggiornamento: O c'è qualche altra implementazione comune per un deque?

Answer 1

ho trovato questa implementazione deque da Wikipedia:

Memorizzazione contenuti in più array piccole, ripartizione array aggiuntivi all'inizio o alla fine come necessario. L'indicizzazione viene implementata mantenendo un array dinamico contenente puntatori a ciascuno degli array più piccoli.

Immagino che risponda alla mia domanda.

Answer 2

Se la deque è implementata come ring buffer sopra std::vector, che si rialloca quando aumenta di dimensioni, quindi l'accesso per indice è effettivamente O (1).

Lo standard fornisce la prova che tale implementazione è stata concepita, almeno conforme alle stime di complessità standard. Clausole 23.2.1.3/4 e 23.2.1.3/5 richiedono che

• inserendo all'inizio o alla fine di un deque richiedono tempo costante, mentre inserimento al centro richiede tempo lineare delle dimensioni della coda doppia

• durante la cancellazione di elementi dalla deque, può chiamare tutti gli operatori di assegnazione, poiché la distanza dagli elementi da cancellare alla fine della deque è.

E, naturalmente, è necessario contare su requisiti standard anziché sulla propria visione su come i contenitori e gli algoritmi potrebbero essere implementati.

NOTA che lo standard richiede più di questi due punti sopra elencati. Implica inoltre la necessità che i riferimenti agli elementi debbano rimanere validi tra gli inserimenti sul retro o sul davanti del deque. Questo può essere soddisfatto se il buffer circolare contiene puntatori agli elementi reali piuttosto che agli elementi stessi. Ad ogni modo, la mia risposta dimostra semplicemente che diverse implementazioni possono soddisfare determinati requisiti.

Answer 3

Una delle possibili implementazioni può essere una matrice dinamica di array const-sized; tale array di dimensioni costanti può essere aggiunto a entrambe le estremità quando è necessario più spazio. Tutti gli array sono pieni tranne, forse, per i primi e gli ultimi che possono essere parzialmente vuoti. Ciò significa conoscere la dimensione di ciascun array e il numero degli elementi utilizzati nel primo array, uno può facilmente trovare una posizione di un elemento per indice.
http://cpp-tip-of-the-day.blogspot.ru/2013/11/how-is-stddeque-implemented.html