Gli Algoritmi Generici di STL

Negli scorsi articoli su STL ( Standard Template Library ) abbiamo parlato dei contenitori sequenziali: vettori, liste e deque. Questa volta vedremo gli algoritmi generici con i quali possiamo operare sui dati contenuti nei contenitori. Esistono moltissimi algoritmi nella libreria STL, questa sede non è adatta a prenderne in considerazione tutti, si tratta solo di fare delle piccole ricerche su internet per trovare moltissima teoria di questi algoritmi. L’insieme degli algoritmi generici di STL costituisce un dizionario completo dei pattern di programmazione su sequenze di valori. Tra gli algoritmi di uso più comune abbiamo generate che consente di generare sequenze di valori, come per esempio quella di Fibonacci.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Fibonacci(void)
{
   static int r;
   static int f1 = 0;
   static int f2 = 1;

   r = f1 + f2 ;
   f1 = f2 ;
   f2 = r ;

   return f1 ;
}

int main(int argc, char** args)
{
   int k;

   vector<int> v(20);
   generate(v.begin(), v.end(), Fibonacci);

   // Stampo la serie
   vector<int>::iterator i;
   for (i = v.begin(); i < v.end(); ++i)
      cout << *i << endl;

   cout << endl;
   cin >> k;

   return 0;
}

Altri algoritmi di uso comune sono ad esempio:

• for_each che itera un’operazione data su tutti gli elementi di una sequenza
• copy che copia tutti gli elementi di una sequenza su di una nuova sequenza
• transform che applica un’operazione su tutti gli elementi di una sequenza e raccoglie i risultati
• count che conta tutti gli elementi uguali ad uno dato
• replace, remove e find per fanno proprio quello che sembrano
• sort, binary_search che compiono operazioni su sequenze ordinate

Generalmente questi algoritmi hanno come parametri la posizione iniziale e finale della sequanza di valori su cui operare, espressi come una  coppia di iteratori ed una funzione.
Vediamo alcuni esempi utilizzando questi algoritmi. Nel precedente esempio avevamo mostrato come creare una sequenza di Fibonacci di 20 elementi e per stampare avevamo utilizzato un ciclo for per iterare la lista di valori, in STL è meglio utilizzare for_each, vediamone l’uso.

...
void print_value(int i)
{
   cout << i << endl;
}

int main(int argc, char** args)
{
   ...
   // Stampo la serie
   for_each(v.begin(), v.end(), print_value);
   ...
}

Un altro modo per stampare a video un elenco di valori è copiarli direttamente su stdout:

...
copy(v.begin(), v.end(), ostream_iterator<int>(cout, "\n"));
...

Un ostream_operator virtualizza uno ostream sotto forma di un iteratore di sola scrittura, è un template che deve essere parametrizzato con il tipo da stampare e deve essere inizializzato da un reference ad uno ostream e con una stringa opzionale, terminata in zero, di default la stringa è vuota.
Prima di concludere vediamo gli algoritmi di sorting, ecco un esempio:

...
struct myClass
{
   bool operator() (int i, int j) { return i > j; }
} myObject;

int main(int argc, char** args)
{
   int k;

   vector<int> v(20);
   generate(v.begin(), v.end(), Fibonacci);

   // ordinamento decrescente
   sort(v.begin(), v.end(), myObject);

   // Stampo la serie
   copy(v.begin(), v.end(), ostream_iterator<int>(cout, "\n"));

   cout << endl;
   cin >> k;

   return 0;
}

Da questi esempi scommetto che state già apprezzando la potenza di questa libreria generica di classi. Non disperate perché su questo blog scriverò altri articoli su STL, perché a mio avviso è ideale per lavorare con base di dati in memoria, sia per l’alto numero di funzioni già fatte, sia per l’ottimizzazione delle procedure.