Che senso ha utilizzare le liste sui vettori, in C ++?

La risposta breve è che i casi sembrano essere pochi e distanti tra loro. Ci sono probabilmente alcuni però.

Si potrebbe essere quando è necessario memorizzare un piccolo numero di oggetti di grandi dimensioni, in particolare oggetti così grandi da non essere in grado di allocare spazio anche per alcuni di essi. Non c'è praticamente alcun modo per fermare un vettore o un deque dall'assegnare spazio per oggetti extra - è come sono definiti (cioè, devono allocare spazio extra per soddisfare i loro requisiti di complessità). Se non riesci impossibile a consentire che lo spazio aggiuntivo venga assegnato, un std::list potrebbe essere il contenitore standard solo che soddisfa le tue esigenze.

Un altro sarebbe quando / se memorizzerai un iteratore in un punto "interessante" in un elenco per un lungo periodo di tempo, e quando fai degli inserimenti e / o delezioni, lo fai (quasi) sempre da un punto in cui hai già un iteratore, quindi non scorrere l'elenco per arrivare al punto in cui stai andando a fare l'inserimento o la cancellazione. Ovviamente lo stesso si applica se lavori con più di un punto, ma stai ancora programmando di archiviare un iteratore in ogni posto con cui probabilmente lavorerai, in modo da manipolare i punti che puoi raggiungere direttamente e solo raramente attraverso l'elenco per ottenere a quei punti.

Per un esempio del primo, considera un browser web. Potrebbe mantenere un elenco collegato di oggetti Tab , con ciascun oggetto scheda che rappresenta nella scheda aperta nel browser. Ogni scheda potrebbe contenere alcune decine di megabyte di dati (di più, soprattutto se è coinvolto qualcosa come un video). Il tuo numero tipico di schede aperte potrebbe facilmente essere inferiore a una dozzina, e 100 è probabilmente vicino all'estremo superiore.

Per un esempio del secondo, considera un elaboratore di testi che memorizza il testo come un elenco collegato di capitoli, ognuno dei quali potrebbe contenere un elenco collegato di (dire) paragrafi. Quando l'utente sta modificando, in genere troverà un punto preciso in cui verrà modificato e quindi eseguirà una buona quantità di lavoro in quel punto (o comunque all'interno di quel paragrafo). Sì, passeranno da un paragrafo all'altro di tanto in tanto, ma nella maggior parte dei casi sarà un paragrafo vicino a dove stavano già lavorando.

Una volta ogni tanto (cose come ricerca e sostituzione globali) si finisce per percorrere tutti gli elementi di tutte le liste, ma è abbastanza raro, e anche quando lo fai, probabilmente farai abbastanza ricerche di lavoro all'interno un elemento nella lista, che il tempo di attraversare la lista è quasi irrilevante.

Si noti che in un caso tipico, è probabile che questo si adatti anche al primo criterio - un capitolo contiene un abbastanza piccolo numero di paragrafi, ognuno dei quali è probabile che sia abbastanza grande (a meno relativo alla dimensione dei puntatori nel nodo, e tale). Allo stesso modo, hai un relativamente piccolo numero di capitoli, ognuno dei quali potrebbe essere di diversi kilobyte o giù di lì.

Detto questo, devo ammettere che entrambi questi esempi sono probabilmente un po 'forzati, e mentre una lista collegata potrebbe funzionare perfettamente per entrambi, probabilmente non offrirebbe un enorme vantaggio in entrambi i casi. In entrambi i casi, ad esempio, l'allocazione di spazio aggiuntivo in un vettore per alcune (vuote) pagine web / schede o alcuni capitoli vuoti è improbabile che costituisca un problema reale.

Secondo lo stesso Bjarne Stroustrup, i vettori dovrebbero sempre essere la raccolta predefinita per le sequenze di dati. Puoi scegliere l'elenco se desideri ottimizzare l'inserimento e la cancellazione di elementi, ma normalmente non dovresti. I costi dell'elenco sono traversal lenti e utilizzo della memoria.

Ne parla questa presentazione .

A circa 0:44 parla di vettori contro liste in generale.

