Modern range-based iteration

La libreria standard è basata sul concetto di iteratore,  ovvero un oggetto che “punta” ad un elemento di un range e che consente di “spostarsi” (iterare) attraverso gli altri elementi, imitando per quanto possibile la sintassi usata con i puntatori. Tutti gli iteratori sono classificati in base ad alcune categorie, all’incirca a seconda che permettano lettura e/o scrittura, e a seconda di che tipi di spostamento supportano (questa spiegazione va oltre lo scopo dell’articolo – basic – ma per saperne di più è possibile partire da qui). In particolare, un vero puntatore è un caso particolare di iteratore:

int arr[] = {1,2,3,4};
int* ptr = &arr[1]; // ptr punta a 2
++ptr; // ptr punta a 3
*ptr = 10;
// arr è ora {1,2,10,4}

Questo articolo tratta alcune linee guida a proposito di iterazione su range. Un range è inteso come due iteratori che rappresentano l’inzio e la fine dell’intervallo di elementi sui quali iterare. Non si tratta, però, di iteratori qualsiasi bensì di quelli che lo standard definisce come InputIterator. Questo categoria di iteratori è la più semplice e consente di scorrere serialmente gli elementi in “sola lettura” (solo input – a “scrivere” sono gli OutputIterator). Per essere più rigorosi (ma non troppo), un InputIterator è un qualsiasi tipo di oggetto che supporta almeno queste operazioni:

• value-semantics (ha un costruttore di copia, un operator= e un distruttore pubblici)
• si può testare l’uguaglianza (operator==, operator!=)
• può essere dereferenziato (*it, it->member), ma il risultato va trattato come se fosse di sola lettura (si può scrivere auto x = *it; ma non *it = 10 come sopra)
• può essere incrementato di 1 (con operator++)

Altre operazioni sono implicate (ad esempio,  la funzione swap) o supportate con certe limitazioni (il costruttore di default). Si noti però che non si parla mai della sequenza di oggetti “puntati”, che infatti potrebbe addirittura… non esistere! Un InputIterator potrebbe “fingere” di iterare su elementi che vengono creati al volo nell’istante in cui si de-referenzia (si vedrà un esempio più avanti). Secondo lo standard, de-referenziando due copie dello stesso iteratore non necessariamente si ottiene lo stesso valore!

Comunque, l’idea fondamentale è che è necessario definire alcune funzioni anziché ereditare da una classe base. Qualsiasi classe che “si comporta” come un InputIterator è allora considerata un InputIterator. Si tratta del classico approccio della generic programming, meglio formalizzato nei Concepts.

Spesso ci troviamo a scrivere cicli su strutture dati, ad esempio su vettori o liste. La libreria standard fornisce diversi algoritmi che internamente operano come dei cicli. Il più semplice è il for_each, che dati due InputIterator Begin/End esegue una certa funzione per ogni elemento nel range [Begin, End).

Un container può essere “descritto” da un range [Begin, End) e per questo definisce le quattro funzioni:

• begin(), cbegin() (ovvero const-begin, che produce un iteratore di sola lettura)
• end(), cend() (ovvero const-end)

begin() è, chiaramente, un InputIterator che punta al primo elemento del container, end(), invece, punta subito fuori dal range (one-past-the-last-element). Ci sono diverse motivazioni per questa scelta architetturale, ma (semplificando) è possibile pensare che questa sia in linea col classico pattern:

for (int i=0; i!=END; ++i) // END escluso
...

con i = END il ciclo si arresta, quindi l’ultima iterazione è proprio con i = END – 1.

Nota: gli iteratori ritornati dalle funzioni begin/end di un container sono generalmente più avanzati di un InputIterator (ad esempio possono supportare contemporaneamente input e output), ma tutti comunque ne supportano le specifiche.

