La Standard Template Library La Standard Template Library

(1)

La Standard Template Library La Standard Template Library

vettori, liste, mappe, ….

find, replace, reverse, sort, ….

puntatori intelligenti puntatori 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.

Contenitori

(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)

(4)

Sequenze 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

(5)

Vector Vector

1 1 2 2 ... ... ⁹ ⁹

begin()

begin() end()end()

p p

p p p p p p p p

0 0

push_back()push_back()

p p

++++

• 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 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

(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)

Algoritmi 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

(11)

val

nodo

next prev

List List

• Le locazioni di memoria non sono contigue

– Lenta la ricerca, veloci inserimento ed estrazione

... ...

list top

val

nodo

next prev

val

nodo

next prev

bottom

(12)

List 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

(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 sequenze Esempio uso sequenze

vector vector

vector

list list

list

(14)

Contenitori associativi 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

(15)

#include <map>

#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;

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 <string>

int main() {

map<string,int> amap;

amap["Primo”]=1;

amap[“Secondo”]=2;

amap["Terzo"]=3;

amap["Quarto"]=4;

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;

}

La Standard Template Library La Standard Template Library