Dal C al C++/Utilizzo basilare di librerie/I contenitori standard

In linguaggio C, l'unico contenitore di oggetti predefinito è l'array di lunghezza fissa, che può essere multidimensionale.

Praticamente in qualunque programma non banale c'è l'esigenza di organizzare i dati in strutture dinamiche, cioè che occupano uno spazio definito solo in fase di esecuzione. A questo scopo, la libreria standard fornisce vari contenitori, tra i quali quello che probabilmente è il più usato è "vector".

Per esempio, dovendo memorizzare i numeri da 1 a 10, e poi stamparli in ordine rovesciato, si può scrivere il seguente programma.

#include <vector>
#include <iostream>
using namespace std;
int main() {
   vector<int> v;
   const int n = 10;
   for (int i = 1; i <= n; ++i) {
      v.push_back(i);
   }
   for (int i = n - 1; i >= 0; --i) {
      cout << v[i] << " ";
   }
}

La variabile "v" rappresenta un array dinamico di interi, inizialmente vuoto.

Nel primo ciclo "for" la funzione membro "push_back" viene chiamata dieci volte per inserire altrettanti valori nel contenitore. Se al posto di 10 si scrive 1000, si ottiene un altro programma sicuramente funzionante; quest'ultimo, stamperà i numeri da 1000 a 1. Se invece si scrive il numero 1000000000 (cento milioni) il programma potrebbe funzionare se il sistema ha abbastanza memoria, oppure potrebbe fallire, sollevando un'eccezione per fallita allocazione di memoria.

L'oggetto "v", appena dopo essere stato creato, occupa spazio solo sullo stack.

Quando si aggiunge il primo oggetto al contenitore, viene allocato nella memoria dinamica un buffer sufficiente a contenere un oggetto di tipo "int", e viene copiato in tale buffer l'oggetto "1", passato come parametro alla funzione membro "push_back".

Quando si aggiunge il secondo oggetto al contenitore, se il buffer allocato in precedenza ha abbastanza spazio libero, viene copiato in tale buffer l'oggetto "2", proprio a fianco dell'oggetto "1" memorizzato in precedenza. Se invece il buffer allocato non ha abbastanza spazio per il nuovo elemento, allora viene allocato un buffer più grande, l'intero contenuto del vecchio buffer viene copiato nel nuovo, il nuovo elemento viene copiato nel nuovo buffer, e infine il vecchio buffer viene deallocato.

Il contenuto esatto dell'oggetto "vector" non è definito dallo standard e quindi dipende dall'implementazione della libreria standard. Una possibile implementazione è la seguente: un puntatore alla zona di memoria dove c'è il buffer contenente gli elementi, il numero di elementi contenuti nel contenitore, e il numero di elementi contenibili nel buffer. Ovviamente il numero di elementi contenibili è sempre maggiore o uguale al numero di elementi contenuti. Se il contenitore non contiene elementi, non è necessario che sia allocato alcun buffer.

La libreria standard del C++ definisce alcune tipologie di contenitori, che possono soddisfare varie esigenze, anche se non tutte.

Si tratta di contenitori tipizzati, cioè, a differenza di molti linguaggi di programmazione orientati agli oggetti, un oggetto contenitore può contenere oggetti di un solo tipo.

Per implementare un contenitore tipizzato si deve usare un template di classe, in cui il parametro del template è il tipo degli oggetti contenuti.

Per esempio la seguente istruzione:

vector<int> a;

definisce la variabile "a" di tipo "vector<int>". Il tipo "vector<int>" non è definito nella libreria standard. Quest'ultima definisce solo il template di classe "vector", ed è l'istruzione citata che istanzia il template creando in fase di compilazione la classe "vector<int>".

I contenitori principali definiti dalla libreria standard sono i seguenti template di classe:

vector: è un array dinamico. L'oggetto contenitore contiene un puntatore a un buffer allocato dinamicamente. Gli elementi sono allineati in tale buffer. Aggiungendo oggetti in fondo al vector, vengono posti in tale buffer. Quando lo spazio del buffer è esaurito, automaticamente viene allocato un buffer più grande, l'intero vecchio buffer viene copiato nel nuovo buffer e si dealloca il vecchio buffer. Il suo scopo è permettere accessi indicizzati estremamente veloci e aggiunte di elementi in fondo abbastanza veloci.
list: è una lista a collegamento doppio (in inglese, "doubly-linked list"). Ogni nodo della lista è allocato autonomamente, e contiene un puntatore all'elemento successivo e un puntatore all'elemento precedente. Aggiungendo un elemento in cima, in fondo o in posizione intermedia, viene allocato un nuovo elemento e si impostano i puntatori in modo da mantenere la struttura di lista. Il suo scopo è permettere aggiunte ed eliminazioni veloci in qualunque punto della sequenza. Non consente accessi diretti, ma solo sequenziali in entrambe le direzioni.
deque: questa parola è l'abbreviazione dell'espressione inglese "Double-Ended QUEue", cioè coda a due estremità. Il suo scopo è permettere accessi diretti abbastanza veloci, e aggiunte ed eliminazioni veloci all'inizio o alla fine della sequenza.
set: è un insieme matematico ordinato di oggetti, cioè è una collezione ordinata priva di doppioni. È rappresentato da un albero di ricerca i cui nodi sono gli elementi contenuti. Quando si tenta di inserire un nuovo elemento, questo viene cercato nell'albero; se trovato, non viene in realtà inserito; se non trovato, viene inserito nella posizione che compete al suo valore. La ricerca per valore ha complessità logaritmica, a confronto della complessità lineare dei tre contenitori già presentati. Per poter ordinare gli elementi, è necessario che dati due elementi "a" e "b", sia definita l'espressione "a < b". Per esempio, questo è vero sia per i numeri predefiniti che per le stringhe, ma non per i numeri complessi.
multiset: è una struttura simile al "set", ma può contenere più volte lo stesso oggetto.
map: è un array associativo ordinato, chiamato anche "dizionario". Tale template è parametrizzato da due tipi: il tipo della chiave e il tipo del valore. È un "set" di associazioni chiave-valore, in cui il criterio di ricerca e di uguaglianza si basa solo sulla chiave.
multimap: è una struttura simile al "map", ma per ogni chiave ci possono essere più valori.