Introduzione agli iteratori in C++

Sebbene possiamo usare gli indici per accedere ai caratteri di una stringa o agli elementi di un vector, esiste un meccanismo più generale, noto come iteratori, che possiamo usare per lo stesso scopo. Come vedremo nelle prossime lezioni, oltre a vector, la libreria definisce diversi altri tipi di contenitori. Tutti i contenitori della libreria hanno iteratori, ma solo alcuni di essi supportano l'operatore indice. Tecnicamente parlando, una stringa non è un tipo contenitore, ma string supporta molte delle operazioni dei contenitori. Come abbiamo visto, string, come vector, ha un operatore indice. Come i vector, anche le stringhe hanno iteratori.

Come i puntatori, gli iteratori ci danno accesso indiretto a un oggetto. Nel caso di un iteratore, quell'oggetto è un elemento in un contenitore o un carattere in una stringa. Possiamo usare un iteratore per recuperare un elemento e gli iteratori hanno operazioni per muoversi da un elemento all'altro. Come con i puntatori, un iteratore può essere valido o non valido. Un iteratore valido denota un elemento oppure denota una posizione successiva all'ultimo elemento in un contenitore. Tutti gli altri valori di iteratore sono non validi.

Uso degli Iteratori

A differenza dei puntatori, non usiamo l'operatore indirizzo (&) per ottenere un iteratore. Invece, i tipi che hanno iteratori hanno membri che restituiscono iteratori. In particolare, questi tipi hanno membri chiamati begin ed end. Il membro begin restituisce un iteratore che denota il primo elemento (o primo carattere), se ce n'è uno:

// il compilatore determina il tipo di b ed e;
// b denota il primo elemento ed e denota una posizione oltre l'ultimo elemento in v
auto b = v.begin(), e = v.end(); // b ed e hanno lo stesso tipo

L'iteratore restituito da end è un iteratore posizionato "uno oltre la fine" del contenitore (o stringa) associato. Questo iteratore denota un elemento inesistente "oltre la fine" del contenitore. Viene usato come marcatore che indica quando abbiamo processato tutti gli elementi. L'iteratore restituito da end è spesso chiamato iteratore off-the-end o abbreviato come "iteratore end". Se il contenitore è vuoto, begin restituisce lo stesso iteratore restituito da end.

Se il contenitore è vuoto, gli iteratori restituiti da begin ed end sono uguali, ossia sono entrambi iteratori off-the-end.

In generale, non conosciamo (né ci interessa) il tipo preciso che un iteratore ha. In questo esempio, abbiamo usato auto per definire b ed e. Di conseguenza, queste variabili hanno qualunque tipo venga restituito rispettivamente dai membri begin ed end. Ritorneremo su questo punto più avanti

Operazioni sugli Iteratori

Gli iteratori supportano solo poche operazioni, che sono elencate nella tabella sottostante. Possiamo confrontare due iteratori validi usando == o !=. Gli iteratori sono uguali se denotano lo stesso elemento o se sono entrambi iteratori off-the-end per lo stesso contenitore. Altrimenti, sono diversi.

Come con i puntatori, possiamo dereferenziare un iteratore per ottenere l'elemento denotato da un iteratore. Inoltre, come i puntatori, possiamo dereferenziare solo un iteratore valido che denota un elemento. Dereferenziare un iteratore non valido o un iteratore off-the-end ha un comportamento indefinito.

Come esempio, proviamo a scrivere un programma che mette in maiuscolo il primo carattere di una stringa. Possiamo farlo usando un iteratore come segue:

string s("una stringa");

// assicuriamoci che s non sia vuota
if (s.begin() != s.end()) {
    // it denota il primo carattere in s
    auto it = s.begin();

    // rende quel carattere maiuscolo
    *it = toupper(*it);
}

Nel programma, prima controlliamo che s non sia vuota. In questo caso, lo facciamo confrontando gli iteratori restituiti da begin ed end. Quegli iteratori sono uguali se la stringa è vuota. Se sono diversi, c'è almeno un carattere in s.

All'interno del corpo dell'if, otteniamo un iteratore al primo carattere assegnando l'iteratore restituito da begin a it. Dereferenziamo quell'iteratore per passare quel carattere a toupper. Dereferenziamo anche it sul lato sinistro dell'assegnamento per assegnare il carattere restituito da toupper al primo carattere in s. L'output di questo programma sarà:

Una stringa

Spostare gli Iteratori da un Elemento all'Altro

Gli iteratori usano l'operatore di incremento (++) per spostarsi da un elemento al successivo. Incrementare un iteratore è un'operazione logicamente simile all'incremento di un intero. Nel caso degli interi, l'effetto è di "aggiungere 1" al valore dell'intero. Nel caso degli iteratori, l'effetto è di "avanzare l'iteratore di una posizione".

Poiché l'iteratore restituito da end non denota un elemento, non può essere incrementato o dereferenziato.

Proviamo a scrivere un programma che mette in maiuscolo tutti i caratteri della prima parola in una stringa. Possiamo farlo usando un ciclo for che inizia con un iteratore al primo carattere e continua finché non incontriamo uno spazio o raggiungiamo la fine della stringa:

// processa i caratteri in s finché non finiamo i caratteri o incontriamo uno spazio
for (auto it = s.begin(); it != s.end() && !isspace(*it); ++it)
    // mette in maiuscolo il carattere corrente
    *it = toupper(*it);

Questo ciclo itera attraverso i caratteri in s, fermandosi quando incontriamo un carattere di spazio. Tuttavia, questo ciclo accede a questi caratteri usando un iteratore, non un indice.

Il ciclo inizia inizializzando it da s.begin, il che significa che it denota il primo carattere (se esiste) in s. La condizione controlla se it ha raggiunto la fine di s. In caso contrario, la condizione poi dereferenzia it per passare il carattere corrente a isspace per vedere se abbiamo finito. Alla fine di ogni iterazione, eseguiamo ++it per avanzare l'iteratore per accedere al carattere successivo in s.

Il corpo di questo ciclo è lo stesso dell'ultima istruzione nell'if precedente. Dereferenziamo it per passare il carattere corrente a toupper e assegniamo la lettera maiuscola risultante di nuovo nel carattere denotato da it.

Tipi di Iteratore

Proprio come non conosciamo il tipo preciso del membro size_type di un vector o di una string, così pure, generalmente non conosciamo, e non abbiamo bisogno di conoscere, il tipo preciso di un iteratore. Invece, come con size_type, i tipi di libreria che hanno iteratori definiscono tipi chiamati iterator e const_iterator che rappresentano i tipi di iteratore effettivi:

// it può leggere e scrivere elementi vector<int>
vector<int>::iterator it;

// it2 può leggere e scrivere caratteri in una string
string::iterator it2;

// it3 può leggere ma non scrivere elementi
vector<int>::const_iterator it3;

// it4 può leggere ma non scrivere caratteri
string::const_iterator it4;

Un const_iterator si comporta come un puntatore const. Come un puntatore const, un const_iterator può leggere ma non scrivere l'elemento che denota; un oggetto di tipo iterator può sia leggere che scrivere. Se un vector o string è const, possiamo usare solo il suo tipo const_iterator. Con un vector o string non const, possiamo usare sia iterator che const_iterator.

Le Operazioni begin ed end

Il tipo restituito da begin ed end dipende dal fatto che l'oggetto su cui operano sia const. Se l'oggetto è const, allora begin ed end restituiscono un const_iterator; se l'oggetto non è const, restituiscono iterator:

vector<int> v;
const vector<int> cv;

// it1 ha tipo vector<int>::iterator
auto it1 = v.begin();

// it2 ha tipo vector<int>::const_iterator
auto it2 = cv.begin();

Spesso questo comportamento predefinito non è quello che vogliamo. Per ragioni che spiegheremo nelle prossime lezioni, è solitamente meglio usare un tipo const (come const_iterator) quando dobbiamo leggere ma non dobbiamo scrivere su un oggetto. Per permetterci di chiedere specificamente il tipo const_iterator, lo standard C++11 ha introdotto due nuove funzioni chiamate cbegin e cend:

// it3 ha tipo vector<int>::const_iterator
auto it3 = v.cbegin();

Come fanno i membri begin ed end, questi membri restituiscono iteratori al primo elemento e uno oltre l'ultimo elemento nel contenitore. Tuttavia, indipendentemente dal fatto che il vector (o string) sia const, restituiscono un const_iterator.

Combinare Dereferenziazione e Accesso ai Membri

