Qual è la differenza tra i contenitori STL deque ed list?

StackOverflow https://stackoverflow.com/questions/1436020

  •  07-07-2019
  •  | 
  •  

Domanda

Qual è la differenza tra i due? Voglio dire, i metodi sono tutti uguali. Quindi, per un utente, funzionano in modo identico.

È corretto ??

È stato utile?

Soluzione

Dal sommario (datato ma ancora molto utile) SGI STL di deque :

  

Un deque è molto simile a un vettore: come un vettore, è una sequenza che supporta l'accesso casuale agli elementi, l'inserimento e la rimozione costanti del tempo alla fine della sequenza e l'inserimento e la rimozione lineari del tempo negli elementi centrale.

     

Il modo principale in cui il deque differisce dal vettore è che il deque supporta anche l'inserimento e la rimozione costanti di tempo all'inizio della sequenza. Inoltre, deque non ha alcuna funzione membro analoga alla capacità di vettore () e reserve () e non fornisce alcuna garanzia sulla validità dell'iteratore associata a tali funzioni membro.

Ecco il riepilogo su list dal stesso sito:

  

Un elenco è un elenco doppiamente collegato. Cioè, è una sequenza che supporta sia l'attraversamento in avanti che all'indietro e l'inserimento e la rimozione di tempo costante (ammortizzato) di elementi all'inizio o alla fine o nel mezzo. Gli elenchi hanno l'importante proprietà che l'inserimento e lo splicing non invalidano gli iteratori per elencare gli elementi e che anche la rimozione invalida solo gli iteratori che puntano agli elementi rimossi. L'ordinamento degli iteratori può essere modificato (ovvero list :: iterator potrebbe avere un predecessore o un successore diverso dopo un'operazione di elenco rispetto a prima), ma gli stessi iteratori non verranno invalidati o fatti puntare a elementi diversi a meno che l'invalidazione o la mutazione è esplicita.

In sintesi, i contenitori possono avere routine condivise ma le garanzie temporali per tali routine differiscono da contenitore a contenitore . Questo è molto importante quando si considera quale di questi contenitori utilizzare per un'attività: prendere in considerazione come il contenitore verrà utilizzato più frequentemente (ad esempio, più per la ricerca che per l'inserimento / eliminazione) fa molta strada nel dirigerti verso il contenitore giusto.

Altri suggerimenti

Vorrei elencare le differenze:

  • Deque gestisce i suoi elementi con a array dinamico , fornisce casuale accesso e ha quasi lo stesso interfaccia come un vettore.
  • Elenco gestisce i suoi elementi come a lista doppiamente collegata e non lo fa fornire accesso casuale .
  • Deque fornisce inserimenti rapidi ed eliminazioni su sia la fine che l'inizio. Inserimento ed eliminazione di elementi in il mezzo è relativamente lento perché tutti gli elementi fino a uno di entrambi le estremità possono essere spostate per fare spazio o in colmare una lacuna.
  • In Elenco , l'inserimento e la rimozione di elementi è veloce in ogni posizione, comprese entrambe le estremità.
  • Deque : qualsiasi inserimento o eliminazione di elementi diverso all'inizio o alla fine invalida tutti i puntatori, i riferimenti, e iteratori che si riferiscono ad elementi del deque.
  • Elenco : l'inserimento e l'eliminazione di elementi lo fanno puntatori, riferimenti non validi e iteratori di altri elementi.

Complessità 

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant

std :: list è sostanzialmente un elenco doppiamente collegato.

std :: deque , sul d'altra parte, è implementato più come std :: vector . Ha un tempo di accesso costante per indice, nonché l'inserimento e la rimozione all'inizio e alla fine, che offre caratteristiche di prestazioni notevolmente diverse rispetto a un elenco.

No. Un deque supporta solo l'inserimento e l'eliminazione di O (1) nella parte anteriore e posteriore. Ad esempio, può essere implementato in un vettore con avvolgimento. Dal momento che garantisce anche l'accesso casuale O (1), puoi essere sicuro che non sta usando (solo) un elenco doppiamente collegato.

Un'altra importante garanzia è il modo in cui ciascun contenitore diverso memorizza i suoi dati in memoria:

  • Un vettore è un singolo blocco di memoria contiguo.
  • Un deque è un insieme di blocchi di memoria collegati, in cui è memorizzato più di un elemento in ciascun blocco di memoria.
  • Un elenco è un insieme di elementi dispersi nella memoria, vale a dire: è memorizzato un solo elemento per memoria "blocco".

Nota che il deque è stato progettato per provare a bilanciare i vantaggi sia del vettore che dell'elenco senza i loro rispettivi svantaggi. È un contenitore particolarmente interessante nelle piattaforme a memoria limitata, ad esempio i microcontrollori.

La strategia di archiviazione della memoria è spesso trascurata, tuttavia è spesso uno dei motivi più importanti per selezionare il contenitore più adatto per una determinata applicazione.

Le differenze di prestazioni sono state ben spiegate da altri. Volevo solo aggiungere che interfacce simili o addirittura identiche sono comuni nella programmazione orientata agli oggetti - parte della metodologia generale di scrittura di software orientato agli oggetti. Non dovresti in alcun modo supporre che due classi lavorino allo stesso modo semplicemente perché implementano la stessa interfaccia, non più di quanto dovresti supporre che un cavallo funzioni come un cane perché implementano entrambi attack () e make_noise ().

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top