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!

Posta un commento o usa questo indirizzo per il trackback.

Commenti

  • juhan  Il 9 giugno 2012 alle 07:01

    Bello e facile. Il limite delle liste in C++ è che tutti gli elementi devono essere dello stesso tipo.
    [troll mode ON] io conosco una classe di linguaggi dove le liste sono vere liste! [troll mode OFF]
    OK, OK, OK! m’è scappato.

    • glipari  Il 9 giugno 2012 alle 10:10

      🙂 ( vedrai come ti metto elementi di tipo diverso in una lista con il C++ … )

  • derkling  Il 10 giugno 2012 alle 22:09

    Ottimo tutorial!
    Unica nota: C++11 ha esteso la generalizzazione di begin() ed end() che ora possono essere applicati anche ad array nativi. Quindi, nell’esempio di sopra scompare l’unica chiamata particolare a “print” fatta a linea 36… a tutto vantaggio della generalizzazione.

    • glipari  Il 10 giugno 2012 alle 23:04

      Grazie! L’estensione agli array del begin()/end() del C++11 non l’avevo ancora mai vista, grazie per l’informazione!

  • Gabriele  Il 17 giugno 2012 alle 19:14

    Bellissimo articolo, grazie!

  • Daniela  Il 30 giugno 2012 alle 19:52

    Grazie^^ mi hai evitato di impazzire^^

  • Daniela  Il 16 luglio 2012 alle 12:53

    Ciao, come potrei fare per eliminare un elemento interno alla lista?
    Grazie mille^^

    • glipari  Il 16 luglio 2012 alle 13:11

      Usa il metodo erase():

      http://www.cplusplus.com/reference/stl/list/erase/

      a cui devi passare l’iteratore all’elemento che devi cancellare. Se usi erase() su un vector, fai attenzione perché la cancellazione invalida eventuali altri iteratori al contenitore. Per la lista, invece, non ci sono problemi.

      • Daniela  Il 17 luglio 2012 alle 17:33

        Ancora grazie!

  • Federico  Il 13 maggio 2013 alle 14:35

    Sei fantastico. Se tutti i tutorial fossero così, il mondo sarebbe migliore. XD

  • SMarches  Il 26 giugno 2013 alle 17:02

    Bella spiegazione, complimenti !

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: