Programmazione Generica - Implementare un Iteratore (1/2)

In questo post parleremo di

• Gerarchia di Iteratori in C++
• Come tradurre in codice i requisiti per un Concept da cppreference.com
• Come implementare un InputIterator con una guida passo passo

La scorsa settimana abbiamo parlato di Iteratori e di come gli Algoritmi offerti dalla Standard Library completino questo pattern introducendo un livello di leggibilità e riusabilità sorprendente. Un buon uso di Algoritmi e Iteratori permette di scrivere codice che sembri quasi linguaggio naturale. Abbiamo visto un esempio di tutto ciò andando a sfruttare std::vector e std::accumulate dalla libreria standard ed espressioni lambda che ci hanno permesso di dare un nome alle operazioni che andavamo a scrivere.

Ora, sfruttare gli algoritmi quando si ha a che fare con strutture dati standard è facile. Tutto è già pensato per funzionare elegantemente insieme. Ma sappiamo bene che nel nostro codice definiamo nuove classi costantemente che astraggano le entità in gioco nel problema che stiamo risolvendo. Come facciamo a rendere le nostre classi compatibili con tutto l'ecosistema degli Algoritmi? In questo articolo vedremo insieme come implementare i nostri Iteratori.

Il Concept di Iteratore

Per dare la possibilità agli sviluppatori di implementare i propri Iteratori, lo standard C++ definisce un'interfaccia comune descritta attraverso dei Concept. I Concept sono una serie di requisiti che un tipo/classe deve soddisfare al fine di essere aderente ad una certa interfaccia. Sono un insieme di metodi da esporre, type-traits da definire e altre proprietà da soddisfare. Se consultiamo la descrizione del Concept di iteratore su cppreference.com scopriamo che gli iteratori sono definiti secondo la seguente gerarchia.

Il diagramma riporta gli iteratori in ordine di proprietà da garantire, da quello meno stringente, InputIterator, a quello più stringente RandomAccessIterator. Ogni classe di iteratore estende quella precedente aggiungendo nuove possibilità.

• InputIterator: E' l'iteratore più semplice. Permette la lettura dell'oggetto puntato e di passare all'elemento successivo, fino alla fine della struttura dati. Elemento fondamentale è che garantisce di poter passare all'elemento successivo una volta sola. Che significa? Significa che se ho un InputIterator it1 e ne faccio una copia per ottenere it2, io posso incrementare it1 e passare all'elemento successivo, ma se facessi la medesima cosa su it2 questa potrebbe fallire. Quando mai potrebbe verificarsi una situazione del genere? Basti pensare ad un iteratore che consumi uno stream di input (ad esempio una stringa digitata da linea di comando dall'utente). Una volta consumato un carattere, questo viene rimosso dallo stream.
• ForwardIterator: Stesse funzionalità esposte da InputIterator, ma supporta l'incremento dell'iteratore all'elemento successivo più volte. Questo è il caso più classico, pensando ad un iteratore su una struttura dati come un vettore o una mappa. Se ancora avessi un ForwardIterator it1 e ne prendessi una copia it2, potrei incrementare sia it1 che it2, poiché, a meno di cancellazioni nella struttura dati, l'elemento successivo sarebbe sempre disponibile in memoria.
• BidirectionalIterator: Aggiunge la possibilità di tornare all'elemento precedente.
• RandomAccessIterator: Permette di puntare a qualunque elemento della serie in tempo costante. Ovvero, se ho un RandomAccessIterator it1 che punta all'elemento i-esimo, posso far avanzare it1 avanti di 5 elementi senza dover passare attraverso gli altri 4

Questa varietà di Concept per Iteratori ci fornisce una grande flessibilità quando dobbiamo implementare il nostro Iteratore. Non è obbligatorio implementare tutta la catena gerarchica. Ci fermiamo quando abbiamo esaurito le funzionalità che vogliamo esporre. Questo è un altro aspetto fondamentale della programmazione generica. Se scriviamo un algoritmo che prende in input un Iteratore, è meglio richiedere l'Iteratore con il minimo numero di requisiti che ci consenta di implementare la nostra funzione. Ad esempio, se devo scrivere un algoritmo se sommi tutti gli elementi di un container, dovrò visitare tutti gli elementi una volta sola. Pertanto il Concept adatto a me sarà InputIterator. E' inutile richiedere un RandomAccessIterator se poi non andrò a sfruttare le sue funzionalità, perché ridurrei la generalità della mia funzione.

Ma adesso basta chiacchierare. Vediamo come implementare il nostro Iteratore per una classe che abbiamo già introdotto settimana scorsa. Una Serie Storica.

Design

Una serie storica è una sequenza di valori, ordinati nel tempo. Il problema delle serie storiche è che a volte presentano valori mancanti. Un'implementazione possibile è quella di usare un vettore di std::pair<double, bool>, dove l'elemento booleano è True quando il valore è presente e False quando l'elemento è mancante. Potrebbe essere interessante implementare un iteratore che permetta di accedere ai soli elementi presenti nella serie storica. La prima bozza della nostra classe TimeSeries potrebbe apparire così.

Vediamo adesso come modificare la nostra classe per fornire la prima versione di un iteratore che iteri sui soli elementi presenti, che chiameremo TimeSeriesIterator. In questo post ci concentreremo sul Concept che funge da base per tutti gli iteratori più complessi: InputIterator.

InputIterator Concept

Consultando cppreference.com, possiamo ottenere una panoramica di tutte le proprietà che TimeSeriesIterator deve soddisfare per essere una valida implementazione di InputIterator. Per prima cosa, in quanto Iteratore, la nostra implementazione deve essere:

• CopyConstructible: Deve esporre un costruttore che permetta di costruire l'iteratore copiando da un'altra istanza di TimeSeriesIterator.
• CopyAssignable: Deve fornire un overload di operator= che permetta di copiare da un'altra istanza di TimeSeriesIterator.
• Destructible: Deve avere un distruttore.
• Dereferenziabile: Deve fornire un overload di operator*().
• Incrementabile: Deve fornire un overload di operator++().
• Swappable: Deve fornire un overload di swap().
• Deve esporre dei std::iterator_traits validi.

Per dare un senso a tutto questo, facciamoci aiutare dal codice.

La prima cosa utile da implementare sono i traits per il nostro iteratore. I traits sono dei nomi standard esposti dal nostro iteratore che rappresentano i tipi in gioco in TimeSeriesIterator e rispetto a cui tutti i metodi sono definiti. Sono anche usati dagli Algoritmi per questioni di programmazione generica. I nomi sono abbastanza parlanti. value_type rappresenta il tipo di dato che il nostro iteratore restituisce una volta dereferenziato, al netto di reference o puntatori. Visto che TimeSeriesIterator ritorna i valori della serie storica non assenti, value_type corrisponde a double. reference rappresenta un reference a value_type, pertanto double&. Stessa cosa per pointer che corrisponde a double*. iterator_category descrive il tipo di iteratore che stiamo implementando, secondo la categorizzazione fornita dalla standard library; nel nostro caso, std::input_iterator_tag. L'ultimo campo, difference_type, espone un tipo di dato in grado di contenere una misura di quanto distano due iteratori l'uno dall'altro. A meno di situazioni atipiche, questo campo può essere assegnato sempre a std::ptrdiff_t.

Passiamo ora agli altri requisiti.

In primis, forniamo un costruttore al nostro TimeSeriesIterator. Il costruttore prende in input un puntatore a TimeSeries (visto che dobbiamo accedere al suo vettore interno) e una posizione all'interno del vettore. Useremo questo costruttore nell'implementazione di begin() ed end() in TimeSeries. Osserviamo che il costruttore va ad inizializzare le due variabili private di TimeSeriesIterator, s e pos. Ma pos non viene inizializzata con il valore passato in position, bensì con il valore ritornato da next_valid_element(). Infatti, vogliamo un iteratore che visiti solo gli elementi non-assenti della serie. next_valid_element() svolge proprio questa funzione. A partire da una posizione di input va a cercare la prima posizione maggiore o uguale per cui TimeSeries presenti un valore.

Seguono un CopyConstructor e un operatore di CopyAssignment che si spiegano da soli.

Arriviamo poi ai due operatori principali, ovvero di pre-incremento operator++() e di dereferenziazione operator*(). L'operatore di pre-incremento svolge la funzione di far avanzare l'istanza di TimeSeriesIterator al successivo elemento valido. Per i nostri scopi, è sufficiente riutilizzare il metodo privato next_valid_element(). Infine si ritorna l'istanza dell'iteratore. D'altro canto, l'operatore di dereferenziazione deve ritornare l'elemento puntato dall'iteratore in qualche forma. Può essere una copia, in tal caso ritornerebbe un value_type, può essere un riferimento non-const, ritornando un reference, o ancora un riferimento const, ritornando un const-reference. Nel nostro caso, scegliamo di ritornare un reference.

Infine, da C++11 si richiede che un Iterator sia anche swappable, ovvero fornisca un metodo swap() che scambi i membri fra due TimeSeriesIterator. Lo implementiamo con il classico utilizzo ricorsivo di swap() sui rispettivi membri.

Terminiamo l'implementazione con i requisiti esplicitamente richiesti da un InputIterator:

• EqualityComparable: Deve fornire un overload di operator==() per confrontare due istante di TimeSeriesIterator (fondamentale per sapere quando si è arrivati alla fine della serie).
• Dereferenziabile come puntatore: Deve fornire un overload di operator->() per garantire una sintassi analoga a quella di un classico puntatore.
• Post-Incrementabile: Deve fornire un overload di operator++(int).

Il codice è abbastanza auto-esplicativo, ma mi soffermo solo su un paio di punti. Per implementare il requisito EqualityComparable è necessario implementare gli operatori di uguaglianza e disuguaglianza. Per minimizzare il rischio di errori, conviene definirne uno per intero (nel nostro caso, operator==()) e definire il secondo in funzione del primo.

In seconda battuta, l'operatore di post-incremento segue un pattern abbastanza standard nell'implementazione di iteratori. Osserviamo che a differenza dell'operatore di pre-incremento, l'iteratore ritornato è una copia invece che un riferimento. Questo perché la semantica del post-incremento è quella di utilizzare il valore corrente dell'iteratore, per poi incrementarlo al termine dell'espressione. Per realizzare questa cosa si ottiene una copia locale dell'iteratore. Si incrementa l'istanza e si ritorna la copia, che punta ancora all'elemento precedente.

Con queste ultime aggiunte abbiamo esaurito i requisiti richiesti da InputIterator Concept. Non rimane che esporre il nostro iteratore attraverso l'interfaccia di TimeSeries.

Per come abbiamo scritto la nostra implementazione di TimeSeriesIterator, il metodo begin() non fa che ritornare un'istanza dell'iteratore costruita passando un puntatore all'oggetto TimeSeries e 0 come posizione iniziale. Se il primo elemento dovesse essere assente, l'iteratore avanzerebbe automaticamente al primo elemento disponibile. Infine, end() ritorna un'istanza di TimeSeriesIterator inizializzato alla posizione appena dopo l'ultimo elemento del vettore data, fungendo da sentinella e segnalando che si è raggiunti la fine della serie.

Non ci resta che testare la nostra implementazione.

Che dovrebbe stampare:

The sum of non-missing elements is 80

Conclusioni

In questo post abbiamo visto passo-passo come sia possibile implementare un InputIterator per le nostre classi, compatibile con gli Algoritmi definiti dalla Libreria Standard. Questo primo articolo ci è servito per porre le basi su cui costruire per estendere TimeSeriesIterator a Concept più articolati. Lo vedremo insieme settimana prossima insieme ad una chicca che ci eviterà tutto questo lavoro ogni volta che dovremo implementare un nuovo Iteratore. Se sei interessato a questa serie di articoli Seguimi su LinkedIn per ricevere una notifica!

Grazie per aver letto fino a qui. Buona settimana e buon lavoro! 😊

Appendice

Il codice completo di questo post:

#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>


class TimeSeries {
public:
  void push_back(double value, bool is_present) {
    data.push_back({value, is_present});
  }


  class TimeSeriesIterator {
  public:
    // Iterator traits
    using value_type = double;
    using reference = value_type &;
    using pointer = value_type *;
    using iterator_category = std::input_iterator_tag;
    using difference_type = std::ptrdiff_t;


    // Constructor
    TimeSeriesIterator(TimeSeries *series, int position)
        : s{series}, pos{next_valid_element(position)} {}


    // CopyConstructible
    TimeSeriesIterator(const TimeSeriesIterator &it)
        : s{it.s}, pos{it.pos} {}


    // CopyAssignable
    TimeSeriesIterator &operator=(const TimeSeriesIterator &it) {
      if (&it == this) return *this;
      s = it.s;
      pos = it.pos;
      return *this;
    }


    // Incrementable
    TimeSeriesIterator &operator++() {
      pos = next_valid_element(pos + 1);
      return *this;
    }


    // Dereferenceable
    reference operator*() { return s->data[pos].first; }


    // Swappable
    friend void swap(TimeSeriesIterator &lhs,
                     TimeSeriesIterator &rhs) {
      using std::swap;
      swap(lhs.s, rhs.s);
      swap(lhs.pos, rhs.pos);
    }


    // EqualityComparable
    friend bool operator==(const TimeSeriesIterator &lhs,
                           const TimeSeriesIterator &rhs) {
      return std::tie(lhs.s, lhs.pos) == std::tie(rhs.s, rhs.pos);
    }
    friend bool operator!=(const TimeSeriesIterator &lhs,
                           const TimeSeriesIterator &rhs) {
      return !(lhs == rhs);
    }


    // Pointer-semantic dereference
    pointer operator->() { return &(s->data[pos].first); }


    // Post-Incrementable
    TimeSeriesIterator operator++(int) {
      auto pre_it = *this;
      ++(*this);
      return pre_it;
    }


  private:
    TimeSeries *s;
    int pos;


    // Return position in 's->data' greater or equal than 'cur'
    // with non-missing element
    int next_valid_element(int cur) {
      auto is_missing = [this](int position) {
        return !s->data[position].second;
      };
      while (cur < s->data.size() && is_missing(cur))
        ++cur;
      return cur;
    }
  };


  using iterator = TimeSeriesIterator;
  iterator begin() { return iterator{this, 0}; }
  iterator end() { return iterator{this, static_cast<int>(data.size())}; }


private:
  using Element = std::pair<double, bool>;
  std::vector<Element> data;
};


int main() {
  auto s = TimeSeries();
  s.push_back(10., true);
  s.push_back(20., false);
  s.push_back(30., true);
  s.push_back(40., true);
  s.push_back(50., false);
  const auto sum = std::accumulate(s.begin(), s.end(), 0.);
  std::cout << "The sum of non-missing elements is " << sum << '\n';
  return 0;
}