Quando dereferenziamo un iteratore, otteniamo l'oggetto che l'iteratore denota. Se quell'oggetto ha un tipo classe, potremmo voler accedere a un membro di quell'oggetto. Per esempio, potremmo avere un vector<string> di stringhe e potremmo aver bisogno di sapere se un dato elemento è vuoto. Assumendo che it sia un iteratore in questo vector, possiamo controllare se la stringa che denota è vuota come segue:

(*it).empty();

Per ragioni che copriremo nella prossime lezioni, le parentesi in (*it).empty() sono necessarie. Le parentesi dicono di applicare l'operatore di dereferenziazione a it e di applicare l'operatore punto al risultato della dereferenziazione di it. Senza parentesi, l'operatore punto si applicherebbe a it, non all'oggetto risultante:

// dereferenzia it e chiama il membro empty sull'oggetto risultante
(*it).empty();

// ERRORE: tenta di recuperare il membro chiamato empty da it
// ma it è un iteratore e non ha un membro chiamato empty
*it.empty();

La seconda espressione viene interpretata come una richiesta di recuperare il membro empty dall'oggetto chiamato it. Tuttavia, it è un iteratore e non ha un membro chiamato empty. Quindi, la seconda espressione è errata.

Per semplificare espressioni come questa, il linguaggio definisce l'operatore freccia (l'operatore ->). L'operatore freccia combina dereferenziazione e accesso ai membri in una singola operazione. Cioè, it->mem è un sinonimo di (*it).mem.

Per esempio, assumiamo di avere un vector<string> chiamato text che contiene i dati caricati da un file di testo. Ogni elemento nel vector è una frase o una stringa vuota che rappresenta un'interruzione di paragrafo. Se vogliamo stampare il contenuto del primo paragrafo da text, scriveremmo un ciclo che itera attraverso text finché non incontriamo un elemento che è vuoto:

// stampa ogni riga in text fino alla prima riga vuota
for (auto it = text.cbegin();
    it != text.cend() && !it->empty(); ++it)
    cout << *it << endl;

Iniziamo inizializzando it per denotare il primo elemento in text. Il ciclo continua finché o processiamo ogni elemento in text o troviamo un elemento che è vuoto. Finché ci sono elementi e non abbiamo visto un elemento vuoto, stampiamo l'elemento corrente. Vale la pena notare che poiché il ciclo legge ma non scrive sugli elementi in text, usiamo cbegin e cend per controllare l'iterazione.

Alcune Operazioni sui vector Invalidano gli Iteratori

Nelle precedenti lezioni abbiamo notato che ci sono implicazioni del fatto che i vector possono crescere dinamicamente. Abbiamo anche notato che una tale implicazione è che non possiamo aggiungere elementi a un vector all'interno di un range for. Un'altra implicazione è che qualsiasi operazione, come push_back, che cambia la dimensione di un vector potenzialmente invalida tutti gli iteratori in quel vector. Esploreremo come gli iteratori diventano non validi in più dettaglio nelle prossime lezioni.

Per ora, è importante sapere che i cicli che usano iteratori non dovrebbero aggiungere elementi al contenitore a cui gli iteratori si riferiscono.

Esercizi

• Rivedi il ciclo che stampava il primo paragrafo in text per invece cambiare gli elementi in text che corrispondono al primo paragrafo in tutto maiuscolo. Dopo aver aggiornato text, stampa i suoi contenuti.

  Soluzione:

  // mette in maiuscolo ogni riga in text fino alla prima riga vuota
  for (auto it = text.begin();
      it != text.end() && !it->empty(); ++it) {
      // mette in maiuscolo ogni carattere nella riga corrente
      for (auto &c : *it)
          c = toupper(c);
  }
  
  // stampa il contenuto di text
  for (const auto &s : text)
      cout << s << endl;
  

• Scrivi un programma per creare un vector con dieci elementi int. Usando un iteratore, assegna a ogni elemento un valore che è il doppio del suo valore corrente.

  Soluzione:

  #include <iostream>
  #include <vector>
  
  using std::cout; using std::endl;
  using std::vector;
  
  int main() {
      // crea un vector con 10 elementi inizializzati a 0
      vector<int> v(10);
  
      // Inizializza il vector con valori 0, 1, ..., 9
      for (size_t i = 0; i < v.size(); ++i)
          v[i] = i;
  
      // assegna a ogni elemento il doppio del suo valore corrente
      for (auto it = v.begin(); it != v.end(); ++it)
          *it = *it * 2;
  
      // stampa i valori nel vector usando un iteratore const
      for (auto it = v.cbegin(); it != v.cend(); ++it)
          cout << *it << " ";
      cout << endl;
  
      return 0;
  }
  

