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!

C++ liste e iteratori...

Salve a tutti :)

In questo post volevo scrivere qualcosa sul come navigare una lista usando gli iteratori in C++.
Cominciamo con un piccolo programma di esempio:

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char **argv) {

    list<int> l;

    for(int i = 0; i < 10; i++)
        l.push_back(i);

    list<int>::const_iterator it;
    for(it = l.begin(); it != l.end(); ++it)
        cout << *it << endl;

}

Bene, nelle prime righe ci sono i soliti include, nello specifico iostream serve per poter utilizzare cout; list come si può intuire serve per poter utilizzare il tipo list dell'STL.
Le successive righe del programma non fanno altro che inizializzare la lista e riempirla con un po' di numeri.

Dalla riga 13 in poi si comincia a scorrere la lista.
Per prima cosa viene dichiarato un const_iterator, un iteratore, cioè un oggetto che permette di accedere ai membri di una classe container (un contenitore di oggetti), in questo caso di una lista. Esso può essere visto come un puntatore agli elementi della classe container, nel nostro caso, esso è il puntatore all'elemento corrente della lista.

Successivamente, l'iteratore viene inizializzato. L'istruzione l.begin() restituisce l'iteratore agli elementi della lista, precisamente un iteratore che punta all'elemento begin.
Gli elementi begin e end non sono il primo e l'ultimo elemento della lista, ma sono dei valori sentinella, l'header e il trailer della stessa. Essi sono cioè l'elemento che precede il primo elemento della lista e quello successivo all'ultimo.
Infatti l'iteratore appena inizializzato non viene subito utilizzato per leggere gli elementi, ma la prima cosa che viene fatta è incrementarlo per poter puntare al primo elemento della lista, con l'istruzione.
Fatto ciò esso può essere utilizzato come se fosse un puntatore all'elemento della lista, in questo caso un puntatore a intero.
Ovviamente l'output del programma è l'elenco dei numeri da 0 a 9.

Una cosa da notare è che l'iteratore in questione è un const_iterator, questo significa che può essere utilizzato in sola lettura e non è possibile modificarne gli elementi.
Per poter modificare gli elementi puntati dall'iteratore basta modificare leggermente il programma precedente:

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char **argv) {

    list<int> l;

    for(int i = 0; i < 10; i++)
        l.push_back(i);

    list<int>::iterator it;
    for(it = l.begin(); it != l.end(); ++it) {
        *it *= 2;
        cout << *it << endl;
    }

}

Come mostrato, in questo modo è possibile modificare gli elementi della lista.

Ovviamente in una lista possono essere contenuti diversi tipi di dati, non solo interi.
Si può scorrere tranquillamente una lista usando gli iteratori anche con altri tipi di strutture dati, quali classi o struct.
Vediamo ora un semplice esempio nell'uso di un iteratore per scorrere una lista che contiene una struct, per poi vederne uno in cui la lista contiene degli oggetti che sono istanze di classi:

#include <iostream>
#include <list>

using namespace std;


struct myStruct {
    string something;
};


int main(int argc, char **argv) {

    list<myStruct> l;

    myStruct *s1 = new myStruct();
    myStruct *s2 = new myStruct();
    s1->something = "hello ";
    s2->something = "world";

    l.push_back(*s1);
    l.push_back(*s2);

    list<myStruct>::const_iterator it;
    for(it = l.begin(); it != l.end(); ++it)
        cout << (*it).something;

}

Qui invece di un intero, la lista contiene una semplice struttura che al suo interno contiene solo una stringa.
Come prima cosa si inizializzano due variabili di tipo myStruct e ci si mette qualcosa dentro.
Visto che ogni tutorial quando ci sono delle stringhe è sempre presente "hello world", questo è quello che è stato inserito nelle strutture :-P
Successivamente si inseriscono le due variabili nella lista. Siccome la lista è stata dichiarata list<myStruct> i riferimenti alle strutture devono essere deferenziati prima di poterli inserire. Ovviamente è possibile inserire direttamente i riferimenti, dichiarando la lista come list<*myStruct>.
Come prima, il passo successivo consiste nell'inizializzare l'iteratore.
La cosa da notare qui è come si accede agli elementi della lista. L'iteratore è un puntatore all'elemento corrente della lista, quindi bisogna innanzitutto deferenziarlo per accedere all'elemento contenuto.
L'istruzione (*it) restituisce quindi l'oggetto di tipo myStruct corrente, si può quindi accedere ai suoi membri semplicemente usando l'operatore punto.
Nel caso in cui nella lista fossero stati inseriti i riferimenti alle strutture, l'istruzione (*it) avrebbe restituito un altro puntatore, cioè un puntatore di tipo myStruct *.
In questo caso per accedere all'elemento in esso contenuto si sarebbe dovuto usare l'operatore -> in questo modo: (*it)->something.
Su questo vorrei sottolineare una cosa...se utilizzate Eclipse CDT (io ci sono capitato con Helios), potreste essere tratti in inganno dall'autocompletamento. Se scrivete it->some e poi utilizzate l'autocompletamento, questo vi mostrerà comunque "something" o qualsiasi altro elemento della struttura. E' un bug che mi ha fatto perdere un bel po di tempo :-)

Per concludere vediamo ora come accedere agli elementi di un iteratore quando in essi è contenuto un oggetto di tipo class. Come vedremo, è praticamente uguale al caso precedente.
Ecco il codice di esempio:

#include <iostream>
#include <list>

using namespace std;


class Persona {

private:
    string nome;
    string cognome;

public:

    Persona(string nome, string cognome): nome(nome), cognome(cognome){};

    string getNome() { return nome; }
    string getCognome() { return cognome; };
};


int main(int argc, char **argv) {

    list<Persona> l;

    Persona *p1 = new Persona(string("Ajeje"), string("Brazorf"));
    Persona *p2 = new Persona(string("Maccio"), string("Capatonda"));

    l.push_back(*p1);
    l.push_back(*p2);

    list<Persona>::const_iterator it;
    for(it = l.begin(); it != l.end(); ++it)
        cout << it->getNome() << " " << it->getCognome() << endl;

}

Qui vediamo una semplice classe chiamata Persona. Ha due variabili istanza che vengono inizializzate nel costruttore e due metodi per accedervi.
Il procedimento è molto simile agli esempi precedenti, cambia solo il fatto che questa volta la lista conterrà oggetti di tipo Persona.
Anche l'inizializzazione è uguale all'esempio precedente.
Quello che cambia è che in questo caso non c'è bisogno di deferenziare l'iteratore per accedere ai metodi dell'oggetto. In questo caso l'iteratore può essere considerato esattamente come un puntatore all'oggetto, dunque può essere usato come tale per accedere ai suoi membri pubblici.

Bene..con questo direi che vi ho annoiati abbastanza e posso chiudere il post :-)
Spero che qualcuno trovi utili le cose che ho scritto!
Arrivederci al prossimo post! ^_^