Contenitori Sequenziali della Libreria STL

Un contenitore sequenziale in STL contiene una collezione di oggetti secondo un preciso ordine lineare. Il valore esportato da un contenitore sequenziale X<T> è appunto T. Tra le strutture che fanno parte di questo gruppo di contenitori abbiamo vector, list e deque. La classe vector<T> rappresenta il classico array dinamico, le sue peculiarità sono un accesso casuale con tempi di accesso costanti, tempi di inserzione e rimozione in fondo costanti e lineari altrove.

// File Corso.h

class CMyPunto
{
public:
   int m_x, m_y;

   CMyPunto(int x, int y)
      { m_x = x; m_y = y; };

   void StampaProdotto();
};

// File Corso.cpp

#include <iostream>
#include <vector>
#include "Corso.h"

using namespace std;

void CMyPunto::StampaProdotto()
{
   cout << "Il prodotto di " << m_x << " e " << m_y 
      << ": " << m_x * m_y << endl;
}

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

   vector vPunti;
   vPunti.push_back(CMyPunto(15, 23));
   vPunti.push_back(CMyPunto(5, 32));
   vPunti.push_back(CMyPunto(33, 45));
   vPunti.push_back(CMyPunto(17, 12));
   vPunti.push_back(CMyPunto(19, 4));

   for (int i = 0; i < (int)vPunti.size(); ++i)
      vPunti.at(i).StampaProdotto();

   cout << endl << endl;    cin >> k;

   return 0;
}

In questo esempio abbiamo utilizzato la funzione size() per sapere la quantità di valori contenuti nel vettore, ma non tutti i contenitori hanno questa caratteristica. In STL è preferibile utilizzare gli iteratori, infatti c’è la funzione begin() che restituisce l’iteratore iniziale, rbegin() l’iteratore a fine serie, si tratta comunque in questo caso di iteratori random. Per quanto riguarda l’allocazione dinamica dei dati occorre dire che il vettore presenta, come tutti i contenitori, un template di classe di default che si chiama allocator. Nell’implementazione HP i vector per default devono avere dimensione zero all’inizio ed un incremento di 100 per ogni elemento in più oltre lo spazio allocato, quindi se si desidera risparmiare spazio in memoria occorre eliminare lo spazio in più, tutto questo a meno di indicare una dimensione iniziale. Vediamo allora di riscrivere il nostro esempio considerando quello che abbiamo appena spiegato.

...
vector::iterator i;
for (i = vPunti.begin(); i < vPunti.end(); ++i)
   i->StampaProdotto();

cout << endl << endl;

vector::reverse_iterator j;
for (j = vPunti.rbegin(); j < vPunti.rend(); ++j)
   j->StampaProdotto();
...
}

La classe list<T> rappresenta una lista doppiamente linkata, prevede tempi costanti di inserzione e rimozione, tempi di accesso costanti ad entrambi gli estremi e tempi lineari nelle parti intermedie, gli iteratori sono bidirezionali.

...
list lPunti;
lPunti.push_back(CMyPunto(3, 6));
lPunti.push_back(CMyPunto(17, 12));
lPunti.push_back(CMyPunto(15, 3));
lPunti.push_front(CMyPunto(11, 7));
lPunti.push_front(CMyPunto(8, 6));

list::iterator i;
for (i = lPunti.begin(); i != lPunti.end(); ++i)
   i->StampaProdotto();
...

La classe deque<T> è una struttura dati ad accesso casuale ottimizzata per il push ed il pop efficiente dei due estremi, provvede tempi costanti di accesso ovunque e tempi costanti di inserzione e rimozioni agli estremi, mentre tempi lineari di inserzione e rimozione al suo interno, gli iteratori sono random.

...
deque dPunti;
dPunti.push_back(CMyPunto(12, 65));
dPunti.push_front(CMyPunto(14, 72));
dPunti.push_front(CMyPunto(5, 5));
dPunti.pop_front();
dPunti.push_back(CMyPunto(7, 18));

deque::iterator i;
for (i = dPunti.begin(); i < dPunti.end(); ++i)
   i->StampaProdotto();
...

La libreria STL offre una gestione dei contenitori sequenziali molto veloce, una volta compreso il funzionamento risulta immediato l’uso di queste strutture dati dinamiche che altrimenti sarebbero molto complicate da gestire attraverso il solo utilizzo classico delle librerie del C++.