I Contenitori Associativi di STL

In un articolo precedente abbiamo parlato dei contenitori sequenziali di STL ( Standard Template Library ) come i vettori, le deque ed altro, in questo nuovo articolo prendiamo in esame gli altri tipi di contenitori, quelli associativi, di cui fanno parte set e multiset, map e multimap. I set e multiset contengono elementi semplici, i map e multimap contengono coppie chiave-valore e sono equivalenti ai dizionari o array associativi di altri librerie e linguaggi. I set ed i map non ammettono elementi ripetuti, mentre i multiset ed i multimap possono contenerne e vengono inseriti a seconda dell’ordine di inserimento.
Tutti i contenitori associativi di STL sono implementati utilizzando una variante della struttura ad alberi binari, gli alberi red-black che consentono di tenere ordinati gli elementi all’interno della struttura. Gli alberi binari hanno sempre un tempo di ricerca logaritmico: il logaritmo in base 2 di 1000 vale circa 10, il che significa che con al massimo 10 confronti si riesce a trovare un elemento su 1000 e con 20 confronti si trova un elemento fra un milione.

#include <iostream>
#include <set>

using namespace std;

int main(int argc, char* argv[])
{
   char c;
   set<int> s;

   s.insert(34);
   s.insert(12);
   s.insert(11);
   s.insert(23);
   s.insert(24);
   s.insert(15);

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

   cin >> c;

   return 0;
}

Come vi avevo detto i contenitori associativi contengono gli elementi in maniera ordinata al contrario delle hash table, ecco perché trovare un valore al loro interno è molto veloce.

#include <iostream>
#include <set>
#include <time.h>

using namespace std;

int main(int argc, char* argv[])
{
   char c;
   int i;
   set<int& s;
   set<int>::iterator it;

   srand((unsigned int)time(NULL));
   for (i = 0; i < 3000; ++i)
      s.insert(rand() % 5000 + 1);

   s.count(i);
   cout << "Abbiamo inserito " <<
         i << " numeri interi" << endl << endl;

   it = s.find(75);
   if (it != s.end())
      cout << "Abbiamo estratto il 75" << endl;
   else
      cout << "Non abbiamo estratto il 75" << endl;

   cout << endl;    cin >> c;

   return 0;
}

Le map, come abbiamo detto in precedenza, sono formate da coppie chiave-valore e quindi risultano estremamente utili ad esempio nei lavori su piano cartesiano della geometria analitica oppure per tenere traccia dell’altezza di alcune persone.

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main(int argc, char* argv[])
{
   char c;
   string s;

   map m;
   map::iterator it;

   m.insert(pair("Mario", 1.84));
   m.insert(pair("Simone", 1.72));
   m.insert(pair("Enrico", 1.75));
   m.insert(pair("Patrizia", 1.68));
   m.insert(pair("Cesare", 1.90));

   cout << "I nostri amici:" << endl;
   for (it = m.begin(); it != m.end(); ++it)
      cout << (*it).first << endl;

   cout << endl << "Digita il nome per sapere l'altezza"
      << endl;
   cin >> s;

   it = m.find(s);
   if (it == m.end())
      cout << "Amico non trovato" << endl;
   else
      cout << "L'altezza di " << s << ": " << (*it).second
           << endl;

   cout << endl;
   cin >> c;

   return 0;
}

Ho cercato di creare degli esempi molto semplici e che vi mostrino come si programma con questi contenitori che sono veramente potenti per la gestione dei dati in memoria. Per domande o spiegazioni varie sono a vostra disposizione nel forum.