Elementi di
programmazione
ad oggetti
a. a. 2009/2010
Corso di Laurea Magistrale in Ingegneria Elettronica
Docente: Mauro Mazzieri, Dipartimento di Ingegneria Informatica,
Gestionale e dell’Automazione
Lezione 10.1
La libreria standard: i contenitori.
Contenitori

Un contenitore è un oggetto che
serve a contenere altri oggetti

Nei contenitori sequenziali ogni elemento
ha un indice numerico e si può accedere
ad un elemento tramite la sua posizione
 L’ordine
valore


degli elementi non dipende dal loro
Nei contenitori associativi l’ordine degli
elementi dipende dal valore di una
chiave
Gli oggetti contenuti sono tutti dello
stesso tipo
Contenitori della libreria
standard
I contenitori sono definite come
template di classe
 Per usare un contenitore bisogna
includere il suo header, es.
#include <vector>
#include <list>

Contenitori sequenziali

vector



list


Vettore con dimensione variabile
Ottimizzato rispetto all’accesso indicizzato agli elementi
Lista con collegamenti bidirezionali
Ottimizzata rispetto all’inserimento e cancellazione di elementi


deque


Non consente di accedere ad un elemento tramite un indice,
sarebbe troppo lento
Coda bidirezionale (double-ended queue)
Adattatori:

stack


queue


Pila (LIFO)
Coda (FIFO)
priority_queue

Coda con gestione della priorità
Contenitori sequenziali

Vector
size
begin

list
end
begin
Vector
Il vector è il più semplice contenitore
sequenziale
 Definito nell’header vector
#include <vector>


Un vector è definito come template di
classe, pertanto va istanziato con un
tipo:
vector<int> ivec;
 vector<string> svec;
 vector<Impiegato> impiegati;

Vector: costruttori

vector<T> v1;



vector<T> v2(v1);


Vuoto
È il costruttore più usato
Costruttore per copia
vector<T> v3(5);


Contiene 5 elementi di tipo T
Gli elementi sono inizializzati al loro valore standard (es.
0 per gli interi) o tramite il loro costruttore di default


vector<T> v4(7, i);

Contiene 7 elementi di tipo T inizializzati a i


Se non c’è un costruttore di default per T, non si può usare
questo costruttore per vector<T>
i deve essere di tipo T
vector<T> v5(i1, i2);

Inizializza il vettore con una copia degli elementi
compresi tra l’iteratore i1 e l’iteratore i2
Dimensione di vector



I vector sono concepiti per avere una
dimensione che cresce dinamicamente,
man mano che si aggiungono oggetti
Sono l’equivalente dinamico degli array
monodimensionali
È possibile avere un vettore di vettori, es.
vector< vector<int> > v;

È indispensabile lo spazio attorno al parametro
di tipo
vector<vector<int>> v;
causerebbe un errore di compilazione,
>> è un operatore!
Operazioni sui vettori


v.empty( )
v.size( )



v.push_back(t)


Numero di elementi
Il suo tipò è vector<T>::size_tipe
Aggiunge t in coda
v[n]



Restituisce l’elemento in posizione n
È un Lvalue
Non avviene nessun controllo sull’indice!!


v1 = v2


La funzione membro at() invece solleva un’eccezione di tipo
out_of_range se il parametro supera la dimensione del vector
Operatore di assegnamento
v1 == v2 (! =, < , <=, >, >=)


Operatori di confronto
Si può usare un operatore relazionale solo se lo stesso
operatore è definito anche per il tipo dell’elemento
Iteratori


Un iteratore definisce un metodo generale
per accedere in successione a ciascun
elemento di un contenitore
Gli iteratori ridefiniscono l’operatore di
deferenziazione *, il che consente di usarli
come fossero puntatori



*i è un Lvalue (es. *i = t; è valido) e serve ad
accedere all’elemento
i++ è l’iteratore si riferisce all’elemento
successivo
i==j è vero se i e j si riferiscono allo stesso
oggetto
Iteratore

Tutti i contenitori della libreria standard
definiscono un iteratore


Gli iteratori ridefiniscono gli operatori





deferenziazione *, consente l’uso come un puntatore
Incremento ++
Uguaglianza ==, diuguaglianza !=
Operatore freccia, es. i->m dereferenzia i e restituisce il
membro m
v.begin()


vector<T>::iterator i;
Restituisce un iteratore che si riferisce al primo elemento
v.end()



Restituisce un iteratore che si riferisce ad una posizione
dopo l’ultimo elemento
Non è un elemento valido, ma solo un valore sentinella
Se il vector è vuoto, v.begin() e v.end() coincidono
Com’è fatto un iteratore?

