Programmazione C++: ancora sui vettori

Oggi si parlerà persino di Facebook, pensa un po’.

Qualche tempo fa (troppo!) avevamo visto i vettori della libreria standard del C++, e di come assomigliassero agli array del C, e di come fossero in fondo semplici da utilizzare. Abbiamo appena scalfito un granellino della libreria standard, oggi ne scalfiamo un altro.

Memorizzare gli elementi dentro un vettore

Il vettore del C++ è bello, ma non è detto che sia sempre la maniera ottimale di gestire un insieme di elementi, per cui la libreria standard mette a disposizione molti altri contenitori, tra cui le liste. Che differenza c’è tra i vari contenitori?

Il vettore ha un requisito fondamentale: deve essere quanto più possibile simile all’array del C. Nell’array, gli elementi sono memorizzati in maniera consecutiva in memoria, in maniera da poter accedere velocemente a un qualsiasi elemento. Ad esempio, supponiamo di avere un array di 10 interi: un intero sono 4 byte, quindi in memoria l’array richiede 40 byte. Questo blocco di 40 byte viene conservato in memoria in un unico blocco consecutivo di indirizzi lungo 40 bytes. Se il primo elemento sta all’indirizzo X, il secondo starà all’indirizzo X+4, il terzo all’indirizzo X+8, l’i-esimo all’indirizzo X+4*(i-1). Se non ci credete, ecco un programmino che ve lo dimostra:

#include <stdio.h>

int main()
{
    int array[10];

    printf("%p\n", &array[0]);
    printf("%p\n", &array[1]);
    printf("%p\n", &array[2]);
    long x = (long) &array[1];
    long y = (long) &array[0];

    printf("Difference: &array[1] - &array[0] = %ld\n", x-y);
}

L’output sarà qualcosa del tipo:

0x7fff2b98a1a0
0x7fff2b98a1a4
0x7fff2b98a1a8
Difference: &array[1] - &array[0] = 4

Ok, adesso credo che sarà facile capire come il C/C++ traduce l’espressione array[i]; prende l’indirizzo base di array, e ci aggiunge (i-1) moltiplicato per la dimensione del tipo di dati.
Questo tipo di accesso si chiama accesso random perché con una somma e una moltiplicazione arriviamo all’elemento voluto.

Stessa cosa avviene per il vettore, e invito voi stessi a fare la prova modificando opportunamente il programma precedente per usare un vector invece dell’array.

C’è un però: il vettore, al contrario dell’array, ha dimensione dinamica, si può allargare e stringere a volontà, aggiungendo e togliendo elementi. Per esempio, possiamo continuare ad aggiungere elementi in fondo al vettore con la funzione push_back(). Ci sono però due problemi: 1) non sappiamo a priori quanto spazio allocare a un vettore; 2) nel caso in cui lo spazio allocato non basti, bisogna spostare il vettore in uno blocco di memoria più grande. Vediamolo con un esempio:

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> v1(16); // alloca inizialmente spazio per 16 elementi
    vector<int> v2;     // alloca lo spazio di default

    cout << "numero elementi nel vettore v1: " << v1.size() << endl;
    cout << "spazio nel vettore v1: " << v1.capacity() << endl;
    cout << "numero elementi nel vettore v2: " << v2.size() << endl;
    cout << "spazio nel vettore v2: " << v2.capacity() << endl;
    cout << endl;

    v2.push_back(13);
    cout << "numero elementi nel vettore v2: " << v2.size() << endl;
    cout << "spazio nel vettore v2: " << v2.capacity() << endl;
    cout << "Indirizzo primo elemento: " << &v2[0] << endl;
    cout << endl;

    v2.push_back(17);
    cout << "numero elementi nel vettore v2: " << v2.size() << endl;
    cout << "spazio nel vettore v2: " << v2.capacity() << endl;
    cout << "Indirizzo primo elemento: " << &v2[0] << endl;
    cout << endl;

    v2.push_back(19);
    cout << "numero elementi nel vettore v2: " << v2.size() << endl;
    cout << "spazio nel vettore v2: " << v2.capacity() << endl;
    cout << "Indirizzo primo elemento: " << &v2[0] << endl;
    cout << endl;

    v2.push_back(23);
    cout << "numero elementi nel vettore v2: " << v2.size() << endl;
    cout << "spazio nel vettore v2: " << v2.capacity() << endl;
    cout << "Indirizzo primo elemento: " << &v2[0] << endl;
    cout << endl;
}

L’output è questo (a meno dei valori degli indirizzi, naturalmente!):

numero elementi nel vettore v1: 16
spazio nel vettore v1: 16
numero elementi nel vettore v2: 0
spazio nel vettore v2: 0

numero elementi nel vettore v2: 1
spazio nel vettore v2: 1
Indirizzo primo elemento: 0xf20060

numero elementi nel vettore v2: 2
spazio nel vettore v2: 2
Indirizzo primo elemento: 0xf20080

numero elementi nel vettore v2: 3
spazio nel vettore v2: 4
Indirizzo primo elemento: 0xf20060

numero elementi nel vettore v2: 4
spazio nel vettore v2: 4
Indirizzo primo elemento: 0xf20060

Avete capito come funziona? Innanzitutto, è possibile specificare una capacità iniziale che per il vettore v1 abbiamo stabilito essere pari a 16 elementi. Invece, per il vettore v2 non abbiamo specificato niente, quindi la capacità iniziale è pari a 0. Quando iniziamo a inserire elementi in v2, utilizzando la funzione push_back(), a poco a poco la capacità cresce. Inizialmente segue il numero di elementi: prima 1 elemento, e 1 di capacità; poi, con due elementi abbiamo 2 di capacità; con 3 elementi, invece, il vettore si allarga un po’ di più, e arriva a 4; a quel punto, quando inseriamo il quarto elemento non c’è bisogno di allargare ancora. Cosa succederebbe se inserissimo un quinto elemento? a quanto viene portata la capacità?(soluzione in fondo al post).

Guardiamo anche l’indirizzo del primo elemento: come vedete, cambia quando passiamo da 1 a 2; questo perché potrebbe non esserci spazio libero dopo il primo elemento per metterci il secondo; può darsi che quello spazio sia già utilizzato da qualche altra cosa. Quindi, il vettore fa così:

• Alloca un nuovo spazio di memoria in modo da poter contenere anche il nuovo elemento (e magari un po’ di più);
• Copia tutti gli elementi dal precedente blocco di memoria in quello nuovo;
• Dealloca il vecchio blocco, che ormai non serve più;
• Infine, inserisce il nuovo elemento

Come vedete è un’operazione piuttosto pesante, specialmente se il vettore è grande. Immaginate poi cosa vuol dire inserire un elemento nel mezzo, per esempio alla posizione i-esima:

• Spostare tutti gli elementi dall’i-esimo in poi di un posto in avanti
• inserire il nuovo elemento al posto i-esimo

Anche cancellare un elemento nel mezzo comporta analogamente delle copie.

Per cui, se dovete fare un sacco di inserimenti e/o estrazioni dal mezzo, non è che il vettore sia un contenitore molto efficiente. Ne esistono altri come la lista e la map che vedremo le prossime puntate.

Per ora ritorniamo alla mia domandina di prima: di quanto si allarga la capacità del vettore v2 quando inseriamo un quinto elemento? Inserite il seguente codice alla fine della funzione main, e provate a vedere che stampa:

    v2.push_back(29);
    cout << "numero elementi nel vettore v2: " << v2.size() << endl;
    cout << "spazio nel vettore v2: " << v2.capacity() << endl;
    cout << "Indirizzo primo elemento: " << &v2[0] << endl;
    cout << endl;

Ed ecco le ultime 3 righe stampate su schermo:

numero elementi nel vettore v2: 5
spazio nel vettore v2: 8
Indirizzo primo elemento: 0x174f0a0

Avete capito la regola? La capacità del vettore ogni volta raddoppia! Se continuate a inserire elementi, al nono elemento inserito la capacità diventerà 16, e così via.
Questa regola serve a ridurre il numero di operazioni di allocazione/copia/deallocazione in cambio di un po’ di spazio sprecato (fino al doppio nel caso peggiore). Il numero di operazioni di allocazione/copia/deallocazione è infatti proporzionale al logaritmo in base 2 del numero di inserimenti.

Il raddoppio però non è necessariamente una regola ottimale. Per esempio, i programmatori di folly (la libreria C++ di Facebook, recentemente rilasciata open source) utilizza una regola diversa. Qui trovate la descrizione della loro regola, e la spiegazione del perché hanno fatto così.

Alla prossima!