Lo standard del linguaggio C++ è composto da regole di sintassi e semantica e da librerie. Una tra le più versatili è la libreria di algoritmi, concepita per lavorare agevolmente su classi contenitore.
Gli algoritmi generici forniti dalla libreria servono a vari scopi (ricerca, manipolazione, ordinamento eccetera). Essi sono resi disponibili sotto forma di API definite in header file di nome algorithm.h. Altre API che logicamente rientrano nella definizione di algoritmi sono invece incluse nello header file numeric.h, anche se il loro uso non è limitato al solo calcolo numerico. La loro implementazione, che fa un uso massivo del costrutto template, è basata sui principi di programmazione generica.
Lo scopo della libreria è quello di fornire una base consolidata ed efficiente per algoritmi d'uso comune, incentrata come sempre su politiche di controllo statico dei tipi.
L'uso degli algoritmi standard di C++ ha molteplici benefici, oltre quello di non dovere costantemente "reinventare la ruota". Nel rispetto delle buone prassi di programmazione ispirate dalle revisioni più recenti dello standard C++, l'uso degli algoritmi consente di ottenere codice performante e soprattutto universalmente comprensibile.
In effetti, uno dei problemi più ricorrenti della programmazione in ambito professionale, è quello di manutenere e revisionare codice altrui. L'uso di API standard consente di minimizzare la parte boilerplate e di focalizzare l'attenzione sulle sezioni di codice più rilevanti.
Data la vastità dell'argomento, in questa lezione non ci addentreremo nel dettaglio di ogni algoritmo della libreria. Cercheremo invece di capire la filosofia che ha ispirato la progettazione degli algoritmi e come essi rientrano a pieno titolo nella set di costrutti del C++ odierno e di quello futuro.
L'algoritmo più semplice
La libreria algorithms predispone molteplici API per la scansione di una classe contenitore e la manipolazione dei suoi elementi. Il più semplice di tutti è la funzione std::for_each che consente di eseguire un blocco di istruzioni sugli elementi di una collezione.
Nell'esempio seguente, essa è impiegata per simulare l'esecuzione sincrona di più richieste HTTP a URL fittizie.
#include <iostream>
#include <vector>
#include <thread> // std::this_thread::sleep_for
#include <chrono> // std::chrono::seconds
#include <algorithm>
void HTTPGetRequest(const std::string& url)
{
std::cout << "GET request: " << url << std::endl;
std::this_thread::sleep_for(std::chrono::seconds(1));
}
int main()
{
std::vector<std::string> urls = {
"URL_1",
"URL_2",
"URL_3",
"URL_4",
"URL_5",
"URL_6",
};
std::for_each(urls.begin(), urls.end(), HTTPGetRequest);
return 0;
}Per brevità, il codice che effettua la richiesta HTTP è sostituito da una chiamata alla funzione std::this_thread::sleep_for.
Gli argomenti della funzione sono gli iteratori di inizio e fine intervallo ed un puntatore al callback HTTPGetRequest. In generale, quest'ultimo è una funzione o un funtore che accetta come parametro un oggetto di tipo compatibile con quello degli elementi della collezione. Il valore di ritorno, se diverso da void, è ignorato.
La funzione std::for_each è responsabile dell'avanzamento dell'iteratore e della sua dereferenziazione, nonché dell'invocazione del callback. La tipologia della classe contenitore è indifferente, purchè essa supporti l'uso di un iteratore forward (cioè dotato dell'operatore di incremento).
Si noti che l'uso della funzione std::for_each è del tutto equivalente all'uso di costrutti quali il ciclo for ed il ciclo for su intervalli (C++11). Il frammento seguente è un modo alternativo di fare sostanzialmente la stessa cosa, senza scomodare una funzione di libreria ed in maniera estremamente concisa:
for(auto url : urls)
HTTPGetRequest(url);Alla luce di tale osservazione è perfettamente legittimo chiedersi perché si sia pensato di definire una funzione che espleta una funzionalità già garantita dal set di istruzioni di base del linguaggio.
Per rispondere a tale domanda bisogna guardare all'evoluzione dello standard da un punto di vista storico e filosofico.
In prima istanza, l'introduzione di std::for_each è in effetti antecedente allo standard C++11, ed in quanto tale ha consentito di rendere meno prolissa la definizione di cicli for su classi contenitore quando i programmatori non avevano a disposizione nè la parola chiave auto nè i cicli basati su intervalli.
Tuttavia, a differenza del ciclo for su intervalli, std::for_each consente di definire esplicitamente l'inizio e la fine dell'intervallo di iterazione. Le evoluzioni più recenti dello standard hanno inoltre perfezionato l'astrazione del concetto di iterazione nella libreria algorithms introducendo le politiche di esecuzione.
A partire dalla revisione C++17 è infatti possibile decidere se iterare in modo sincrono o asincrono con l'aggiunta di un singolo parametro, come mostrato nel listato seguente:
#include <iostream>
#include <vector>
#include <thread> // std::this_thread::sleep_for
#include <chrono> // std::chrono::seconds
#include <algorithm>
#include <execution> // std::execution::par
void HTTPGetRequest(const std::string& url)
{
std::cout << "GET request: " << url << std::endl;
std::this_thread::sleep_for(std::chrono::seconds(1));
}
int main()
{
std::vector<std::string> urls = {
"URL_1",
"URL_2",
"URL_3",
"URL_4",
"URL_5",
"URL_6",
};
std::cout << "Sequencial execution:\n";
std::for_each(urls.begin(), urls.end(), HTTPGetRequest);
std::cout << "Parallel execution:\n";
std::for_each(std::execution::par, urls.begin(), urls.end(), HTTPGetRequest);
return 0;
}In questo caso, il parametro aggiuntivo std::execution::par serve a indicare che l'esecuzione delle varie iterazioni del ciclo può essere parallelizzata. Il modo in cui la parallelizzazione viene implementata dipende dalla piattaforma target. A seconda della politica selezionata e dell'architettura è possibile che la parallelizzazione sia implementata in multi-threading oppure con istruzioni vettorializzate SIMD.
Allo stato attuale, il supporto alla parallelizzazione è ancora in fase di completamento da parte di molti compilatori. Ad esempio, GCC 9.1 supporta il parallelismo negli algoritmi standard introducendo una dipendenza alla libreria Intel TBB (Threading Building Blocks). Per compilare il listato precedente è quindi necessario installare la libreria ed includerla nel processo di linking con il seguente comando:
g++ -std=c++17 main.cpp -ltbbLa funzione std::for_each è un buon esempio della filosofia che ha guidato lo sviluppo della libreria di algoritmi.
Le politiche di esecuzione, così come altre astrazioni, sono state concettualizzate molto prima della loro effettiva implementazione. La libreria è stata concepita per integrare gradualmente nel tempo tutte le funzionalità previste dalla commissione che sviluppa lo standard. Anche API come std::for_each, che possono sembrare ridondanti, risultano in realtà strumenti accessori molto potenti e flessibili, se valutati nel contesto delle revisioni più avanzate dello standard e di quelle future.
Algoritmi più comuni
La libreria di algoritmi include decine di API molto variegate per scopo e modalità di impiego. Gli algoritmi più popolari sono probabilmente quelli di ricerca, ordinamento, copia e manipolazione di cui si da un esempio di uso nel listato seguenti:
#include <iostream>
#include <iterator> // std::ostream_iterator
#include <vector>
#include <list>
#include <random> // std::mt19937
#include <functional> // std::multiplies
#include <numeric> // std::iota, std::accumulate, std::transform etc.
#include <algorithm>
// funzione predicato per numeri interi
bool isEven(int n)
{
return (n % 2 == 0);
}
int main()
{
std::vector<int> v(15);
// inizializza il vettore v con numeri progressivi a partire da 1
std::iota(v.begin(), v.end(), 1);
// copia gli elementi di v in una sequenza di valori per lo standard output separati da uno spazio
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
// stampa la posizione a cui si trova il valore 5 in v
auto found = std::find(v.begin(), v.end(), 5);
if (found != v.end())
{
std::cout << "Element 5 found at position "
<< std::distance(v.begin(), found) << "\n";
}
// calcola la somma degli elementi di v
std::cout << "Sum: "
<< std::accumulate(v.begin(), v.end(), 0) << "\n";
// calcola il prodotto degli elementi di v
std::cout << "Product: "
<< std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>()) << "\n";
// cambia l'ordine degli elementi di v in modo casuale
std::shuffle(v.begin(), v.end(), std::mt19937{std::random_device{}()});
// riposiziona gli elementi di v in ordine decrescente
std::sort(v.rbegin(), v.rend());
// popola la lista l con valori booleani true/false se il corrispondente elemento
// in v è pari/dispari.
std::list<bool> l(v.size());
std::transform(v.begin(), v.end(), l.begin(), isEven);
// conta il numero di elementi pari in v
std::cout << "Even numbers: "
<< std::count_if(v.begin(), v.end(), isEven) << "\n";
// calcola il numero di elementi dispari in v (not_fn richiede C++17)
std::cout << "Odd numbers: "
<< std::count_if(v.begin(), v.end(), std::not_fn<bool(int)>(isEven)) << "\n";
return 0;
}Come anticipato, la tipologia degli algoritmi standard è molto estesa, e per molti di essi il rilascio dello standard C++17 ha apportato cambiamenti significativi sotto forma di nuovi sovraccarichi come visto in precedenza nel caso di std::for_each.
Inoltre, in molti casi è possibile avvalersi di API definite nello header file functional.h per l'uso di puntatori a funzione in osservanza delle politiche di controllo statico dei tipi. Tipicamente tali puntatori a funzione sono operatori unari (predicati) come nel caso della funzione isEven o binari per eseguire operazioni di calcolo, confronto eccetera.
Paradigmi e modelli di programmazione
Dagli esempi precedenti si evince che il design degli di algoritmi standard e quello delle classi contenitore è basato su astrazioni di ampio respiro, in grado di conciliare problematiche molto diverse tra loro come il calcolo numerico, la manipolazione di dati eterogenei mediante l'uso di predicati e operatori sovraccaricati, la gestione della memoria, l'implementazione di filtri e persino l'interfacciamento con i canali di I/O.
Il tutto cercando di ottimizzare le prestazioni su ogni piattaforma target mediante l'uso di implementazioni efficienti.
Gli algoritmi come abbiamo visto, si adattano anche a stili e paradigmi di programmazione differenti. Ad esempio l'implementazione di std::accumulate previene effetti collaterali e richiama lo stile di programmazione funzionale, mentre std::for_each è sicuramente molto più vicino alla programmazione procedurale.
A partire dallo standard C++17 è inoltre emersa in maniera più evidente la tendenza a incorporare negli algoritmi standard non solo paradigmi, ma anche modelli di programmazione.
In particolare la possibilità di applicare politiche di esecuzione alternative a quella sequenziale di fatto ha aperto la strada all'implementazione di API di alto livello come std::transform_reduce.
Il listato seguente riprende il primo esempio in cui si è fatto uso di std::for_each per eseguire in maniera asincrona richieste HTTP. In questa variante, std::transform_reduce è usata per eseguire le richieste e calcolare un valore globale di ritorno, indicativo del fatto che esse siano andate a buon fine o meno.
#include <iostream>
#include <vector>
#include <thread> // std::this_thread::sleep_for
#include <chrono> // std::chrono::seconds
#include <algorithm>
#include <execution> // std::execution::par
#include <functional> // std::logical_and
bool HTTPGetRequest2(const std::string& url)
{
std::cout << "GET request: " << url << std::endl;
std::this_thread::sleep_for(std::chrono::seconds(1));
// nella simulazione, ogni richiesta ha esito positivo
return true;
}
int main()
{
std::vector<std::string> urls = {
"URL_1",
"URL_2",
"URL_3",
"URL_4",
"URL_5",
"URL_6",
};
std::cout << "Parallel execution with return values:\n";
bool ok = std::transform_reduce(std::execution::par, urls.begin(), urls.end(),
true, std::logical_and<bool>(), HTTPGetRequest2);
std::cout << "Request success: " << ok << std::endl;
return 0;
}In definitiva, in questo esempio è possibile osservare come una sola API dello standard racchiuda in nuce un modello complesso come MapReduce. La naturale conclusione è che gli algoritmi standard, seppure perfettibili, sono una risorsa preziosa e molto potente.
Evoluzioni future
La libreria di algoritmi standard è stata aggiornata in modo sostanziale nelle revisioni più recenti dello standard ed è destinata a cambiare ancora per recepire le innovazioni future.
In particolare, gli standard successivi a C++20 molto probabilmente incorporeranno una astrazione di più alto livello per le definizione degli intervalli o range per rendere trasparente l'uso degli iteratori.
Inoltre un nuovo costrutto sintattico, noto come concepts, consentirà la definizione di restrizioni e criteri vari per l'esecuzione di algoritmi sotto forma di predicati valutabili a tempo di compilazione.
Come esempio, sarà possibile decorare la definizione di una funzione template che implementa un algoritmo di ordinamento specificando che necessita di iteratori ad accesso casuale per poter operare con una sintassi più semplice.
Ciò andrà a beneficio non solo della espressività e leggibilità del codice, ma anche della qualità dei messaggi di diagnostica emessi dal compilatore, che risultano ad oggi particolarmente criptici e di scarsa utilità nella comprensione degli errori di codifica derivati dall'uso di template.