STL - List

Dal terzo capitolo di Designing Components with the C++ STL, di Ulrich Breymann, dedicato ai container.

Il container List ha una serie di metodi aggiuntivi:

• void merge(list&), void merge(list&, Compare_object): fonde due liste ordinate - complessità O(n). E' possibile specificare la modalità di comparazione.
• void push_front(const T& t): inserisce un elemento all'inizio.
• void pop_front(): elimina il primo elemento.
• void remove(const T& t): elimina tutti gli elementi uguali a t - O(n).
• void remove_if(Predicate P): elimina tutti gli elementi per cui vale il predicato passato.
• void reverse(): inverte l'ordine degli elementi nella lista.
• void sort(), void sort(Compare_object): ordina gli elementi in una lista usando Compare_object o l'operatore < definito per gli elementi. O(n log n).
• void splice(iterator pos, list& x): sposta il contenuto della lista x prima di pos.
• void splice(iterator pos, list&x, iterator it): sposta l'elemento di x puntato da it prima di pos.
• void splice(iterator pos, list& x, iterator first, iterator last): sposta gli elementi di x in [first, last) prima di pos. Se x == this pos deve essere esterno all'intervallo passato.
• void unique(), void unique(binaryPredicate): elimina gli elementi identici consecutivi, ad eccezione del primo, se applicato ad una lista ordinata lascia solo elementi unici.

Faccio un esempio che riassume, modificando leggermente, gli esempi proposti dal libro:

#include<iostream>
#include<iterator>
#include<list>

using namespace std;

void display(const list<int>& aList) {
   list<int>::const_iterator it = aList.begin();
   while (it != aList.end())
       cout << *it++ << ' ';
   cout << "[size is " << aList.size() << ']' << endl;
}

int main() {
   list<int> list1;
   list<int> list2;
   list<int> list3;

   for (int i = 0; i < 10; ++i) {
       list1.push_front(i * 2);
       list2.push_back(i * 2 + 1);
       list3.push_back(20 + i);
   }
   display(list1);
   cout << "Sorting:" << endl;
   list1.sort();
   display(list1);

   cout << "The other list:" << endl;
   display(list2);

   cout << "Merging:" << endl;
   list1.merge(list2);
   display(list1);
   display(list2);

   cout << "The third list:" << endl;
   display(list3);

   cout << "Splice:" << endl;
   list<int>::iterator it = list3.begin();
   advance(it, 4);
   list1.splice(list1.end(), list3, list3.begin(), it);
   display(list1);
   display(list3);
}

La funzioncina display() ci mostra la scansione sequenziale di una lista via iteratore. Le tre liste sono inizializzate usando push_front() e push_back(), la prima lista viene ordinata usando sort(), dopodichè viene fusa con list2 usando merge(). La terza lista viene utilizzata per farne uno splice() in list1: i suoi primi quattro elementi vengono spostati alla fine di list1.