Compactness matters. Vectors are more compact than lists. And predictable usage patterns matters enormously. With vectors you have to shove a lot of elements over but caches are really, really good at that. ... Lists don't have random access. But when you traverse a list, you keep doing random access. There's a node here, and it goes to that node, in memory. So you are actually random accessing your memory, and you are maximizing your cache misses, which is exactly the opposite of what you want.

All'incirca all'1: 08, riceve una domanda su questo problema.

What we should see it that we need a sequence of elements. And the default sequence of elements in C++ is the vector. Now, because that is compact and efficient. Implementation, mapping to hardware, matters. Now, if you want to optimize for insertion and deletion - you say, 'well, I don't want the default version of a sequence. I want the specialized one, which is a list'. And if you do that, you should know enough to say, 'I'm accepting some costs and some problems, like slow traversals and more memory usage'.

L'unico posto in cui di solito utilizzo le liste è dove ho bisogno di cancellare elementi e non invalidare gli iteratori. std::vector invalida tutti gli iteratori durante l'inserimento e la cancellazione. std::list garantisce che gli iteratori agli elementi esistenti sono ancora validi dopo l'inserimento o l'eliminazione.

Oltre alle altre risposte già fornite, le liste hanno alcune caratteristiche che non esistono nei vettori (perché sarebbero follemente costose.) Le operazioni di giunzione e unione sono le più significative. Se hai spesso un gruppo di liste che devono essere aggiunte o unite, una lista è probabilmente una buona scelta.

Ma se non è necessario eseguire queste operazioni, probabilmente no.

La mancanza di cache intrinseca / compatibilità delle pagine delle liste collegate tende a renderle quasi completamente ignorate da molti sviluppatori C ++ e con una buona giustificazione in quella forma predefinita.

Le liste collegate possono ancora essere meravigliose

Tuttavia, le liste concatenate possono essere meravigliose se supportate da un allocatore fisso che restituisce loro quella località spaziale di cui sono intrinsecamente prive.

Dove eccellono è che possiamo dividere una lista in due liste, per esempio, semplicemente memorizzando un nuovo puntatore e manipolando un puntatore o due. Possiamo spostare i nodi da una lista all'altra in tempo costante con la semplice manipolazione del puntatore e una lista vuota può semplicemente avere il costo di memoria di un singolo puntatore head .

Simple Grid Accelerator

Come esempio pratico, considera una simulazione visiva 2D. Ha una schermata a scorrimento con una mappa che si estende su 400x400 (160.000 celle di griglia) utilizzata per accelerare le cose come il rilevamento di collisioni tra milioni di particelle che si muovono in ogni fotogramma (evitiamo i quadricipiti qui in quanto tendono a peggiorare con questo livello di dati dinamici). Un sacco di particelle si muovono costantemente attorno ad ogni fotogramma, il che significa che passano continuamente da una cella all'altra.

In questo caso, se ogni particella è un nodo di lista a collegamento singolo, ciascuna cella della griglia può iniziare come un puntatore head che punta a nullptr . Quando nasce una nuova particella, la inseriamo semplicemente nella cella della griglia in cui si trova impostando il puntatore head di quella cella in modo che punti a questo nodo particellare. Quando una particella si sposta da una cella della griglia alla successiva, modifichiamo solo i puntatori.

Questo può essere molto più efficiente della memorizzazione di 160.000% divectors per ogni cella della griglia e di tornare indietro e cancellare dal centro tutto il tempo su una base fotogramma per fotogramma.

std :: list

