La Standard Template Library
• La libreria standard STL e’ una libreria di classi di
contenitori, algoritmi ed iteratori.
• STL e’ una libreria generica: tutti i suoi componenti
sono parametrizzati (possono essere applicati a
qualsiasi tipo, anche creato dall’utente)
puntatori intelligenti
vettori, liste, mappe, ….
find, replace, reverse, sort, ….
1
Contenitori
• Un contenitore è un oggetto capace di
immagazzinare altri oggetti e che possiede metodi
per accedere ai suoi elementi.
– Ogni contenitore ha un iteratore associato che permette
di muoversi tra gli elementi contenuti
– Una sequenza è un contenitore di lunghezza variabile i
cui elementi sono organizzati linearmente. E’ possibile
aggiungere e rimuovere elementi
– Un contenitore associativo è una sequenza che
permette un efficiente accesso ai suoi elementi basato
su una chiave.
2
Iteratori (puntatori intelligenti)
• Gli iteratori sono dei puntatori agli elementi di un
contenitore e ci permettono di muoverci all’interno
di esso:
– Iteratori monodirezionali: Permettono di accedere
all’elemento successivo o al precedente
– Iteratori bidirezionali : Permettono di accedere sia
all’elemento successivo che al precedente
– Iteratori ad accesso casuale : Permettono di accedere
ad un qualunque elemento del contenitore
3
Sequenze
• Vector (#include <vector>)
– Tempo costante di inserimento e cancellazione di
elementi all’inizio e alla fine del vettore.
– Tempo lineare con il numero di elementi per
inserimento e cancellazione di elementi all’interno del
vettore
– Iteratore ad accesso casuale
• List (#include <list>)
– Tempo costante di inserimento e cancellazione di
elementi in ogni punto della lista
– Iteratore bidirezionale
4
Vector
begin()
end()
0
1
2
...
9
++ p
p
p
p
p
push_back()
p
• Le locazioni di memoria sono contigue
– Accesso casuale, veloce l’accesso agli elementi, lenti
inserimento ed estrazione
5
Vector (dichiarazioni)
Si dichiara:




vector<int> v; // dichiara un vettore vuoto di interi
vector<Razionale> v; // vettore di razionali
vector<int> v(7); // vettore di 7 interi
vector<int> v(5,3); // vettore di 5 interi tutti uguali a 3
 v.size() // dimensione del vettore
 // si può usare normalmente v[i] per accedere agli elementi
6
Vector (iteratori)
Un iteratore è un puntatore ad un elemento del vector.
Dichiarazione:
 vector<int>::iterator it; // dichiara un iteratore di un vettore di interi
 vector<int>::reverse_iterator it; // dichiara un iteratore inverso
 vector<int>::const_iterator it; // dichiara un iteratore di un vettore costante di
interi
it++ (avanza di un elemento o retrocede nel caso di iteratori inversi)
It-- (retrocede di un elemento o avanza nel caso di iteratori inversi)
v.begin() // restituisce l’iteratore al primo elemento del vettore
v.end() // restituisce l’it. al successivo dell’ultimo del vettore
*it // restituisce l’oggetto puntato da it
it=(it.begin()+it.end())/2; restituisce l’it. all’elemento medio
v.rbegin() v.rend() //restituiscono gli iteratori inversi all’ultimo e
all’elemento precedente il primo
7
Vector (metodi)
Il vector può avere dimensione variabile.
 v.push_back(5); // inserisce 5 alla fine del vettore (la dimensione sarà
// aumentata di uno)
 v.pop_back() // cancella l’ultimo elemento(la dimensione sarà
// diminuita di uno)
 v.insert (it,18); // inserisce 18 nella posizione precedente all’iteratore
 v.erase (it); // cancella l’elemento nella posizione dell’iteratore
// (l’iteratore viene spostato all’elemento successivo)
8
Algoritmi (#include <algorithm>)
• Gli algoritmi sono delle funzioni globali capaci di
agire su contenitori differenti
find
max_element
count
copy
sort
min_element
• Sono incluse operazioni di ordinamento (sort,
merge, min_element, max_element...), di ricerca
(find, count, equal...), di trasformazione
(transform, replace, fill, rotate, shuffle...), e varie
altre operazioni.
9
Algoritmi
Possono essere applicati a tutti i contenitori (o quasi)
 sort (it1, it2);




// ordina un vettore (non vale per le liste)
//dall’iteratore it1 all’iteratore it2
reverse (it1, it2); // inverte un vettore da it1 a it2
it_trov=find (it1,it2,5) // cerca il 5 da it1 a it2. Se lo trova restituisce
// l’iteratore, altrimenti restituisce v.end()
it_max=max_element (it1,it2) // restituisce l’iteratore che punta al
// massimo del vettore
it_min=min_element (it1,it2) // restituisce l’iteratore che punta al
// minimo del vettore
L’elenco completo lo trovate sul Libro di testo in Appendice.
Gli algoritmi funzionano anche sugli array standard (basta passare i
puntatori invece degli iteratori)
10
List
nodo
val
list
next
top
bottom
prev
...
nodo
nodo
val
val
next
next
prev
prev
• Le locazioni di memoria non sono contigue
– Lenta la ricerca, veloci inserimento ed estrazione
11
List
list<int> l;
//dichiarazione
 Agli iteratori non possono essere applicate operazioni aritmetiche
(es. it=(l.begin()+l.end())/2; )
 l.sort();
// ordina una lista
 l.reverse() // inverte una lista
12
Esempio uso sequenze
#include <vector
list >
#include <algorithm>
#include <iostream>
int main() {
vector
list <int> container;
int val;
for (int i=0; i<10; i++) {
val = (int)((float)rand()/RAND_MAX*10);
container.push_back(val); }
vector
list <int>::iterator it1;
for ( it1=container.begin(); it1!=container.end();
it1++)
cout << "vector : " << *it1 << endl;
return 0;
}
13
Contenitori associativi
• Sono contenitore di coppie ( key, value ) e
possiedono un iteratore bidirezionale
• map
– Viene richiesto l’operatore < per la chiave
– Gli elementi sono ordinati secondo la chiave
14
Esempio uso contenitori associativi
#include <map>
#include <algorithm>
#include <iostream>
#include <string>
int main() {
map<string,int> amap;
amap["Primo”]=1;
amap[“Secondo”]=2;
cout << "Size : " << amap.size() << endl;
amap["Terzo"]=3;
amap["Quarto"]=4;
cout << "Size : " << amap.size() << endl;
map<string,int>::iterator it;
for ( it=amap.begin(); it!=amap.end(); it++)
cout << "map : " << it->first << " " << it->second << endl;
cout << amap.find("Terzo")->second << endl;
return 0;
}
15