Newsgroup: it.comp.lang.c++
Titolo: Comportamento di std::vector

Mi chiedevo come si comporta il vector quando si scrive ad esempio:
vector<string> vs;
vs[10000] = "ciao";
..alloca i primi 10000 elementi o e' piu' furbo?
-- 
Saluti,
 Francesco Cipriani

 ..alloca i primi 10000 elementi o e' piu' furbo?
L'uso di un indice al di fuori del semi-intervallo [0, N) nell'operator[]
di uno std::vector V tale che V.size()==N e` un errore, a fronte
del quale una implementazione di std::vector puo` fare cio` che
piu` desidera (puoi aspettarti un crash, ma puo` succedere di
peggio -- sporcamenti arbitrari di memoria, ecc).
Questa e` una scelta *di prestazioni*: l'indiciamento di uno
std::vector non deve avvere NESSUN overhead rispetto a quello
di un array, neppure la singola istruzione-macchina necessaria
per controllare che l'indice sia in range.
Se preferisci che sia fatto il controllo, puoi usare la sintassi:
 
vs.at
(10000) = "ciao";
che solleva una exception out_of_range (che puoi
gestire con try/catch); l'overhead rispetto all'uso di
operator[] e` minimo ma NON nullo (puoi aspettarti
appunto circa 1 istruzione di macchina nel caso che
l'indice sia in-range, parecchie di piu` se e` out of
range perche` il caso in cui una exception si verifica
non e` tipicamente ottimizzato in maniera molto
spinta dal compilatore, dovendosi, per un buon
progetto, trattare appunto di caso "eccezionale").
Mi pare di capire che quello che tu implichi con "piu`
furbo" sia l'uso di un vettore sparso, dove la memoria
e` allocata per tutte e sole le "celle" effettivamente
usate.  std::vector non si comporta cosi`, perche`
cio` comporterebbe overhead elevati per il caso che
std::vector e` ottimizzato per coprire, cioe` la pura
sostituzione degli array.
Puoi ottenere esattamente questo comportamento
con:
std::map<int, string> vvs;
vvs[10000] = "ciao";
naturalmente con diverse caratteristiche di prestazioni.
Una std::map<int,T> non e` (prestazioni a parte)
un ESATTO rimpiazzo per un std::vector<T> perche`
vi sono varie sottili ma cruciali differenze; ad esempio,
template<class container>
double media(const container& c)
{
    double total = 0.0;
    int count = 0;
    container::const_iterator it = c.begin();
    while(it != c.end()) {
        ++count;
        total += *it++;
    }
    return count?(total/count):0.0;
}
media(vs) ti darebbe la media considerando che
"esistano" tutti gli elementi dello std::vector vs (se
vs.size()==10000, 10000 elementi); media(vvs)
considererebbe "esistenti" solo quegli elementi
che sono stati settati esplicitamente appunto con
istruzioni del tipo vvs[23]=45;.
Inoltre (anche se per la media() e` ininfluente)
il loop su std::vector andrebbe in ordine per indici
da 0 in poi, quello sulla std::map andrebbe in un
ordine "arbitrario" ("apparentemente casuale").
Insomma, se quello che desideri e` simulare piu`
o meno strettamente uno std::vector<T> ma con
l'ottimizzazione del caso "vettore sparso" (solo
pochi elementi dell'apparente range veramente
settati) devi realizzare tu stesso la simulazione --
non e` difficile, basta incapsulare std::map e
implementare i vari membri che ti interessano,
o delegando alla std::map che incapsuli oppure
gestendoli tu stesso (ad esempio devi sapere
il valore dell'indice piu` grosso usato in
operator[], per gestire tu size() ed end(); e
anche gli iterator probabilmente dovrai rifarli, se
ti interessa poterli usare ad esempio con gli
algoritmi generici ottenuti con #include <algorithm>).
Il solito Google puo`, in alternativa, aiutarti a trovare
implementazioni gia` fatte di "sparse matrix" viste
come template di tipo piu` o meno "STL-oriented"
(qui il termine STL e` corretto visto che la libreria
standard del C++ c'entra sino a un certo punto:-).
Ma svilupparti tu stesso un template sparse_vector
(tutt'altro che difficile) potrebbe essere un utile ed
istruttivo esercizio.
Alex