Supponiamo, ora, di avere una classe Plot che supporta un replot:
class Plot
{
public:
...
void replot();
...
};
dato un vector di Plot potremmo ridisegnare ogni plot con un banale ciclo, sfruttando le funzioni sopra citate:
vector<Plot> plots;
for (auto it = plots.begin(); it != plots.end(); ++it)
{
i->replot();
}
Ma potremmo usare anche un for_each:
for_each(plots.begin(), plots.end(), [](Plot& plot)
{
plot.replot();
});
Cosa scegliere e perché? Ci sono almeno quattro buone ragioni per le quali scegliere un algoritmo invece di scrivere un ciclo:

1) Efficienza: un algoritmo è potenzialmente vincente perché:

• evita di ripetere alcune chiamate (e.g. plots.end()), mantenendo il codice compatto,
• gli implementatori delle STL possono specializzare particolari algoritmi in base al container, massimizzando le performance,
• (generalmente) gli algoritmi sono sofisticati e implementati rispettando lo stato dell’arte (e.g. sort). anche algoritmi apparentemente banali, come potrebbe essere “visitare tutti gli elementi” possono essere ottimizzati e nascondere  gradi di sofisticazione insospettabili!

2) Correttezza: scrivere un ciclo a mano è error-prone, richiede di controllare la validità del range in cui si itera e potenzialmente fa perdere più tempo a scrivere controlli che non a implementare il core del proprio algoritmo.

3) Manutenibilità: è più facile mettere mano su un codice che usa algoritmi standard, documentati e provati, oppure su listati completamente scritti a mano (e più verbosi)? Generalmente è molto più semplice leggere e comprendere un codice che utilizza algoritmi standard ed uno dei motivi principali è che questi ultimi sono ben documentati (e i loro nomi hanno un significato che esprime l’intento del programmatore). Essi rappresentano un vero e proprio “vocabolario” con cui comunicare (ad esempio nel proprio team) e dal quale attingere funzionalità già pronte.

4) Astrazione: non sempre occorre avere a che fare con gli iteratori. Con un ciclo scritto a mano è necessario utilizzarli, dereferenziarli, … Con un algoritmo, invece, è possibile utilizzare direttamente l’oggetto “puntato”, come nell’esempio sopra, dove accediamo ad un’istanza di business, Plot, e non ad un iteratore.

Primo DO della giornata: ove possibile, preferire l’utilizzo degli algoritmi ai cicli scritti a mano.

Questo primo DO è generale, non da applicarsi sol al C++. Veniamo al nocciolo di questo post. Iterare su un range: quali sono le nuove linee guida?

All’inizio abbiamo detto che ogni container può essere descritto da un range (Begin. End]. Abbiamo anche fatto vedere come utilizzare le funzioni begin/end per iterare su un container. Il range (Begin, End] è del tipo:

vector<int> vec {1,2,3,4,5};
auto first = vec.begin();
auto one_past_last = vec.end();
// [first, one_past_last) "descrive" vec

L’unico problema è che questo approccio non è abbastanza generico. Ad esempio non può essere applicato agli array C-style (e.g. int arr[]). Come rimediare? Il C++11 introduce le funzioni non-membro begin/end, con un overload per gli array C-style. Oltre a supportare gli array, queste due funzioni danno uniformità e coerenza, promuovendo l’estensibilità (è possibile creare delle specializzazioni per i propri container) e incrementando l’incapsulamento. Le non-member functions begin/end sono fatte così:

// C++11
template< class C >
auto begin( C& c ) -> decltype(c.begin());

// C++11 - overload per gli array C
template< class T, size_t N >
T* begin( T (&array)[N] );

DO: Utilizzare le funzioni non-membro begin(x) e end(x) invece di x.begin() e x.end().

for_each( begin(vec), end(vec), ... ) // C++11
E se avessimo bisogno di cbegin() e cend() ? Il C++14 introduce anche queste due funzioni non-membro, sfuggite al C++11:
// C++14
template< class C >
auto cbegin( const C& c ) -> decltype(std::begin(c));

// C++14
template< class C >
auto cend( const C& c ) -> decltype(std::end(c));
DO: [C++14] Utilizzare le funzioni non-membro cbegin(x) e cend(x) invece di x.cbegin() e x.cend().

Concludiamo questo primo articolo a proposito di iterazione su range con una seconda novità del C++11: il range-based for loop (RBFL). Questo costrutto equivale ad utilizzare un for_each su un container. Stesse garanzie di performance ma più compattezza:

// C++11
for (const auto& elem : vec)
{
cout << elem << " ";
}

// quando vec è una variabile locale, è come scrivere
for_each(begin(vec), end(vec), [](const T& elem)
{
cout << elem << " ";
});
La sintassi è semplice e probabilmente già vista in altri linguaggi. Da notare la possibilità di usare auto. Chiaramente, anche qui, il concetto di iteratore è celato e si opera direttamente sugli oggetti contenuti nel vettore.

DO: Utilizzare il range-based for loop al posto del for_each, è più semplice e compatto.

Il RBFL opera su strutture x che supportino il concetto di iterazione, ovvero:

• abbiano le funzioni membro x.begin() e x.end(), oppure,
• abbiano le funzioni non-membro begin(x) e end(x) (trovate con ADL – Argument Dependent Lookup), oppure,
• per le quali esistono le specializzazioni di std::begin(x) e std::end(x).

Le funzioni devono ritornare degli InputIterator (in realtà il requisito è più “leggero”, come vedremo nel prossimo esempio. Maggiori dettagli qui).

Bonus track

Il RBFL permette di iterare su una qualsiasi struttura “iterabile”. Abbiamo detto poco fa cosa vuol dire, ma vogliamo vederne un esempio pratico?

Supponiamo di voler iterare su tutti gli interi entro un certo intervallo, qualcosa del tipo:

for (int i=0; i<100; ++i)
...

Possiamo usare il RBFL senza creare una sequenza intermedia? Sì, per farlo abbiamo proprio bisogno di scrivere una struttura iterabile e un InputIterator che ne abiliti l’iterazione. Per il nostro scopo, in realtà, dobbiamo solo implementare un wrapper ad un finto container che simuli una lista crescente di numeri ed un suo iteratore.

Per ricapitolare, vogliamo qualcosa del genere:

for (auto i : range{0,10})
{
cout << i << " ";
}
// 0 1 2 3 4 5 6 7 8 9
Ribadisco che questo è solo un esempio, molto probabilmente non efficiente quanto un for da 0 a N!

Iniziamo da questo “finto container”. Abbiamo detto che per usare il RBFL è sufficiente implementare una delle tre opzioni:

• funzioni membro x.begin() e x.end(), oppure
• funzioni non-membro begin(x) e end(x) (trovate con ADL – Argument Dependent Lookup), oppure
• specializzazioni std::begin(x) e std::end(x)

Scegliamo la prima e supponiamo, per un attimo, di aver già pensato al nostro InputIterator ad-hoc:
class range_t
{
public:
class range_it
{
// lo vediamo dopo
}

private:
range_it start_it;
range_it end_it;
};
La nostra classe range_t mantiene due iteratori che rappresentano inizio e fine range. Ora vediamo una possibile implementazione di range_it:
class range_it
{
public:
range_it(int val)
: value{val}
{
}

private:
int value;
};

L’idea (banale) è di wrappare un valore del range in questo iteratore range_it. Le operazioni su un range_it sono in realtà operazioni sul valore che wrappa.

Non siamo totalmente conformi alle specifiche di un InputIterator ma siamo dentro ai requisiti del RBFL (perché questo ha bisogno solo degli operatori che abbiamo implementato):

for (auto i : range_t{0, 10})
{
cout << i << " ";
}
// 0 1 2 3 4 5 6 7 8 9

L’esempio è volutamente semplice. Restano aperte alcune questioni (anch’esse non complicate da affrontare) che lasciamo ai lettori, come ad esempio:

• generalizzare il range per qualsiasi tipo numerico (attenzione all’operator!= su float e double…),
• completare range_it in modo che implementi tutte le specifiche di un InputIterator,
• personalizzare lo step (e.g. {0, 10} a step di 0.1).