Aritmetica degli Iteratori

Incrementare un iteratore sposta l'iteratore di un elemento alla volta. Tutti i contenitori della libreria hanno iteratori che supportano l'incremento. Similarmente, possiamo usare == e != per confrontare due iteratori validi in qualsiasi tipo di contenitore della libreria.

Gli iteratori per string e vector supportano operazioni aggiuntive che possono spostare un iteratore di più elementi alla volta. Supportano anche tutti gli operatori relazionali. Queste operazioni, che sono spesso chiamate aritmetica degli iteratori, sono descritte nella tabella seguente:

Operazioni Aritmetiche sugli Iteratori

Possiamo aggiungere (o sottrarre) un valore intero a un iteratore. Farlo restituisce un iteratore posizionato avanti (o indietro) di tanti elementi quanti sono il valore. Quando aggiungiamo o sottraiamo un valore intero a un iteratore, il risultato deve denotare un elemento nello stesso vector (o string) o denotare uno oltre la fine del vector (o string) associato. Come esempio, possiamo calcolare un iteratore all'elemento più vicino al punto medio di un vector:

// calcola un iteratore all'elemento più vicino al punto medio di vi
auto mid = vi.begin() + vi.size() / 2;

Se vi ha 20 elementi, allora vi.size()/2 è 10. In questo caso, impostiamo mid uguale a vi.begin() + 10. Ricordando che gli indici iniziano da 0, questo elemento è lo stesso di vi[10], l'elemento dieci oltre il primo.

Oltre a confrontare due iteratori per uguaglianza, possiamo confrontare iteratori di vector e string usando gli operatori relazionali (<, <=, >, >=). Gli iteratori devono essere validi e devono denotare elementi in (o uno oltre la fine di) lo stesso vector o string. Per esempio, assumendo che it sia un iteratore nello stesso vector di mid, possiamo controllare se it denota un elemento prima o dopo mid come segue:

// processa elementi nella prima metà di vi
if (it < mid) {
    // it denota un elemento prima del punto medio
} else {
    // it denota un elemento al punto medio o dopo
}

Possiamo anche sottrarre due iteratori purché si riferiscano a elementi nello stesso vector o string, oppure uno oltre la fine dello stesso. Il risultato è la distanza tra gli iteratori. Per distanza intendiamo la quantità per cui dovremmo cambiare un iteratore per ottenere l'altro. Il tipo di risultato è un tipo intero con segno chiamato difference_type. Sia vector che string definiscono difference_type. Questo tipo è con segno, perché la sottrazione potrebbe avere un risultato negativo.

Uso dell'Aritmetica degli Iteratori

Un algoritmo classico che usa l'aritmetica degli iteratori è la ricerca binaria. Una ricerca binaria cerca un particolare valore in una sequenza ordinata. Opera guardando l'elemento più vicino al centro della sequenza. Se quell'elemento è quello che vogliamo, abbiamo finito. Altrimenti, se quell'elemento è più piccolo di quello che vogliamo, continuiamo la nostra ricerca guardando solo gli elementi dopo quello rifiutato. Se l'elemento centrale è più grande di quello che vogliamo, continuiamo guardando solo nella prima metà. Calcoliamo un nuovo elemento centrale nell'intervallo ridotto e continuiamo a cercare finché o troviamo l'elemento o finiamo gli elementi.

Possiamo realizzare una ricerca binaria usando gli iteratori come segue:

// Supponiamo che text sia un vector<string> ordinato
vector<string> text;
string obiettivo; // la stringa che stiamo cercando

// beg ed end denoteranno l'intervallo che stiamo cercando
auto beg = text.begin(), end = text.end();
// punto medio originale
auto mid = text.begin() + (end - beg)/2;

// finché ci sono ancora elementi da guardare e non abbiamo ancora trovato obiettivo
while (mid != end && *mid != obiettivo) {
    // l'elemento che vogliamo è nella prima metà?
    if (obiettivo < *mid)
        // se sì, aggiusta l'intervallo per ignorare la seconda metà
        end = mid;
    else
        // altrimenti, l'elemento che vogliamo è nella seconda metà
        // inizia a cercare con l'elemento subito dopo mid
        beg = mid + 1;

    // nuovo punto medio
    mid = beg + (end - beg)/2;
}

