Templates e STL
Michelangelo Diligenti Ingegneria Informatica e
dell'Informazione
diligmic@dii.unisi.it
Argomenti
●
Templates in C++
●
C++ standard template library (STL)
Problema con i linguaggi tipati
●
Funzione per scambiare due variabili int
void Swap(int& first, int& second) { int temp = first;
first = second;
second = temp;
}
●
Funzione per scambiare due variabili float
void Swap(float& first, float& second) { float temp = first;
first = second;
second = temp;
}
Problema con i linguaggi tipati
●
Se poi ho string? E poi due double? ecc.
●
Serve fare una libreria di funzioni per ogni funzione?
●
Notate che la logica rimane la stessa
Solo il tipo cambia
●
Soluzione: fare si che i tipi siano anch'essi parametri
Si definisce una sola funzione
Il tipo diventa un parametro
=> templates
I templates: vantaggi
●
Soluzione: fare si che i tipi siano anch'essi parametri => templates
Le funzioni forniscono un template i cui tipi sono specificati di volta in volta
Serve sintassi adeguata per specificare una classe di argomenti diversa
●
Meccanismo fondamentale per realizzare il code reuse
Tutte le librerie standard del C++ sono realizzate con
questo meccanismo
Templates in C++: sintassi
●
Esempio
template <typename Type>
void Swap(Type& first, Type& second) { Type temp = first;
first = second;
second = temp;
}
lista di tipi
funzione che usa
anche i tipi definiti
nel template
Templates in C++: sintassi
●
Sintassi:
template<typename Tipo1, …, typename TipoN>
tipo_ritornato funzione(args) { … }
●
typename indica al compilatore che cosa segue è un tipo anche se per ora sconosciuto
Tipo1, …, TipoN possono essere usati nella
definizione
Templates in C++: sintassi
●
Esempio:
#include "date.h"
template <typename Type>
void Swap(Type& first, Type& second) {
const Type tmp = first; first = second; second = tmp; } int main() {
int i1 = 3, i2 = 4;
string s1 = “a”, s2 = “b”;
Date t1, t2;
Swap<int>(i1, i2);
Swap<string>(s1, s2);
Swap<Date>(t1, t2);
}
Lista tipi passata prima di
lista degli argomenti
Templates in C++: sintassi
●
Possibile anche omettere la dichiarazione dei tipi desiderati quando si chiama la funzione
compilatore crea la funzione in base ai tipi passati
template <typename Type>
void Swap(Type& first, Type& second) { Type tmp = first;
first = second;
second = tmp;
}
int main() {
int i1 = 3, i2 = 4;
string s1 = “a”, s2 = “b”;
Swap(i1, i2);
Swap(s1, s2);
Swap(i1, s1); // No errore in compilazione!!! Non posso instanziare Type univoco
}
Templates e compilatore
●
Templates sono istanziati nel momento in cui il compilatore trova un loro utilizzo
Quando il compilatore trova la definizione non fa nulla tranne qualche controllo di sintassi
Istanziazione nel momento in cui viene chiamata la funzione per tipo
Si costruisce il codice sorgente al volo
Templates e compilatore
●
Esempio
template <typename Type>
void Swap(Type& first, Type& second) { Type tmp = first;
first = second;
second = tmp;
}
int main() {
int i1 = 3, i2 = 4;
Swap(i1, i2);
}
Istanzio il template con degli int
Type->int nella funzione
void Swap(int& first, int& second) { int tmp = first;
first = second;
second = tmp;
}
compilatore
genera la funzione e la compila
Templates e compilatore
●
L'implementazione deve essere visibile in compilazione e non in linking come di solito
Non basta aver visibile la definizione, compilatore genera il codice al volo con l'implementazione
Il codice generato sostituisce i tipi passati come argomenti nel codice della definizione
Non c'è alcuna penalità in termini di prestazioni
Possibile anche mantenere inlining. Esempio:
template <typename Type>
inline void Swap(Type& first, Type& second) { ...}
Templates: svantaggi
●
Svantaggi
Compilazione lenta
Errori del compilatore sono difficilmente comprensibili
File .h (header) più complessi e meno leggibili
Templates e classi
●
Template sono un meccanismo ancora più potente
Possibile creare classi che sono templates
Sintassi
template<typename Type1, …, typename TypeN>
class NomeClasse {
// definizione classe come al solito
// i tipi Type1,...,TypeN possono essere riferiti
};
Templates e classi
●
Esempio:
template<typename T>
class Vector { public:
Vector(int size) : vec(NULL) { if (size > 0) vec = new T[size]; } inline const T& Get(int i) { return vec[i]; }
inline void Set(int i, const T& el) { vec[i] = el; } ~Vector() { if(vec != NULL) delete[] vec; }
private:
T* vec;
};
metodi inline
Templates e classi
●
Se metodi sono complessi meglio non metterli inline
template<typename T>
class Vector { public:
Vector(int size);
inline const T& Get(int i) const { return vec[i]; } inline void Set(int i, const T& el) { vec[i] = el; } ~Vector() { if (vec != NULL) delete[] vec; } private:
T* vec;
};
template<typename T>
Vector<T>::Vector(int size) { if (size <= 0) {
std::cerr << “Wrong parameter”; exit(0);
}
vec = new T[size];
};
metodo non inline
ma sempre insieme
alla definizione nel .h
Deve essere visibile
al compilatore.
Templates e classi: esempio
● Classe che realizza una lista di oggetti template <typename T>
class Stack { private:
class Elem { public:
Elem() { el = NULL; prec = NULL; succ =NULL; } T* el;
Elem* prec;
Elem* succ;
};
Elem* testa;
public:
Stack();
void Push(T* el); // aggiunge elemento
T* Pop(); // ritorna NULL se la lista è vuota ~Stack();
};
classe dentro la classe
Utility class usata solo
nel contesto della classe
esterna
Templates e classi: esempio
●
Esercizio:
Implementare la classe pila (Stack) per generici oggetti con tutti i suoi metodi
Implementare un main che chiama la classe, la riempie con 10 oggetti e poi li svuota
ATTENZIONE alla gestione della memoria!
Templates e classi: esempio
●
Definizione della classe
template <typename T>
class Stack { private:
class Elem { public:
Elem() { el = NULL; prec = NULL; succ =NULL; } T* el;
Elem* prec;
Elem* succ;
};
Elem* testa;
public:
Stack();
void Push(T* el); // aggiunge elemento T* Pop(); // ritorna NULL se stack vuoto ~Stack();
};
Templates e classi: esempio
●
Metodo Push (in .h)
template <typename T>
void Stack<T>::Push(T* el) { Elem* elem = new Elem;
elem->el = el;
elem->prec = testa;
if (testa != NULL)
testa->succ = elem;
testa = elem;
}
Templates e classi: esempio
●
Metodo Pop e costruttore (in .h)
template <typename T>
T* Stack<T>::Pop() {
if (testa == NULL) return NULL;
T* el = testa->el;
Elem* prec = testa->prec;
delete testa;
testa = prec;
if (testa != NULL) testa->succ = NULL;
return el;
}
template <typename T>
Stack<T>::Stack() { testa = NULL; }
Templates e classi: esempio
●
Distruttore deve essere aggiunto
–
si alloca la memoria dinamicamente
template <typename T>
Stack<T>::~Stack() {
while(Pop() != NULL) {}
}
Templates e classi: esempio
●
Main
#include <iostream>
#include “stack.h”
int main() {
Stack<int> pila;
for (int i = 0; i < 10; ++i) {
std::cout << "Add " << i << std::endl;
pila.Push(new int(i));
}
int* res = NULL;
while ((res = pila.Pop()) != NULL) {
std::cout << "Pop " << *res << std::endl;
delete res;
}
return 0;
}
Instanzio il template T=int
Crea una pila di int ma poteva
essere qualsiasi altro tipo
Ownership dei dati
●
Usare T* in Elem implica che la gestione della memoria dei dati e' esterna alla classe
– Si dice che la classe non ha “ownership” dei dati
●
Vantaggio
– Evita le copie in Push e Pop
– Istanze di T possono anche non essere copiabili
● Se copy constructor o operator= non sono definiti per T il template resta utilizzabile
●
Svantaggio
– Allocazione e deallocazione viene gestita esternamente
● Facile sbagliare per chi usa la classe
Ownership e soluzione 2
●
Soluzione alternativa, dati sono proprieta' (“owned”) dalla classe
template <typename T>
class Stack { private:
class Elem {
T el; // costruttore T() invocato in costruzione // come prima
...
};
…
void Push(const T& el_);
T Pop();
// Ora non posso fare check che el sia NULL inline bool Empty() const { testa != NULL; } ...
};
Ownership e soluzione 2
template <typename T>
void Stack<T>::Push(const T& el) { … /* come prima */
elem->el = el; // invocazione all'operator=
}
template <typename T>
T Stack<T>::Pop() {
const T& el = testa->el;
… /* come prima */
return el; // invocazione al copy constructor }
int main() {
Stack<int> lista;
for (int i = 0; i < 10; ++i) lista.Push(i);
while (!lista.Empty())
std::cout << "Pop " << lista.Pop() << std::endl;
return 0;
}
Classi e Ownership
●
Esempio: classi Vector e Matrix viste in precedenza avevano ownership interna alla classe
●
Attenzione: le librerie standard usano ownership interna
–
Dati sono copiati in inserimento
–
Allocazione e deallocazione viene gestita
direttamente nella classe
Classi e Ownership
●
Templates mi permettono un trucco
●
Avere ownership sia interna che esterna!
template <typename T>
class Stack { private:
class Elem { … }; // come prima
void Push(const T& el_); // per valore T Pop(); // per valore
...
};
Stack<int> s1;
for (int I = 0; I < 10; +I) s1.Push(i);
Stack<int*> s2;
for (int i = 0; i < 10; +i) s2.Push(new int(i));
… // deallocare I dati di s2!
Conviene definire inserimenti e ritorno per valore
Se instanzio il template con il dato ownership dei dati diviene interna
Se instanzio il template con
puntatore: ownership dei puntatori interna ma i dati puntati hanno
ownership esterna
Templates e compilatore
●
Sorgente generato deve essere corretto
Non tutti i tipi sono compatibili con un template
template<typename T>
class Numero { private:
T num;
public:
Numero(const T& n) : num(n) { } void Add(const T& n) {
num = num + n;
} };
// Nel main chiamo Numero<int> num(3);
Istanzio con int.
Codice generato:
class Numero { private:
int num;
public:
Numero(const int& n) : num(n) { } void Add(const int& n) {
num = num + n;
} };
Templates e compilatore
●
Sorgente generato deve essere corretto
Non tutti i tipi sono compatibili con un template
template<typename T>
class Numero { private:
T num;
public:
Numero(const T& n) : num(n) { } void Add(const T& n) {
num = num + n;
} };
// Nel main chiamo
Numero<Date> num(Date(3,3,15));
Istanzio con Date: operator+
deve essere definito tra date) o ERRORE in compilazione:
class Numero { private:
Date num;
public:
Numero(const Date& n) : num(n) { } void Add(const Date& n) {
num = num + n;
} };
Templates e valori di default
●
Possibile specificare un tipo di default per un template
Simile a valori di default per funzioni
Sintassi
template<typename T=TipoDefault> class NomeClasse { … }
Esempio
template <typename T=int> class Vector { … }
Se scrivo =>
Vector vec; // nulla specificato sul tipo, sarà vettore di interi
Templates ed ereditarietà
●
Possibile usare ereditarietà in classi con templates
Templates instanziano codice che può contenere classi che contengono ereditarietà
Usato spesso in librerie standard
●
Esempio realizzare una libreria che crea contenitore pila ed una coda generici (con template)
Entrambe si basano su una lista: creo lista con template
Uso ereditarietà per definire una coda ed una pila
Templates ed ereditarietà
●
Classe lista generica
Costruttore tenuto protected, non deve essere usata se non dalle classi derivate
template<typename T>
class List { private:
class Elem { … Come prima … };
Elem* testa;
Elem* coda;
protected:
List() : testa(NULL), coda(NULL) { } void PushCoda(T* el) { … }
void PushTesta(T* el) { … } T* PopCoda() { … }
T* PopTesta() { ... }
};
Templates ed ereditarietà
template<typename T>
class Stack : public List<T> { public:
Stack() { }
void Push(T* el) {
this->PushTesta(el); } T* Pop() {
return this->PopTesta(); };
};
template<typename T>
class Queue : public List<T> { public:
Queue() { }
void Enqueue(T* el) { this->PushCoda(el); } T* Dequeue() {
return this->PopTesta(); } };
Template con ereditarietà
Si richiama solo i metodi di lista, nessuna
implementazione
aggiuntiva
Templates e composizione
●
Composizione con templates: dati membri possono a loro volta essere istanze di classe templetizzata
●
Esempio realizzare una libreria che crea contenitore pila ed una coda generici (con template)
Entrambe si basano su una lista: creo lista con template
Uso composizione per definire la lista come dato membro in coda e pila
Metodi di classi composte chiamano i metodi di lista
Templates e composizione
template<typename T>
class Stack { private:
List<T> list;
public:
void Push(T* el) { list.PushTesta(el); } T* Pop() {
return list.PopTesta(); };
};template<typename T>
class Queue { private:
List<T> list;
public:
void Enqueue(T* el) { list.PushCoda(el); } T* Dequeue() {
return list.PopTesta(); } };
Template con composizione (migliore scelta in questo Caso) rispetto a ereditarieta' Dato membro ha
instanzazione rispetto a T
Chiamo metodi su dato
membro
Standard Template Library
●
Dal 1994 fa parte dello standard del C++
Collezione di librerie di contenitori come vettori, dizionari, ecc
Permette di scrivere codice in modo veloce, affidabile, compatto ed elegante
Grande generalità
Poiché standard è molto portabile su tutte le piattaforme
Architettura software
a classi
basata su templates per gestire qualsiasi tipo e classe
personalizzabile tramite definendo operatori appropriati
Standard Template Library
●
Contiene la classe string
●
Ed i seguenti contenitori con un insieme di algoritmi associati
Dentro il namespace std (standard)
Sequenziali: deque, list, vector
Associativi: map, multimap, multiset, set Adattatori: priority_queue, queue, stack
●
ATTENZIONE: Fondamentale imparare ad usarla
Vector: dichiarazione
●
Vettore di oggetti
template<typename T> class std::vector {}
●
Per usarlo dichiarare
#include <vector>
●
ed opzionalmente “using namespace std;”
●
Costruttori
vector<T> vec; // costruisce vettore vuoto vector<T> vec(100); // 100 elementi uguali a T() T t; vector<T> vec(100, t); // 100 elementi uguali a t vector<T> vec1(vec); // copy costructor
Vector: metodi
●
Basato su concetto di size e capacity
size è la dimensione del vettore in elementi inseriti
capacity è dimensione della memoria allocata
v.capacity(), v.size() // getters a capacity e size
v.reserve(n) // capacity=n, rialloca la memoria v.push_back(T) // aggiunge un elemento in fondo
// (size++ ed eventualmente rialloca se capacity<size) v.pop_back() // elimina ultimo elemento, size--
v[i] o v.at(i) // ritorna elemento i-esimo
v.begin() // ritorna iteratore (vedremo cosa sia) al primo elemento v.end() // ritorna iteratore subito dopo ultimo elemento
v.front() // ritorna iteratore al primo elmento v.back() // ritorna iteratore all'ultimo elmento v.clear() // svuota il vettore
Vector: esempio
std::vector <int> v;
v.push_back(10);
v.push_back(3);
v.push_back(6);
for (int i = 0; i < v.size(); i++) std::cout << v[i] << std::endl;
●
Se non si deve ottimizzare l'uso del vettore si basa solo su push_back per aggiungere e v[i] per leggere il vettore
●
Allocazione memoria fatta dalla classe in modo
automatico
Vector: esempio
std::vector <int> v;
v.reserve(3);
v.push_back(10);
v.push_back(3);
v.push_back(6);
for (int i = 0; i < v.size(); i++) std::cout << v[i] << std::endl;
●
Potenzialmente più veloce quando il vettore cresce molto. Usabile solo se la dimensione è nota a priori
So che la dimensione sarà 3,
per cui dico subito alla classe di
allocare 3 elementi.
Vector: iteratori
●
Iterare su vettori si fa semplicemente con ciclo for
●
Ma il concetto di iteratore sarà fondamentale per altri contenitori per cui vediamolo da subito
vale per tutti i contenitori stl
delega ad una classe iteratore il compito di scorrere gli elementi
l'iteratore generalizza il concetto di puntatore
ad ogni passo l'iteratore ritorna il puntatore ad un elemento
quando lo si incrementa il puntatore passa
all'elemento successivo
Vector: iteratori
●
Esempio
std::vector<int> v;
v.push_back(1);
v.push_back(2);
std::vector<int>::iterator iter = v.begin();
for (; iter != v.end(); iter++)
std::cout << *iter << std::endl;
iteratore che punta a primo elemento
vai all'elemento successivo
finche' non si punta alla fine
Vector: vantaggi
●
In C
int vec[N]; // dimensione fissa
oppure int* vec = (int*) malloc(N*sizeof(int));
e poi realloc(vec, N1*sizeof(int)); // per riallocare
●
In C++
vector<int> vec(N);
vec.reserve(N1); // per riallocare
●
VANTAGGI
Chiaro come sono inizializzati gli elementi (usando il default costructor)
Gestione della memoria trasparente (allocazione fatta dal costruttore, deallocazione fatta dal distruttore del vettore)
Permette la crescita dinamica, senza dover gestire la memoria
Vector: vantaggi
●
Efficienza pari a quella dei il vettore del C
Accesso ad un elemento O(1)
Riallocazione costo O(n) quando avviene
Si deve riallocare la memoria e ricopiare l'intero vettore nella nuova locazione
ATTENZIONE: in realtà si riesce a fare poche
riallocazioni allocando un blocco di elementi in più e non solo uno alla volta
ci pensa il push_back ad ottimizzare
●
Conclusione: molti vantaggi, nessuna penalita'
Containers e copy constructor
●
Qualsiasi oggetto può essere usato in un container STL?
Per avere un funzionamento corretto, oggetto deve avere un default constructor ed essere copiabile
ATTENZIONE: copy constructor deve funzionare!
Se default non va bene deve essere definito
Quando si inserisce in contenitore, dato è
copiato: byte-copy o chiamata a copy constructor se definito
ATTENZIONE se l'oggetto memorizzato è grande
meglio memorizzare i puntatori
Containers e copy constructor
#include <stdio.h>
#include <sys/time.h>
#include <vector>
#include <iostream>
int main() {
struct timeval starttime; gettimeofday(&starttime, NULL);
std::vector<std::vector<int> > matrix;
for (int i = 0; i < 100; ++i) {
std::vector<int> vec(1000000, 1);
matrix.push_back(vec);
}
struct timeval endtime; gettimeofday(&endtime, NULL);
long msec = 1000000 * (endtime.tv_sec - starttime.tv_sec) + (endtime.tv_usec - starttime.tv_usec);
std::cout << msec << “\n”;
}
push_back copia l'intero vettore
Containers e copy constructor
#include <iostream>
#include <sys/time.h>
#include <vector>
int main() {
struct timeval starttime; gettimeofday(&starttime, NULL);
std::vector<std::vector<int>* > matrix; // vettore di puntatori a vettori for (int i = 0; i < 100; ++i) {
std::vector<int>* vec = new std::vector<int>(1000000, 1);
matrix.push_back(vec);
}
struct timeval endtime; gettimeofday(&endtime, NULL);
long msec = 1000000*(endtime.tv_sec - starttime.tv_sec) + (endtime.tv_usec - starttime.tv_usec);
std::cout << msec << “\n”;
for (int i = 0; i < 100; ++i) delete matrix[i];
}
deallocazione
push_back copia solo il puntatore
Memorizzare puntatori?
●
TUTTI i contenitori STL copiano all'inserimento
●
Come evitare la copia
–
Memorizzando i puntatori agli oggetti
–
std::vector<Date*> invece di std::vector<Date>
●
Quando usare i puntatori come dati da memorizzare
–
Se la copia è inefficiente
–
Se non abbiamo implementato un copy constructor ed il byte copy non funziona correttamente
–
Se gli oggetti da memorizzare sono astratti
–
Se si vuole ritardare l'inizializzazione degli oggetti
●
Se si usano i puntatori ricordarsi di deallocare!
Esercizio
●
Creare una gerarchia di classi per gestire le persone che lavorano o studiano all'università di Siena
Persone sono o studenti o ricercatori o docenti o ammistratori
Tutti hanno nome, luogo di nascita, indirizzo di lavoro
Studenti hanno inoltre una facoltà e corso di laurea che frequentano
Ricercatori hanno degli argomenti di ricerca
Docenti hanno dei corsi che insegnano
Amministrativi hanno un ufficio di appartenenza
●
Deve essere possibile salvare o rileggere ogni persona su/da una stringa che ne codifica le sue caratteristiche
●
Definire una classe che definisce un Dipartimento come un insieme di Persone (usa std::vector)
Deve essere possibile stampare su file la stringa
descrittiva di tutte le persone del Dipartimento
Deque
●
Simile ad un vettore ma non rialloca mai l'intera memoria quando si aumenta la capacità
Un elemento sta nella stessa cella di memoria per tutta la sua vita nella deque
Non ha equivalenza con nessun costrutto C: anche se è, come qualsiasi cosa, implementabile in C
Chiave allocazione a blocchi
Quando si esaurisce lo spazio si rialloca un nuovo blocco
Implementata in stl da contenitore
template<typename T> class std::deque { }
Utilizzabile mediante #include<deque>
Deque
●
Accesso resta O(1) ma con due dereferenziazioni
Prima si cerca il blocco
e poi dentro il blocco
vector
deque
puntatori ai blocchi
detta array_map
Deque e complessità
●
Accesso deque[i]
Prima si cerca il blocco
num_blocco = i / num_elementi_per_blocco
Trovato il blocco vado nell'array_map[num_blocco e trovo il puntatore al blocco: p_blocco
Poi dentro il blocco accedo all'emento con
p_blocco[i % num_elementi_per_blocco]
Più lento del vettore di una costante ma sempre O(1)
●
Aggiunta di elementi con push_back
Se l'ultimo blocco è esaurito si deve
allocare blocco con costo fisso O(num_elementi_per_blocco)
costo è costante ed è O(1) rispetto alla size della deque
Deque: metodi
●
Molto simile al vettore (sono “quasi” itercambiabili) a parte i metodi relativi alla capacità
d.size() // ritorna size
d.push_back(T) // aggiunge un elemento in fondo (size++) d.pop_back() // elimina ultimo elemento, size--
d[i] o d.at(i) // ritorna elemento i-esimo.
d.begin() // ritorna iteratore al primo elemento
d.end() // ritorna iteratore subito dopo ultimo elemento d.front(), d.back() // ritorna puntatore a primo o ultimo elmento d.clear() // svuota la deque
Deque: esempio
#include<deque>
std::deque <int> d;
d.push_back(1);
d.push_back(2);
for (int i = 0; i < d.size(); i++) std::cout << d[i] << std::endl;
// o con gli iteratori
std::deque<int>::iterator iter = d.begin();
for (; iter != d.end(); iter++)
std::cout << *iter << std::endl;
List
●
Lista ha complessità lineare per le rimozioni od inserimenti in qualsiasi punto
●
Vettori e deque veloci per accessi random o sequenziali
Inserimento e rimozione di elementi non in coda è lento O(size)
Non abbiamo visto come farlo e solo mostrato push_back per aggiungere in coda...
List
●
Implementata in stl da contenitore
template<typename T> class std::list { }
●
Utilizzabile mediante
#include<list>
●
Implementa una lista come la conoscete voi
VANTAGGI
Contenitore generico di tipi grazie ai template
Non dovete nemmeno pensare all'implementazione che usa puntatori ecc.
Sicura e veloce
List: metodi
l.size() // ritorna size
l.push_back(T) // aggiunge un elemento in fondo (size++) l.push_front(T) // aggiunge un elemento in cima (size++) l.pop_back() // elimina ultimo elemento, size-- l.pop_front() // elimina primo elemento, size--
l.begin() // ritorna iteratore al primo elemento
l.end() // ritorna iteratore dopo ultimo elemento
l.front() // ritorna puntatore a primo elemento
l.back() // ritorna puntatore a ultimo elemento
l.clear() // svuota la lista
List: esempio
#include<list>
std::list <int> l;
l.push_back(1);
l.push_front(2);
l.push_back(4);
// non ammette accesso random, si deve usare gli iteratori std::list<int>::iterator iter = l.begin();
for (; iter != l.end(); iter++) std::cout << *iter << std::endl;
Stl e adattatori
●
Partendo dall'implementazione di contenitori base, STL realizza altri contenitori
Sotto si usa una lista o deque o vettore
Ma l'interfaccia è rivista per rendere facilmente accessibili solo alcune funzionalità
Realizzano quello che si chiama un Wrapper
Incapsulano la classe rendendo accessibili
alcune cose e nascondendone altre
Stack
●
Realizza uno stack (code FIFO)
●
Implementata a partire da una deque
●
Definita come
template<typename T> class stack { }
●
Per usarla aggiungere
#include<stack>
●
Metodi
push(el) // aggiunge un elemento (size++)
pop() // rimuove un elemento (size--)
top() // prende l'elemento in testa
size() // dimensione dello stack
empty() // bool che controlla se vuota
Stack: esempio
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<string> allwords; // stack of di parole string word;
while (cin >> word) // legge le parole da stdin allwords.push(word);
while (allwords.size() > 0) {
cout << allwords.top() << endl; // scrive la parola su stdout allwords.pop(); // rimuove la parola
}
return 0;
}
Coda con priorità
●
Realizza una coda con priorità
Elemento massimo (o minimo) sempre in testa alla coda
Inserimento e rimozione O(log(n))
Implementa struttura dati heap
Definita come
template<typename T> class priority_queue { }
Per usarla aggiungere
#include<queue>
Possibile cambiare funzione di ordinamento
Coda con priorità: metodi
●
push(el) // aggiunge un elemento (size++)
●
pop() // rimuove un elemento (size--)
●
top() // prende l'elemento in testa
●
size() // dimensione dello stack
●
empty() // ritorna true se vuota
Coda con priorità: heap
●
Implementazione della coda con priorità
Usa struttura dati detta Heap
Memorizzazione dell'albero attraverso un vettore,
=> le code con priorità sono adattatori nell'stl
●
Heap è un albero binario che ha le seguenti proprietà (heap property)
La radice memorizza il valore minimo tra tutti i nodi dell'albero
Valore memorizzato in un nodo è sempre
superiore al valore memorizzato nel padre
Heap
●
Esempio albero dove la heap property è verificata
Potrei anche usarlo con ordinamento crescente
9 8
6
2
4 7
3
Heap: aggiunta nodi
●
Inserimento elemento
Aggiunta in prima posizione libera
Riaggiorno l'albero, scambiando i nodi finché proprietà heap non è verificata
Complessità O(log n)
9 8
6
2
Albero iniziale 3
Heap: aggiunta nodi
●
Inserimento elemento
Aggiunta in prima posizione libera
Riaggiorno l'albero, scambiando i nodi finché proprietà heap non è verificata
Complessità O(log n)
9 8
6
2
3 Aggiungo elemento
in prima posizione libera Heap property non più verificata
1
Heap: aggiunta nodi
●
Inserimento elemento
Aggiunta in prima posizione libera
Riaggiorno l'albero, scambiando i nodi finché proprietà heap non è verificata
Complessità O(log n)
9 8
6
2
1 Scambio nodi fino a che heap property non è di nuovo verificata
3
Heap: aggiunta nodi
●
Inserimento elemento
Aggiunta in prima posizione libera
Riaggiornamento albero, scambiando i nodi finché proprietà heap non è verificata
Complessità O(log n)
9 8
6
1
2 Scambio nodi fino a che
heap property non è di nuovo
verificata. Max log(n) passi
3
Heap: rimozione nodi
●
Rimozione elemento nella radice
Eliminazione radice, sostituita da ultimo nodo nell'albero
Riaggiornamento l'albero, scambiando i nodi finché proprietà heap non è verificata
Complessità O(log n)
9 8
6
1
2 Eliminazione nodo
3
Heap: rimozione nodi
●
Rimozione elemento nella radice
Eliminazione radice, sostituita da ultimo nodo nell'albero
Riaggiornamento l'albero, scambiando i nodi finché proprietà heap non è verificata
Complessità O(log n)
9 8
6 2 Sostituzione con ultimo
nodo dell'albero
3
Heap: rimozione nodi
●
Rimozione elemento nella radice
Eliminazione radice, sostituita da ultimo nodo nell'albero
RIaggiornamento l'albero, scambiando i nodi finché proprietà heap non è verificata
Complessità O(log n)
9 8
6 2 Sostituzione con ultimo
nodo dell'albero
Heap property non verificata
3
Heap: rimozione nodi
●
Rimozione elemento nella radice
Eliminazione radice, sostituita da ultimo nodo nell'albero
RIaggiornamento l'albero, scambiando i nodi finché proprietà heap non è verificata
Complessità O(log n)
9 8
6 3 Scambio nodi finché
heap property
non viene verificata, in max log(n) passi
2
Coda con priorità: heap
●
Push e pop hanno complessità O(log(n)), n dimensione dei dati
●
Top ha complessità O(1)
–
semplice accesso alla radice
●
Inserire un insieme di dati e rileggerlo elemento ad elemento ordinato complessità O(n log(n))
–
Non deve stupire visto che nlog(n) è ottimo
ottenibile per l'ordinamento di un insieme!
Coda con priorità: esempio
#include <iostream>
#include <queue>
using namespace std;
int main () {
priority_queue<int> mypq;
mypq.push(30);
mypq.push(100);
mypq.push(25);
mypq.push(40);
while (!mypq.empty()) {
cout << mypq.top() << " ";
mypq.pop();
}
cout << endl;
return 0;
}
Code: ordinamento custom
●
La coda con priorità è utilissima ma se mi serve ordinamento speciale?
●
In generale come definisco ordinamento per oggetti generici nell'STL?
–
Quello che vediamo adesso usabile in tutti i
contenitori ordinati dell'STL (priority_queue, map, etc.)
●
Nota:
–
Ordinamento sempre realizzato tramite confronti tra coppie di oggetti
–
Definire odinamento tra coppie definisce
ordinamento totale
Code: ordinamento custom
●
Metodo standard
–
definisco una class/struct che fa da comparatore
● Implementa operator() tra due istanze
–
Esempio per coppie di istanze di date:
struct CompareDate {
bool operator()(const Date& a, const Date& b) const { return a.GetYear() < b.GetYear();
} };
●
Vantaggio:
– Diverse classi comparatore a seconda delle esigenze
– Esempio per fare ordinamento decrescente return b.GetYear() < a.GetYear();
Code: ordinamento custom
●
Classe comparatore:
#include “date.h”
struct CompareDate {
bool operator()(const Date& a, const Date& b) const { return a.GetYear() < b.GetYear();
} };
// Per definire un'istanza
priority_queue<Date, vector<Date>, CompareDate> coda;
Classe che mi determina ordinamento:
terzo parametro del template
Secondo parametro del template è il contenitore usato, in genere non va cambiato il default: vector<...>
Necessario ridefinirlo anche se usate il default perché cambiate il terzo parametro
Dichiarazione di
classe comparatore
tra Date
Code: ordinamento custom
●
Metodo di default:
–
Se non definite il comparatore e scrivete
priority_queue<Date> coda;
– Compilatore utilizza valori di default dei parametri del template priority_queue<Date, vector<Date>, less<Date> > coda;
– less<T> classe templetizzata definita nelle librerie template<typename T>
struct less {
bool operator()(const T& l, const T& r) const { return l < r;
}
};
Less invoca operator<
sulle classi
Comparatore di default
Code: ordinamento custom
●
Ordinamento di default senza comparatore:
priority_queue<Date> coda;
Comparatore di default less<T> confronta due istanze oggetti a,b con il test:
a < b
Viene invocato l'operator< tra coppie di istanze
Attraverso operator overloading di operator<, diviene realizzabile ordinamento custom
Esempio: priority_queue<Date> coda;
OK solo se e' definito operator<(const Date& date1, const Date& date2)
Altrimenti errore in compilazione appena viene istanziato il template
Code: ordinamento custom, esercizio
●
Esercizio: implementare una classe Date, con overloading operator< che confronta due date
●
Realizzare due code una che ordina le date in modo descrescente ed una crescente
●
Scrivere un main che riempie le code (usando le librerie STL) con delle date e poi le svuota
stampando i valori inseriti
Iteratori e contenitori
●
Il mondo degli iteratori STL è variegato
Iteratori standard quelli visti fin qui
Iteratori inversi (reverse iterator) per scandire il contenitore all'indietro
Iteratori const, che non permettono di modificare gli oggetti scanditi
Obbligatori se usati in metodi const o per container dichiarati const
E molti altri... ma con i tre suddetti si coprono le
esigenze al 99.9%
Iteratori e contenitori const
#include<list>
std::list<int> l;
l.push_back(1);
l.push_front(2);
std::list<int>::iterator iter = l.begin();
for (; iter != l.end(); iter++)
(*iter)++; // modifico il contenuto
std::list<int>::const_iterator iter = l.begin();
for (; iter != l.end(); iter++)
std::cout << *iter << “\n”; // OK non modifico il contenuto std::list<int>::const_iterator iter = l.begin();
for (; iter != l.end(); iter++)
(*iter)++; // ERRORE in compilazione modifico il contenuto
Iteratori possono
modificare il contenitore
Iteratori const non possono
modificare il contenuto
Iteratori e contenitori inversi
#include<list>
std::list<int> l;
l.push_back(1);
l.push_front(2);
std::list<int>::reverse_iterator iter = l.rbegin();
for (; iter != l.rend(); iter++) (*iter)++;
std::list<int>::reverse_const_iterator iter = l.rbegin();
for (; iter != l.rend(); iter++)
std::cout << *iter << std::endl;
scandisco all'indietro
e possibilmente modifico i dati
scandisco all'indietro
ma non posso modificare
i dati
Contenitori associativi
●
Permettono di associare oggetti ad oggetti
chiave → valore
●
O di creare insieme di oggetti
●
Vantaggi
Permettono la ricerca efficiente
Tipicamante O(log(n))
Per esempio possibile creare dizionari
parola → numero_occorrenze
Map
●
Implementata in stl da contenitore
●
template<typename T1, typename T2> class std::map { }
●
Utilizzabile mediante
●
#include<map>
●
Implementa un albero binario di ricerca ordinato per chiave
VANTAGGI
Contenitore generico di tipi grazie ai template
Ricerche per chiave hanno complessità O(log(n))
Inserimenti hanno complessità O(log(n))
Map: metodi
m.size() // ritorna dimensione della mappa m.insert(make_pair(T1, T2)) // aggiunge coppia chiave->valore
m[T1] = T2 // operatore equivalente a m.insert(make_pair(T1, T2)) m.begin() // ritorna iteratore a prima coppia (chiave,valore)
m.end() // ritorna iteratore subito dopo ultima coppia m.clear() // svuota la mappa
m.erase(T1) // rimuove un elemento
m.find(T1) // ritorna iteratore a (T1,valore) o m.end() se non trovato Ritorna una coppia chiave → valore
Realizzata tramite la classe pair:
template <typename T1, typename T2> class pair { T1 first;
T2 second;
pair(const T1& f, const T2& s) : first(f), second(s) {}
};
Map: operator[]
●
operator[] ritorna riferimento ad elemento associato
–
Esempi
map<string, int> m;
m[“pippo”] ritorna int per cui possibile m[“pippo”]++; m[“pippo”] = 0;
oppure
map<int, string> m1;
m[4] = “ciao”; m[4].find(“d”);
Map: operator[]
●
operator[] non e' const
–
Se elemento non presente viene inserito
–
Inizializzazione tramite costruttore di default
●
Esempi
–
map<string, int> m; m[“pippo”]++;
m[“pippo”] aggiunge elemento pari a 0 chiama costruttore di default di int: int() poi lo incrementa, valore finale e' 1
–
map<int, string> m1; m[5] = “ciao”;
m[5] crea stringa vuota chiamando string()
poi si assegna a “ciao”
Map: creazione di bag of words
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<string, int> freq; // dizionario parole → frequenza string word;
while (cin >> word) { // leggo parole dall'input
freq[word]++; // oppure freq.insert(make_pair(word, 0))->second++;
}
map<string, int>::const_iterator iter;
for (iter=freq.begin(); iter != freq.end(); ++iter) {
cout << iter->first << "->" << iter->second << endl;
}
iter = freq.find(“pippo”);
if (iter != freq.end())
cout << “Pippo ” << iter->second;
return 0;
}
iteratore ritorna pair:
iter->first chiave
iter->second: valore Ricerche su mappa
tramite find
Map: esercizi con mappe STL
●
1) Leggere un testo in ingresso da file, creare bag of words, stampare le parole
●
2) Un docente deve gestire i voti assegnati ai
suoi studenti. Creare una classe per la gestione:
leggere da file l'insieme di nomi delle persone che frequentano un corso e voto associato,
permettere la ricerca del voto dato il nome di uno studente.
Suggerimento: creare una classe che contenga una mappa nome->voto e costruttore che
prende il nome del file da cui caricare i dati ed
un metodo per la ricerca.
Multimap
●
Map ha un solo elemento data una chiave
●
Multimap ammette più elementi con stessa chiave
typename<K, V> std::multimap<K, V>
●
Stessa interfaccia di std::map ma:
–
senza operator[], necessario usare m.insert()
–
senza metodo find, vedi prossima slide
●
Attenzione: possibile ottenere una cosa simile a multimap con
std::map<K, std::vector<V> >
Multimap
●
Ricerca su multimap
multimap<int, string> m2;
pair<multimap<int, string>::iterator,
multimap<int, string>::iterator> range;
range = m2.equal_range(10);
multimap<int, string>::iterator iter;
for (iter = range.first; iter != range.second; ++iter)
cout << iter->first << ” “ << iter->second << “\n”;
Map: esercizi con multimap
●
1) Un docente deve gestire i voti assegnati ai suoi studenti. Creare una classe per la gestione dei voti. Leggere da file l'insieme di nomi delle persone che frequentano un corso e voto
associato, stampare gli studenti in ordine di voto.
–
Suggerimento: riprendere da esercizio
precedente ed aggiungere un metodo dove: si copia la mappa in una multimap con chiave e
valore invertiti e stampare con un'iterazione sulla
multimap.
Mappe ed ordinamento custom
●
La mappa contiene un terzo elemento nel template
map<T1, T2, Comparator>
Compare è la funzione di ordinamento per confrontare le coppie
Default chiama una funzione di comparazione che chiama operator< per ordinare
Possibile definire un'altra funzione di ordinamento
Mappe ed ordinamento custom
●
Esempio, ordinare in modo descrescente
struct cmp {
bool operator() (const int& a, const int& b) { return b < a;
} };
map<int, string, cmp> mappa;
mappa[3] = “ciao”;
mappa[5] = “ciacai”;
mappa[2] = “ciaociao”;
map<int, string, cmp>::const_iterator iter = mappa.begin();
for (; iter != mappa.end(); ++iter)
std::cout << iter->first << “->” << iter->second << “\n”;
Dichiarazione di classe comparatore
Con b < a, ordino in modo decrescente, a < b, in modo crescente (default)
Set
●
Implementata in stl da contenitore
template<typename T> class std::set { }
●
Utilizzabile mediante
#include<set>
●
Implementa un insieme di oggetti
Organizzati in un albero binario di ricerca ordinato per chiave
VANTAGGI
Contenitore generico di tipi grazie ai template
Ricerche per chiave hanno complessità O(log(n))
Inserimenti hanno complessità O(log(n))
Set: metodi
s.size() // ritorna size
s.insert(T) // aggiunge un elemento
s.begin() // ritorna iteratore al primo elemento
s.end() // ritorna iteratore subito dopo ultimo elemento s.clear() // svuota la mappa
s.erase(T) // rimuove un elemento
s.find(T) // ritorna iteratore a elemento o s.end() se non trovato
Mappe/Set: ordinamento di classi
●
Abbiamo visto map<K, V, Comparator>
–
Comparator di default chiama operator< attraverso l'uso di Comparator=less<K>
Per usare una classe generica come chiave in una mappa è necessario che l'operator< sia definito
Per tipi noti (int, float, ecc) il compilatore sa come confrontarli e non si deve fare nulla
●
Oppure possibile definire una funzione di
comparazione custom come abbiamo visto
Mappe ed ordinamento di classi
●
Esempio, ordinare date senza usare operator<
(fate voi il caso in cui si usa operator<)
struct cmp {
bool operator() (const Date& a, const Date& b) {
if (a.GetYear() != b.GetYear()) return a.GetYear() > b.GetYear();
if (a.GetMonth() != b.GetMonth()) return a.GetMonth() > b.GetMonth();
return a.GetDay() > b.GetDay();
} };
map<Date, int, cmp> mappa;
mappa[Date(1,1,2011)] = 1;
mappa[Date(1,1,2010)] = 3;
mappa[Date(3,3,2012)] = 5;
map<Date, int, cmp>::const_iterator iter = mappa.begin();
for (; iter != mappa.end(); ++iter) {
std::cout << iter->first.GetYear() << iter->first.GetMonth()
<< iter->first.GetDay() << “->” << iter->second << “\n”;
}
Map: esercizi
Esercizio 1
Leggere un testo in ingresso da file
Creare bag of words
Stampare le parole in ordine decrescente di frequenza (consiglio usare multimap e
comparatore)
Map: esercizi
Esercizio 2:
–
una compagnia aerea tiene la lista delle persone che viaggeranno su un singolo volo su un file
–
Creare una classe che permetta di leggere il file, memorizzando i nomi delle persone
–
Permettere alla polizia di cercare se una
persona viaggia su un certo volo, o stampare
tutte le persone viaggianti in ordine alfabetico
Multiset
●
Multiset
–
Set che può avere piu' volte lo stesso elemento inserito
●
Definito come
template<typename T> class std::set { }
●
Utilizzabile mediante
#include<set>
Tabelle hash
●
unsortedmap (compilatori vecchi hash_map)
Interfaccia come map, ma si definisce funzione hash invece che operatore di ordinamento per tipi custom
Accesso ad un elemento ha costo indipendente dalla dimensione della tabella O(1)
recente aggiunta allo standard (c++-11)
●
unsortedset (compilatori vecchi hash_set)
–
Test di presenza nel set O(1)
–
Da standard c++-11
●
Basate su tabelle hash, anche se lo standard non si
lega ad una particolare implementazione
Tabelle hash: implementazione
●
Hash function mappa la chiave su indice numerico
–
Indice numerico accede ad elemento in vettore
–
Vettore memorizza le coppie chiave-valore
Hash Function
Hash
Chiavi Lista coppie chiave-valore Indice 152 ha conflitto. La lista chiavi valore permette di capire, se il match per una chiave e' corretto e prendere il valore corretto tra quelli nella lista
Unsortedmap / Unsortedset
●
Definite come
template<typename Key,typename Value, typename Hash = hash<Key> >
unsortedmap
template<typename Key, typename Hash = hash<Key> > unsortedset
●
Funzioni di Hash sono passate tramite template
–
hash<string>, hash<float>, etc. gia' definite da stl
–
Farle per classi custom non e' semplice, dobbiamo garantire l'uniformita del mapping sull'intervallo
●
Interfaccia di fatto identica a map/set
–
