Come è implementato lo ordinamento per std :: deque?

Question

Non ho finora imparato come std::deque sia implementato sotto il cofano e scoperto che si tratta di qualcosa come un array di puntatori agli array di n byte, in cui i dati vengono effettivamente memorizzati. Quindi ora ho un paio di domande relative ai deques.

Un quadro che descrive il mio stato attuale delle conoscenze la sua struttura:

Le domande sono:

1. Quando è in corso un'operazione di push_front e non c'è spazio libero nel blocco dati 0, un nuovo blocco dati è allocato su heap e un puntatore a questa memoria appena allocata viene inserito nell'array 'Map' come nell'array ordinario - in tempo O (numero_di_blocchi), sì?

2. Come ordinare questa bestia? Non riesco ad immaginare niente di meglio quindi copia tutti i dati in un array, ordinalo e poi rimettilo in ordine. Ma questo approccio richiede O (n) memoria ausiliaria ... Ma! std::sort fornisce un'interfaccia simile per l'ordinamento sia di std::vector e di std::deque. Come vengono implementati diversi algoritmi per diverse strutture di dati? Utilizzando una specializzazione template? In tal caso, perché std::list non può essere ordinato utilizzando std::sort? Oppure, std::sort non si preoccupa della struttura interna di questi contenitori e utilizza solo iteratori e metodi, che sono simili sia in std::vector e std::deque (come operator[], size(), ecc.)? Questa idea sembra ragionevole e una risposta a "perché non è possibile ordinare std::list?" diventa evidente

3. Come vengono scelte le dimensioni dei blocchi dati? Dirai "Dipende dall'implementazione", ma ti preghiamo di dire di più sulle diverse implementazioni e motivazioni dietro alle soluzioni.

Hai bisogno di chiarimenti qui. Grazie.

Answer 1

Per rispondere alla prima domanda, sì, è praticamente come funziona. Si può notare che questo approccio può essere esteso a una struttura gerarchica multilivello. Ma le implementazioni pratiche di solito si attaccano alla struttura a due livelli, esattamente come mostrato nella foto.

Per la seconda domanda, se si sta prendendo circa std::sort, quindi std::sort funziona senza alcuna conoscenza circa i meccanismi del contenitore reale. Se funziona su una gamma di iteratori ad accesso casuale. Poiché gli iteratori di std::deque sono iteratori ad accesso casuale, std::sort può essere applicato a std::deque. E si può effettivamente sostenere che l'accesso casuale ad elementi di tale struttura dati è piuttosto efficiente. Non è efficiente come l'accesso casuale in un vettore, ma è comunque abbastanza efficiente da dare un senso nel contesto di std::sort.

Non è possibile utilizzare std::sort con std::list perché iteratori std::list s' non sono iteratori ad accesso casuale. Se lo desideri, puoi implementare la tua versione semplice (lenta) di iteratore ad accesso casuale per std::list. Sarà possibile applicare std::sort a un intervallo di tali iteratori e quindi ordinare uno std::list con std::sort. Ma per ovvi motivi sarà proibitivamente inefficiente.

In caso di std::deque gli iteratori di accesso casuale sono più che adeguatamente efficienti.

Non sono disposto a rispondere alla terza domanda. In effetti non sarei sorpreso di scoprire che queste dimensioni sono scelte empiricamente, sulla base di una serie di esperimenti. E, naturalmente, probabilmente non esiste una soluzione "taglia unica".