Post on 07-Jan-2016
description
1
La Standard Template LibraryLa Standard Template Library
vettori, liste, mappe, ….vettori, liste, mappe, ….
find, replace, reverse, sort, …. find, replace, reverse, sort, ….
puntatori intelligentipuntatori intelligenti
• 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)
2
• 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.
ContenitoriContenitori
3
• 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
Iteratori (puntatori intelligenti)Iteratori (puntatori intelligenti)
4
SequenzeSequenze• 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
5
VectorVector
11 22 ...... 99
begin()begin() end()end()
pppp pp pp pp
00 push_back()push_back()
pp++++
• Le locazioni di memoria sono contigue– Accesso casuale, veloce l’accesso agli elementi, lenti
inserimento ed estrazione
6
Vector (dichiarazioni)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
7
Vector (iteratori)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 vettorev.end() // restituisce l’it. al successivo dell’ultimo del vettore
*it // restituisce l’oggetto puntato da itit=(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
8
Vector (metodi)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)
9
Algoritmi (#include <algorithm>)Algoritmi (#include <algorithm>)
• Gli algoritmi sono delle funzioni globali capaci di agire su contenitori differenti
• 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.
find
count copy
max_element sort
min_element
10
AlgoritmiAlgoritmi
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)
11
val
nodo
next
prev
ListList
• Le locazioni di memoria non sono contigue– Lenta la ricerca, veloci inserimento ed estrazione
......list
top
val
nodo
next
prev
val
nodo
next
prevbottom
12
ListListlist<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
13
#include < >#include <algorithm>#include <iostream>
int main() {
<int> container;int val;for (int i=0; i<10; i++) { val = (int)((float)rand()/RAND_MAX*10); container.push_back(val); } <int>::iterator it1;for ( it1=container.begin(); it1!=container.end(); it1++) cout << "vector : " << *it1 << endl;return 0;}
Esempio uso sequenzeEsempio uso sequenze
vector
vector
vector
list
list
list
14
Contenitori associativiContenitori 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
15
#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; }
#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; }
Esempio uso contenitori associativiEsempio uso contenitori associativi