Un modo ragionevole di rappresentare un iteratore
per un vettore è usare un puntatore


ma potrebbe essere anche definito come una coppia
(puntatore, offset), che consentirebbe di controllare
per una lista potrebbe essere un puntatore ad un
collegamento
Al di là della loro effettiva definizione, ciò che
conta è che gli iteratori hanno degli operatori con
una semantica comune
N.B. I puntatori sono utilizzabili iteratori su vettori!
Es.
int numbers[] = { 1, 3, 5, 7, 11 };
size_t nnumbers = sizeof(numbers) / sizeof(int);
vector<int> number_vector(numbers, numbers +
nnumbers);

Aritmetica degli iteratori

Per gli iteratori è definita un’aritmetica,
come per i puntatori

i++, i-


i + 5, i -3, i += 7, i -= 9



Si riferisce all’elemento successivo o precedente
Sono definiti per gli iteratori bidirezionali
Un certo numero di elementi più avanti o più indietro
Sono definiti per gli iteratori ad accesso casuale
i–j
È di tipo vector<T>::difference_type
 A differenza di vector<T>::size_type, è un valore con
segno
 È definita solo per gli iteratori ad accesso casuale
Tramite l’aritmetica degli iteratori è possibile inizializzare un
iteratore direttamente in una posizione desiderata
vector<T>::iterator i = v.begin() + v.size() / 2;

Intervallo di iteratori

Un intervallo è definito tramite due iteratori


Il primo si riferisce al primo elemento
dell’intervallo
Il secondo si riferisce ad un elemento dopo
l’ultimo




Intervalli inclusivi a sinistra, in matematica li
indicheremmo come [inizio, fine)
Deve essere possibile raggiungere la fine
dell’intervallo incrementando successivamente il
riferimento alla’inizio dell’intervallo
Se l’inizio e la fine dell’intervallo coincidono,
l’intervallo è vuoto
Per iterare sull’intervallo compreso tra first e last, è
lecito un ciclo del tipo
while (first != last) {
// fai qualcosa con *first
first++;
}
Iterare sugli elementi di un
vettore

Usando gli indici


for (vector<T>::size_type i = 0; i <
v.size(); i++)
// fai qualcosa con v[i]
Usando un iteratore

for (vector<T>::iterator i = v.begin(); i
!= v.end(); i++)
// fai qualcosa con *i
Quando si modifica la dimensione di un vettore (es.
con push_back), gli iteratori esistenti non sono più
validi.
Iteratore costante

Tutti i contenitori della libreria standard definiscono un
iteratore costante


vector<T>::const_iterator i;
L’iteratore costante va usato quando si usano, ma non si
modificano, gli elementi del vettore



for (vector<T>::const_iterator i = v.begin(); i != v.end(); i++)
cout << *i;
Usare *i come se fosse un Lvalue causa un errore di
compilazione
Il valore dell’iteratore può essere cambiato, ma non può essere
usato l’iteratore per cambiare il valore riferito

const vector<T>::iterator i = v.begin();



L’iteratore non può essere cambiato, ma l’elemento riferito sì!
… è decisamente inutile
Un vector costante può avere solo iteratori costanti

const vector<T> v;
conts vector<T>::iterator i = v.begin(); // errore!!!
vector<T>::const_iterator j = v.end(); // Ok
typedef in vector

size_type




iterator
const_iterator

reverse_iterator


const_reverse_iterator


difference_type


value_type
reference
const_reference






tipo numerico senza segno in
grado di contenere la dimensione
del più grande contenitore
possibile
iteratore
iteratore che non consente di
modificare gli elementi
iteratore che scorre gli elementi
in ordine inverso
iteratore che scorre gli elementi
in ordine inverso e non consente
di modificare gli elementi
tipo numerico con segno in
grado di contenere la differenza
tra due iteratori
il tipo dell’elemento
value_type&
const value_type&
iteratori in vector

v.begin()


v.end()



v.rbegin()
r.rend()


iteratore riferito al
primo elemento
iteratore riferito ad un
elemento dopo l’ultimo
iteratore al rovescio
riferito all’ultimo
elemento
iteratore al rovescio
riferito ad un elemento
prima del primo
di ognuno c’è la versione const
e la versione non const
Altri contenitori sequenziali

Deque

Coda bidirezionale: permette l’inserimento di
elementi in testa o in coda in tempo costante



Inserire o rimuovere elementi nel mezzo comporta
spostare elementi a destra o a sinistra
Permetto l’accesso indicizzato agli elementi
List

Lista bidirezionale: ogni elemento conosce il
precedente ed il successivo


