Risposta

std::vector e std::list sono contenitori STL diversi con implementazioni e comportamenti distinti.

• std::vector implementa un array dinamico, gli elementi sono disposti in modo continuo in memoria. Accesso veloce per indice (O(1)), aggiunta veloce alla fine (amortizzato O(1)), costosi inserimenti e rimozioni in mezzo (O(n)), poiché gli elementi devono essere spostati.
• std::list è una lista doppiamente concatenata. Accesso casuale lento (O(n)), inserimenti e rimozioni veloci in qualsiasi punto della lista (O(1)), maggiori spese di memoria (due puntatori per elemento) e frequenti allocazioni/deallocazioni.

Quando scegliere:

• Usa std::vector quasi sempre, se non sono necessarie frequenti inserzioni/rimozioni a metà.
• std::list è giustificato solo quando è necessario inserire/rimuovere in qualsiasi punto con grandi volumi di dati, quando spostare elementi in un vettore è troppo costoso.
• Per collezioni piccole, anche se è necessaria l'aggiunta in mezzo, std::vector è spesso più veloce a causa della località dei dati.

Esempio:

std::vector<int> v;
v.push_back(1);
v[0] = 2; // accesso veloce per indice

std::list<int> l;
l.push_back(1);
// l[0] = 2; // Errore: std::list non ha accesso per indice!

Domanda insidiosa

"Perché std::list è quasi inutilizzato nei moderni progetti C++ nonostante il vantaggio teorico in caso di frequenti inserimenti a metà collezione?"

Risposta: Perché nella pratica, a causa di numerose piccole allocazioni, perdita di località dei dati (cache-friendly), complessità della struttura e scarsa supporto di alcune operazioni (std::list è inefficiente anche per liste grandi a causa delle perdite di tempo per allocazione e deallocazione, e il rallentamento dovuto ai cache miss sovente supera i guadagni asintotici). Inoltre, i moderni processori sono molto sensibili alla località della cache, quindi anche con grandi volumi di dati, std::vector è spesso più veloce in condizioni reali.

Esempi di errori reali a causa della mancata conoscenza delle sfumature dell'argomento

---

Storia

Nei sistemi in tempo reale, per memorizzare una coda di eventi è stata scelta std::list a causa di frequenti rimozioni da posizioni casuali. Di conseguenza, il sistema è diventato 10 volte più lento a causa dei frequenti accessi all'heap e della scarsa localizzazione dei dati in memoria.

---

Storia

In un processore grafico, sono stati memorizzati array di vicini come std::list per via delle inserzioni. Questo ha portato a un drammatico aumento dell'uso della memoria e alla degradazione delle cache L1/L2, nonostante non ci siano stati reali profitti in termini di velocità.

---

Storia

Nel servizio di generazione report, ogni report veniva assemblato da oggetti Linked List. Nei test di stress, il servizio ha cominciato a "rallentare", e il profiling ha mostrato colli di bottiglia nei costi di allocazione quando si lavorava con le liste. Sono passati a vector — il risultato è migliorato notevolmente.