C++ e STL: ordinare una lista

Salve di nuovo.. :)

Visto che è da un bel po che non scrivo mezza riga di codice C++ voglio scrivere un post e cogliere l'occasione di scrivere qualcosina, seppur semplice.
Avevo intenzione di scrivere un semplice programmino per ordinare una lista utilizzando il metodo sort().

Innanzitutto la lista è un container di elementi, infatti è implementata nella STL (Standard Template Library) come template. E' implementata come una lista doppiamente linkata, ovvero ogni nodo è collegato al successivo ed al precedente, inoltre ci sono 2 nodi speciali, head e tail, o header e trailer, che rappresentano l'inizio (elemento precedente al primo) e la fine (elemento successivo all'ultimo) della lista.

Ok. dopo questa bella immagine passiamo al codice.
Innanzitutto cosa voglio fare: voglio creare una lista di interi ed ordinarla usando il metodo sort().

#include <iostream>;
#include <list>;

using namespace std;


bool intComparator(int a, int b) {
 return a <= b;
}


int main() {

 list<int> intList;

 intList.push_front(2);
 intList.push_front(5);
 intList.push_front(7);

 list<int>::iterator intIT;
 cout << "Original int list: \n";
 for(intIT = intList.begin(); (intIT != intList.end()); ++intIT)
  cout << *intIT << " ";
 cout << endl;

 intList.sort(intComparator);
 cout << "Ordered int list: ";
 for(intIT = intList.begin(); (intIT != intList.end()); ++intIT)
   cout << *intIT << " ";
 cout << endl;

 return 0;
}

Allora, dopo i classici include, per prima cosa mi dichiaro il mio comparatore. Il comparatore può essere qualsiasi funzione che prende 2 parametri dello stesso tipo e restituisce true se nell'ordinamento il primo elemento viene prima del secondo elemento, false altrimenti. 

Subito dopo comincia il main. Dichiaro una lista intList che farà da container di elementi di tipo intero.

Successivamente la riempio con un po' di numeri, li inserisco da "davanti" con push_front() che inserisce un elemento alla prima posizione della lista, quindi immediatamente dopo l'header. La sequenza ottenuta è quindi [7, 5, 2].

Fatto ciò stampo a video la lista disordinata. Dichiaro un iteratore intIT, che sarà quindi un container per degli elementi di una lista che contiene interi, dunque, sarà a sua volta un container per elementi di tipo intero.

L'iteratore viene inizializzato nel for con intList.begin() che restituisce il puntatore all'header.

Questo, quindi, deve essere incrementato per puntare al primo elemento, ed è la prima cosa che viene fatta nel for. 

Dopo di che non viene fatto altro che la stampa a video dell'elemento corrente. L'iteratore è un puntatore all'elemento corrente, quindi, per essere usato, va deferenziato.

Il ciclo finisce quando l'iteratore arriva a intList.end() che corrisponde al trailer della stessa.

Subito dopo il for avviene l'ordinamento della lista. Il metodo può essere richiamato anche senza parametri, in tal caso viene utilizzato la relazione "<" per il confronto.

Il metodo però accetta anche un argomento. Questo è il puntatore alla funzione comparatore scritta, identificato dal nome della funzione ovviamente, in questo caso intComparator.

In questo modo per eseguire il confronto tra gli elementi verrà utilizzata la funzione specificata.

Il programma si chiude stampando di nuovo la lista a video, stavolta ordinata :)

Ok, questo è un post molto "tranquillo" :)

Ma ho intenzione di utilizzarlo come trampolino di lancio per capire un paio di cose e condividerle.

Per esempio: se eseguo l'overload della funzione intComparator, come faccio a passare alla funzione il puntatore "esatto" della funzione che voglio eseguire? Viene deciso a runtime?

Inoltre voglio vedere anche come posso passargli un comparatore implementato in un'altra classe.

Vediamo che ne esce fuori.. :)

Al prossimo post!