List (STL)

Il container List è un contenitore sequenziale incluso nella libreria standard del C++. La definizione di questa classe si trova nel file header <list> del namespace std.

Descrizione

La List rappresenta un'alternativa al vector in quanto più efficiente quando si rende necessario fare inserimenti in un punto qualsiasi del contenitore. Infatti, grazie alla doppia concatenazione la List può essere scorsa in entrambe le direzioni con tempo di inserimento (o di eliminazione) costante (O(1)). Gli oggetti non sono mantenuti in zone di memoria adiacenti e pertanto non è possibile effettuare un accesso diretto ad essi. La ricerca, invece, avviene in tempo lineare (O(n)). La List è gestita, come tutti i container della STL, tramite iteratori bidirezionali che supportano gli operatori ++ e -- per lo spostamento all'elemento precedente (--) o successivo (++).

Operazioni sugli elementi

La List è particolarmente efficace negli inserimenti in posizione dei suoi elementi, ma risulta meno efficiente nell'accesso ad essi o nella ricerca, in quanto, per trovare un elemento bisogna necessariamente scorrere tutto il contenitore. Nel caso si presenti la necessità di effettuare queste operazioni frequentemente si dovrebbe considerare la possibilità di utilizzare un container diverso come la Map (STL).

Ecco un esempio di costruzione e stampa di una List tramite un Iteratore:

 #include <iostream>
 #include <list>
 using namespace std;
 int main(){
    list<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(5);
    for(list<int>::iterator i = l.begin(); i != l.end(); i++)
        cout << *i << endl;
    return 0;
 }