// se mid è uguale a end, non abbiamo trovato obiettivo
if (mid == end)
    cout << "non trovato\n";
else {
    cout << "trovato\n";
    cout << "Posizione: " << distance(text.begin(), mid) << endl;
}

Iniziamo definendo tre iteratori: beg sarà il primo elemento nell'intervallo, end uno oltre l'ultimo elemento, e mid l'elemento più vicino al centro. Inizializziamo questi iteratori per denotare l'intero intervallo in un vector<string> chiamato text.

Il nostro ciclo prima controlla che l'intervallo non sia vuoto. Se mid è uguale al valore corrente di end, allora abbiamo finito gli elementi da cercare. In questo caso, la condizione fallisce e usciamo dal while. Altrimenti, mid si riferisce a un elemento e controlliamo se mid denota quello che vogliamo. Se sì, abbiamo finito e usciamo dal ciclo.

Se abbiamo ancora elementi da processare, il codice dentro il while aggiusta l'intervallo spostando end o beg. Se l'elemento denotato da mid è maggiore di obiettivo, sappiamo che se obiettivo è in text, apparirà prima dell'elemento denotato da mid. Pertanto, possiamo ignorare gli elementi dopo mid, cosa che facciamo assegnando mid a end. Se *mid è più piccolo di obiettivo, l'elemento deve essere nell'intervallo di elementi dopo quello denotato da mid. In questo caso, aggiustiamo l'intervallo facendo in modo che beg denoti l'elemento subito dopo mid. Sappiamo già che mid non è quello che vogliamo, quindi possiamo eliminarlo dall'intervallo.

Alla fine del while, mid sarà uguale a end o denoterà l'elemento che stiamo cercando. Se mid è uguale a end, allora l'elemento non era in text.

Esercizi

• Leggi un insieme di interi in un vector<int>. Stampa la somma di ogni coppia di elementi adiacenti. Modifica il tuo programma in modo che stampi la somma del primo e dell'ultimo elemento, seguita dalla somma del secondo e del penultimo, e così via. Usa gli iteratori per accedere agli elementi del vector.

  Soluzione:

  #include <iostream>
  #include <vector>
  
  using std::cin; using std::cout; using std::endl;
  using std::vector;
  
  int main() {
      vector<int> v;
      int val;
  
      // legge un insieme di interi in v
      while (cin >> val)
          v.push_back(val);
  
      // stampa la somma di ogni coppia di elementi adiacenti
      if (v.size() < 2) {
          cout << "Non ci sono abbastanza elementi." << endl;
          return 1;
      }
  
      cout << "Somma di ogni coppia di elementi adiacenti:" << endl;
      for (auto it = v.begin(); it != v.end() - 1; ++it)
          cout << *it + *(it + 1) << " ";
      cout << endl;
  
      // stampa la somma del primo e dell'ultimo elemento,
      // del secondo e del penultimo, ecc.
      cout << "Somma del primo e dell'ultimo elemento, "
           << "del secondo e del penultimo, ecc.:" << endl;
      auto beg = v.begin();
      auto end = v.end() - 1; // end denota l'ultimo elemento
      while (beg < end) {
          cout << *beg + *end << " ";
          ++beg;
          --end;
      }
      // se c'è un elemento centrale non ancora sommato
      // (vettore di dimensione dispari)
      if (beg == end)
          cout << *beg; // o *end, sono uguali in questo caso
      cout << endl;
  
      return 0;
  }
  

• Nel programma di ricerca binaria, perché abbiamo scritto mid = beg + (end - beg) / 2; invece di mid = (beg + end) / 2;?

  Soluzione:

  La sottrazione di due iteratori (end - beg) restituisce la distanza tra gli iteratori, che è un valore intero. Dividendo questa distanza per 2, otteniamo la metà della distanza tra beg ed end. Aggiungendo questo valore a beg, otteniamo un iteratore che punta al punto medio dell'intervallo.

  D'altra parte, l'espressione (beg + end) / 2 non è valida perché non possiamo sommare direttamente due iteratori. Gli iteratori rappresentano posizioni in un contenitore e non hanno un significato matematico diretto come i numeri interi. Pertanto, l'operazione di somma tra due iteratori non è definita e il compilatore genererebbe un errore.