Per accedere ad un elemento occorre attraversare
tutti gli elementi precedenti
L’inserimento o la rimozione di un elemento in un
punto qualsiasi richiede un tempo costante
Aggiungere elementi ad un
contenitore sequenziale

c.push_back(t)


c.push_front(t)



inserimento prima dell’iteratore i
c.insert(i, n, t)


inserimento in testa (solo list e deque)
per i vector si può usare
v.insert(v.begin(), t)
ma si tratta di un’operazione dispendiosa
c.insert(i, t)


inserimento in coda
inserisce n elementi prima dell’iteratore i
c.insert(i, b, e)

inseresce prima dell’iteratore i gli elementi
della sequenza compresa tra b ed e
Aggiungere elementi ad un
contenitore sequenziale

Aggiungere un elemento ad un
contenitore significa copiarlo


Non c’è nessuna relazione tra t e
l’elemento nel contenitore dopo che è
stato inserito
Gli inserimenti in un vector o deque
invalidano gli iteratori

Sicuramente quelli che si riferiscono ad
elementi dopo quello inserito
 end()
è sempre invalidato
Dimensione di un contenitore

c.size()


c.max_size()


restituisce un bool che indica se c.size() è 0 o no
c.resize(n)





restituisce un valore di tipo c::size_type che rappresenta il
numero massimo di elementi che il contenitore può contenere
c.empty()


restituisce il numero di elementi
imposta la dimensione del contenitore a n elementi
se n < c.size() gli elementi in eccesso vengono scartati
se si devono aggiungere nuovi elementi, prendono il valore di
default
invalida gli iteratori
c.resize(n, t)


imposta la dimensione del contenitore ad n elementi
se si devono aggiungere nuovi elementi, assumono valore t
Capienza di un contenitore

Un vettore cresce dinamicamente per far
spazio ai nuovi elementi inseriti


Viene allocato più spazio di quello utilizzato
dagli elementi attuali, per
v.capacity()


restituisce il numero di elementi che possono essere
inseriti senza dover allocare della memoria
v.reserve(n)


impone che la capacità sia almeno pari ad n
può esseere utile ad es. v.reserve(50) prima di fare
un ciclo che chiama 50 volte push_back()
Accesso agli elementi

c.front()

se c non è vuoto, è il primo elemento


c.back()

se c non è vuoto, è l’ultimo elemento


c[n]



corrisponde a *c.end()
corrisponde a *--c.end()
l’elemento di indice n
solo per vector e deque
c.at(n)



l’elemento di indice n
solleva l’eccezione out_of_range se l’indice non
è valido
solo per vector e deque
Rimozione di elementi

c.erase(i)


c.erase(b, e)


rimuove tutti gli elementi
pop_back


rimuove la sequenza di elementi compresa tra
gli iteratori b ed e
c.clear()


rimuove l’elemento a cui fa riferimento
l’iteratore i
Rimuove l’ultimo elemento
pop_front


Rimuove il primo elemento
Solo per list e deque (non per vector)
Operazioni su list

l1.sort()


l1.splice(i, l2)


rimuove gli elementi duplicati
l1.remove(v)


fusione di liste ordinate
l1.unique()


muove l’elemento *e dalla lista l2 prima di i in questa lis
(senza copiarlo)
l1.merge(l2)


sposta i valori della list l2 a partire dall’iteratore i di
questa list (senza copiarli)
l1.splice(i, l2, e)


ordinamento crescente
rimuove tutte le istanze di v
l1.reverse()

inverte l’ordine della list
deque
tipi e operatori di vector…
 … più operazioni su testa

front()
 push_front()
 pop_front()

una coda a due capi, ottimizzata per
operazioni che si svolgono alle
estremità
Adattatori per sequenze : stack
template< typename T, typename C = deque<T> >
class stack {
protected:
C c;
public:
typedef typename C::value_type value_type;
typedef typename C::reference reference;
typedef typename C::const_reference const_reference;
typedef typename C::size_type size_type;
typedef C container_type;
explicit stack(const C& __c = C()) : c(__c) {}
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
void push(const value_type& __x) { c.push_back(__x); }
void pop() { c.pop_back(); }
};
Adattatori per sequenze: queue
template<typename T, typename C = deque<T> >
class queue {
protected:
C c;
public:
typedef typename C::value_type value_type;
typedef typename C::reference reference;
typedef typename C::const_reference const_reference;
typedef typename C::size_type size_type;
typedef C container_type;
explicit queue(const C& __c = C()) : c(__c) {}
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() { return c.front(); }
const_reference front() const { return c.front(); }
reference back() { return c.back(); }
const_reference back() const { return c.back(); }
void push(const value_type& __x) { c.push_back(__x); }
void pop() { c.pop_front(); }
};
Adattatori per sequenze:
priority_queue
template<typename T, typename C = vector<T>,
typename Cmp = less<typename C::value_type> >
class priority_queue {
protected:
C c;
Cmp comp;
public:
typedef typename C::value_type value_type;
typedef typename C::reference reference;
typedef typename C::const_reference const_reference;
typedef typename C::size_type size_type;
typedef C container_type;
explicit priority_queue(const Cmp& __x = Cmp(), const C& __s = C()) : c(__s),
comp(__x) { std::make_heap(c.begin(), c.end(), comp); }
template<typename In> priority_queue(In __first, In __last, const Cmp& __x = Cmp(),
const C& __s = C()) : c(__s), comp(__x) {
c.insert(c.end(), __first, __last);
std::make_heap(c.begin(), c.end(), comp); }
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const_reference top() const { return c.front(); }
void push(const value_type& __x);
void pop();
};
Contenitori associativi

