Programmazione C++: liste e iteratori

Le liste

Nei post sulla programmazione funzionale ho rotto le scatole con le liste, la struttura dati di base di ogni buon linguaggio funzionale che si rispetti. Ci sono le liste in C++? Si, ma non sono poi così flessibili. In realtà, come vedremo più avanti, ogni contenitore può essere trattato come una lista, perché il C++ generalizza il concetto in una maniera molto potente e flessibile.

Dicevo nello scorso post che i vettori non sono sempre la struttura dati più adatta per le nostre esigenze, specialmente quando dobbiamo inserire e estrarre dal mezzo, perché gli elementi sono memorizzati consecutivamente in memoria e per inserire nel mezzo devo spostare una buona metà di elementi.

Nella lista, invece, gl elementi non sono memorizzati consecutivamente in memoria, ma possono stare dove gli pare. In pratica, il contenitore list della libreria standard implementa la buona vecchia lista linkata, gioia e dolori degli studenti del corso di “Fondamenti di Informatica I”.

Facciamo subito un esempio che è meglio.

#include <list>
#include <iostream>

using namespace std;

int main()
{
    list<int> lista;

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

    for (int i=0; i<10; i++) {
        cout << "Elemento " << i << ": " << lista.front() << endl;
        lista.pop_front();
    }
    return 0;
}

Per prima cosa, stavolta includiamo l’header file list invece di vector. Con il primo ciclo for inseriamo 10 elementi in fondo alla lista. Con il secondo ciclo for, prima stampiamo a video il contenuto della testa della lista (ottenuta con la funzione front), e poi lo estraiamo (con la funzione pop_front()).

Se volessi leggere gli elementi a partire dal fondo, posso usare back() e push_back(), come segue:

#include <list>
#include <iostream>

using namespace std;

int main()
{
    list<int> lista;

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

    for (int i=0; i<10; i++) {
        cout << "Elemento " << i << ": " << lista.back() << endl;
        lista.pop_back();
    }
    return 0;
}

E se volessi leggere un elemento nel mezzo? Qui non si può usare l’accesso diretto (o random) come nel vettore. In altre parole, scrivere

cout << lista[5];

darebbe un errore di compilazione perché la lista non ha la possibilità di visitare il quinto elemento con una somma e una moltiplicazione, ma deve scorrere tutti gli elementi uno alla volta.

Inoltre, entrambi questi programmi stampano la lista, ma la distruggono man mano che leggono. non è molto comodo vorremmo poter leggere senza distruggere.

Iteratori

Per scorrere gli elementi si usa il concetto di iteratore, che è anche un design pattern, ovvero una tecnica di programmazione ben studiata nei sacri testi della programmazione object oriented. Cos’è un iteratore?
In OOP, l’iteratore è un oggetto che permette di visitare gli elementi in un contenitore in un certo ordine. L’iteratore disaccoppia il contenitore dal metodo di visita, e semplifica l’interfaccia (un sacco di paroloni, ma poi in pratica è molto semplice, vedrete).

In C++ l’iteratore è una generalizzazione del concetto di puntatore, che ci permette di scorrere gli elementi di un contenitore in ordine, utilizzando una sintassi simile a quella dei puntatori. Ecco come scorrere gli elementi di una lista.

#include <list>
#include <iostream>

using namespace std;

int main()
{
    list<int> lista;

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

    list<int>::iterator p;
    int i = 0;
    for (p = lista.begin(); p != lista.end(); p++) 
        cout << "Elemento " << i++ << ": " << *p << endl;  

    return 0;
}

(Sembra molto complicato a prima vista, ma vedrete che tra un po’ ve lo semplifico. E’ che all’inizio, per capire le cose per bene, bisogna prendere la strada lunga, poi quando le nostre gambe sono ben allenate possiamo prendere la scorciatoia).

Quindi, l’iteratore qui l’ho chiamato p, e che si tratti di un iteratore lo capite dalla dichiarazione del tipo:

list::iterator p;

Poi, nel ciclo for, p prende inizialmente il valore restituito dalla funzione begin(). Questa funzione (metodo in dialetto OOP) restituisce l’iteratore che punta al primo elemento della lista. Il ciclo for si ferma quando p è pari al valore della funzione end(), che restituisce l’iteratore che punta al valore successivo all’ultimo elemento della lista. In pratica, end() restituisce un puntatore a un elemento non valido. A ogni iterazione del ciclo for, il valore di p è incrementato (p++): questo vuol dire che al termine di ogni iterazione, p passerà da un elemento al successivo.