Questo è per gli elenchi fatti a mano, intrusivi, collegati singolarmente e supportati da un allocatore fisso. std::list rappresenta un elenco doppiamente collegato e potrebbe non essere altrettanto compatto quando vuoto come un singolo puntatore (varia in base all'implementazione del fornitore), in più è una specie di sofferenza implementare gli allocatori personalizzati in formato std::allocator .

Devo ammettere che non uso mai list qualunque. Ma le liste collegate possono essere ancora meravigliose! Tuttavia non sono meravigliosi per le ragioni per cui le persone sono spesso tentate di usarli, e non così meravigliosi se non sono supportati da un allocatore fisso molto efficiente che attenua almeno gli errori di pagina obbligatori e i problemi di cache associati.

Devi prendere in considerazione la dimensione degli elementi nel contenitore.

int vector vettore è molto veloce poiché la maggior parte dei dati si adatta alla cache della CPU (e le istruzioni SIMD possono probabilmente essere utilizzate per la copiatura dei dati).

Se la dimensione dell'elemento è maggiore, il risultato dei test 1 e 3 potrebbe cambiare in modo significativo.

Da un confronto delle prestazioni molto completo :

This draw simple conclusions on usage of each data structure:

• Number crunching: use std::vector or std::deque
• Linear search: use std::vector or std::deque
• Random Insert/Remove:
  • Small data size: use std::vector
  • Large element size: use std::list (unless if intended principally for searching)
• Non-trivial data type: use std::list unless you need the container especially for searching. But for multiple modifications of the container, it will be very slow.
• Push to front: use std::deque or std::list

(come nota a margine std::deque è una struttura dati molto sottovalutata).

Da un punto di vista della convenienza std::list fornisce la garanzia che gli iteratori non vengano mai invalidati quando si inseriscono e si rimuovono altri elementi. È spesso un aspetto chiave.

Il motivo principale per utilizzare gli elenchi secondo me è invalidazione iteratore : se aggiungi / rimuovi elementi a un vettore, tutti i puntatori, i riferimenti, gli iteratori che hai tenuto a determinati elementi di questo vettore può essere invalidato e portare a bug sottili ... o errori di segmentazione.

Questo non è il caso delle liste.

Le regole precise per tutti i contenitori standard sono fornite in questo post StackOverflow .

In breve, non c'è una buona ragione per usare std::list<> :

• Se hai bisogno di un contenitore non ordinato, std::vector<> regole.
  (Elimina elementi sostituendoli con l'ultimo elemento del vettore.)

• Se hai bisogno di un contenitore ordinato, std::vector<shared_ptr<>> regole.

• Se hai bisogno di un indice sparse, std::unordered_map<> rules.

Questo è tutto.

Trovo che ci sia una sola situazione in cui tendo ad usare una lista collegata: quando ho preesistenti oggetti che devono essere collegati in qualche modo per implementare qualche logica applicativa aggiuntiva. Tuttavia, in quel caso non uso mai std::list<> , piuttosto ricado a un puntatore successivo (intelligente) all'interno dell'oggetto, soprattutto perché la maggior parte dei casi d'uso genera un albero piuttosto che un elenco lineare. In alcuni casi, la struttura risultante è un elenco collegato, in altri è un albero o un grafico aciclico diretto. Lo scopo principale di questi puntatori è sempre quello di costruire una struttura logica, mai di gestire oggetti. Abbiamo std::vector<> per quello.

Devi mostrare come stavi facendo gli inserti nel tuo primo test. Il tuo secondo e terzo test, il vettore vincerà facilmente.

Un uso significativo delle liste è quando devi supportare la rimozione di elementi durante l'iterazione. Quando il vettore viene modificato, tutti gli iteratori sono (potenzialmente) non validi. Con un elenco, solo un iteratore dell'elemento rimosso non è valido. Tutti gli altri iteratori rimangono validi.

L'ordine di utilizzo tipico per i contenitori è vettore, deque, quindi elenco. La scelta del contenitore è in genere basata su push_back scegli vettoriale, pop_front seleziona deque, inserisci scegli elenco.

Un fattore che posso pensare è che man mano che un vettore cresce, la memoria libera si frammenterà man mano che il vettore dealna la sua memoria e alloca un blocco più grande più e più volte. Questo non sarà un problema con gli elenchi.

Ciò si aggiunge al fatto che un numero elevato di push_back s senza riserva causerà anche una copia durante ogni ridimensionamento che lo rende inefficiente. Anche l'inserimento nel mezzo provoca una mossa di tutti gli elementi a destra, ed è anche peggio.

Non so se questa è una delle maggiori preoccupazioni, ma è stata la ragione che mi è stata data nel mio lavoro (sviluppo del gioco mobile), per evitare i vettori.