set<T>


multiset<T>


insieme
insieme con possibilità di valori ripetuti
map<K, T>

mappa associativa



Ad un oggetto di tipo T è associata una chiave di tipo
K
Data la chiave è possibile accedere direttamente
all’elemento
multimap<K, T>

mappa associativa con possibilità di chiavi
ripetute
map
map
pair

tipo generico che identifica una coppia

definito come template<class First, class
Second> class pair { //… }






es. pair<string, int> voce(“Mauro”, 12);
make_pair(f, s) restituisce un pair, inferendo i
parametri di tipo dai tipo di f e s
p1.first è il membro pubblico corrispondente al
primo elemento
p1.second è il membro pubblico corrispondente
al secondo elemento
p1 < p2 restituisce (p1.first < p2.first) ||
(!(p2.first < p1.first) && p1.second <
p2.second)
p1==p2 resituisce (p1.first == p2.first) &&
(p1.first == p2.first)
Contenitori associativi: tipi
membro

Oltre ai tipi definiti anche dai contenitori
vettoriali, i contenitori associativi
definiscono

key_type


mapped_type


Il tipo del valore contenuto
value_type


Il tipo della chiave
presente anche per i contenitori sequenziali, nei
contenitori associativi corrisponde a pair<const
key_type, mapped_type>
key_compare

Il tipo del criterio di confronto
Contenitori associativi:
operazioni

m[k]



m.find(k)


cerca il primo elemento con chiave k
m.upper_bound(k)


Cerca l’elemento con chiave k
m.lower_bound(k)


Restituisce l’elemento il cui valore della chiave è k
Solo per contenitori con chiave unica
cerca il primo elemento con chiave maggiore di k
m.equal_range(k)

restituisce un pair il cui primo elemento è
m.lower_bound(k) ed il secondo è m.upper_bound(k)
Contenitori associativi: iteratori

Dereferenziando un iteratore di un
contenitore associativo si ottiene un
pair

esempio:
map<string, int> m;
// …
map<string, int>::iterator i = m.begin();
cout << i->first; // stampa la chiave
cout << i->second; // stampa il valore
Aggiungere elementi

Si può usare l’operatore [] per aggiungere
elementi



usare un valore della chiava che non è già presente ha
l’effetto di aggiungere un elemento
esempio
map<string, int> frequenza;
frequenza[“casa”] = 2; // aggiunge un elemento la cui
chiave è “casa” e imposta il valore a 2
in alternativa, si può usare il membro insert(), es.
frequenza.insert(make_pair(“casa”, 2));

non ha effetto se esiste già un elemento la cui chiave è
“casa”
Provare il semplice esercizio: memorizzare e
stampare la frequenza delle parole lette fa un
flusso di input (suggerimento: usare
frequenza[parola]++).
map


Contenitore associativo, permette di recuperare un
elemento sulla base del suo valore
map<K, T>, dove K è il tipo della chiave e T è il
tipo dell’elemento



Es.
map<string, int> rubrica;
string s;
// …
int i = rubrica[s];
Non possono essere presenti due elementi con la
stessa chiave
L’accesso ad un elemento richiede un tempo
logaritmico rispetto alla numerosità degli elementi
multimap

una multimap è una map che può
avere due o più elementi con la
stessa chiave
permette di recuperare tutti gli elementi
con un certo valore della chiave
 accesso in tempo logaritmico

set
insieme ordinato di elementi
 tutti gli elementi debbono essere
diversi tra loro
 accesso in tempo logaritmico ad un
qualsiasi elemento dell’insieme

multiset
set che consentono la presenza di più
elementi uguali
 accesso in tempo logaritmico a
qualsiasi elemento