Per ottenere il valore dell’elemento, basta utilizzare l’indirezione, ovvero l’operatore *:

cout << "Elemento " << i++ << ": " << *p << endl;  

Ok, fin qui credo sia semplice da capire, anche se un po’ complicato da scrivere.
E adesso, sorpresa: gli iteratori esistono anche per i vettori!
Ecco l’esempio:

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> vettore;

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

    vector<int>::iterator p;
    int i = 0;
    for (p = vettore.begin(); p != vettore.end(); p++) 
        cout << "Elemento " << i++ << ": " << *p << endl;  

    return 0;
}

Come vedete ho semplicemente sostituito list con vector, e lista con vettore, e tutto funziona come prima.

Ok, se mi avete seguito fin qui, adesso è venuto il momento delle magie, attenzione. Per prima cosa, scrivo una funzione print che stampa tutti gli elementi di una lista:

void print(list<int>::iterator a, list<int>::iterator b)
{
    list<int>::iterator p;
    cout << "[";
    for (p=a; p!=b; ++p) cout << *p << ", ";
    cout << "]" << endl;
}

Adesso per stampare una lista mi basta scrivere:

print(lista.begin(), lista.end());

Però, se volessi stampare un vettore dovrei riscrivere la funzione… posso generalizzarla? Certo che sì, basta usare gli ingiustamente famigerati template:

template<class Iter>
void print(Iter a, Iter b)
{
    cout << "[";
    for (Iter p=a; p!=b; ++p) cout << *p << ", ";
    cout << "]" << endl;
}

Ecco, adesso la funzione non dipende più dal fatto che ho una lista: basta che abbia una qualsiasi cosa che si comporti come un iteratore. Qualsiasi cosa significa anche un normale puntatore C! Ecco un esempio finale in cui metto tutto insieme:

#include <list>
#include <vector> 
#include <string> 
#include <deque> 
#include <iostream>

using namespace std;

template<class Iter>
void print(Iter a, Iter b)
{
    cout << "[";
    for (Iter p=a; p!=b; ++p) cout << *p << ", ";
    cout << "]" << endl;
}


int main()
{
    list<int> lista;
    vector<int> vettore;

    for (int i=0; i<10; i++) 
        lista.push_back(i);
    for (int i=0; i<15; i++) 
        vettore.push_back(2*i);

    deque<string> coda = {"Ok", "Panico", "insalate", "di", "cibernetica"}; 
    int array[] = {1,2,3,5,7,11,13,17};

    string str = "C++ rulez";

    print(lista.begin(), lista.end());
    print(vettore.begin(), vettore.end());
    print(coda.begin(), coda.end());
    print(array, array+8);
    print(str.begin(), str.end());

    return 0;
}

Se salvate questo file con il nome “stampa_tutto.cpp”, potete compilare con il comando:

g++ -std=c++0x stampa_tutto.cpp

Questo produce il file a.out, e lanciandolo otterrete il seguente output:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, ]
[Ok, Panico, insalate, di, cibernetica, ]
[1, 2, 3, 5, 7, 11, 13, 17, ]
[C, +, +,  , r, u, l, e, z, ]

Spiegazione breve (che si è fatto tardi):
Ho preparato 4 contenitori: una lista, un vettore, una coda (con il tipo deque), e un classico array C. Le ho inizializzate in modo diverso (con un ciclo for le prime due, con una inizializzazione in linea le ultime 2).
Infine, ho preparato una stringa str.

Quindi, ho chiamato print() su tutte. L’unica chiamata strana è quella per l’array C: poichè un array non è un oggetto C++ ma una struttura dati C, non ha le funzioni membro begin() e end(). Quindi, ho passato direttamente il puntatore al primo elemento (array) e il puntatore successivo all’ultimo elemento (array+8).

Infine: anche la stringa è un contenitore! In particolare, è un contenitore di caratteri! Possiede gli iteratori, e le funzioni begin() e end(), come il vettore e la lista. Per cui, non vedo perchè non potrei chiamare la mia funzione print() su di essa, non credete?

Cone questo, oggi è tutto, alla prossima!

About these ads