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.2
La libreria standard: algoritmi e oggetti
funzione.
Complessità computazionale

La complessità di un’elaborazione può essere definita

in termini di tempo di esecuzione


in termini di occupazione di memoria


complessità spaziale
La complessità è espressa come funzione della dimensione
dell’input



complessità temporale
es. numero di elementi da ordinare, numero di elementi in un
contenitore
è una misura di complessità relativa, perché il tempo
effettivamente impiegato o la memoria effettivamente occupata
dipendono dallo specifico elaboratore
Notazione O

se la complessità di una certa operazione è f(n), dove n è la
dimensione dell’input, la complessità appartiene alla famiglia
O(g), dove g è funzione di n, se e solo se esistono una costante
positiva k ed un n’ tali che, per tutti gli n > n’,
f(n) <= k * g(n)
Complessità delle operazioni sui
contenitori
[]
vector
O(1)
list
deque
O(1)
insert
front /
erase push_front
back /
push_back
O(n)1
O(1) / O(n)2
O(1)
O(1)
O(1)
O(n)
O(1) /
O(n)2
O(1) / O(n)2
stack
queue
O(1) / O(n)2
O(1) /
O(n)2
O(1) / O(n)2
priority-queue
1.
2.
O(log n) /
O(log n) /
O(n)2 tutti i successivi;
O(n)2a volte
Inserire o eliminare un elemento comporta spostare
è necessario spostarli tutti
Normalmente richiede un tempo costante, ma se non c’è spazio disponibile
occorre spostare tutto il vettore
Algoritmi generici


Sui contenitori sono disponibili operazione
per accedere e manipolare membri
La libreria standard l’implementazione di
algoritmi generici


Indipendenti dal contenitore e dal tipo
dell’oggetto contenuto
Operano su sequenze


Definite da coppie di iteratori
#include <algorithm>
Esempi: sort, unique_copy, find…
Esempio: ordinare e copiare
vector<Elemento> v;
lista<Elemento> l;
// …
sort(v.begin(), v.end());
unique_copy(v.begin(),
v.end(), l.begin());
Esempio: cercare e contare
string s;
char c;
string::const_iterator i =
find(s.begin(), s.end(), c);
int n = count(s.begin(),
s.end(), c);
Esempio: cercare un elemento
vector<int> v;
// …
vector<int> const_iterator
result = find(v.begin(),
v.end(), 42);
cout << result == v.end() ?
“non presente” : “presente”;

Come sarebbe fatto usando list?
Esempio: array
Gli algoritmi possono essere usati
anche su array, usando i puntatori
come iteratori
int a[6] = {1, 2, 3, 5, 7,
11};
int* result = find(a, a + 6,
42);
cout << result == a + 6 ?
“non presente” : “presente”;

Algoritmi: presupposti

Un algoritmo ha bisogno di:




attraversare la collezione, avanzando da un
elemento al successivo, a partire dal primo;
sapere quando fermarsi, ovvero quando si
arriva alla fine della sequenza;
accedere ad un elemento deferenziando un
iteratore
L’iteratore “uno-dopo-l’ultimo” serve dunque:


come valore sentinella
nel caso di alcuni algoritmi (es. find), viene restituito
come valore che indica fallimento (es. elemento non
trovato)
Algoritmi che non modificano
una sequenza












for_each invoca una funzione per ogni argomento
find trova la prima occorrenza dell’argomento
find_if trova il primo elemento che soddisfa un predicato
find_first_of cerca un valore di una sequenza in un’altra
adjacent_find cerca una coppia di valori consecutivi
count conta le occorrenze di un valore
count_if conta gli elementi che verificano una condizione
mismatch trova il primo elemento diverso di due sequenze
equal controlla se due sequenze sono uguali
search cerca la prima ocorrenza di una sottosequenza
find_end cerca l’ultima occorrenza di una sequenza
search_n cerca l’n-esima occorrenza di un valore in una
sequenza
Algoritmi che modificano una
sequenza

























transform applica un’operazione a tutti gli elementi
copy copia elementi
copy_backward copia a partire dall’ultimo elemento
swap scambia due elementi
iter_swap scambia due elementi indicato
swap_rages scambia gli elementi di due sequenze
replace sostituisce elementi con un nuovo valore
replace_if sostituisce elementi che verificano una condizione
replace_copy copia una sequenza sostituendo gli elementi che hanno un certo valore
replace_copy_if copia una sequenza sostituendo tutti gli elementi che soddisfano un predicato
fill sostituisce tutti gli elementi con un valore
fill_n sostituisce i primi n elementi con un certo valore
unique_copy copia omettendo i duplicati
generate sostituisce ogni elementi con il risultato di un’operazione
generate_n sostituisce i primi n elementi con il risultato di un’operazione
remove rimuove gli elementi che hanno un certo valore
remove_if rimuove gli elementi che soddisfano un predicato
remove_copy copia una sequenza rimuovendo gli elementi con un certo valore
remov_copy_if copia una sequenza rimuovendo gli elementi che soddisfano un predicato
unique rimuove gli elementi adiacenti uguali
unique_copy copia una sequenza rimuovendo gli elementi adiacenti uguali
reverse inverte l’ordine degli elementi
rotate ruota gli elementi
rotate_copy copia gli elementi in una sequenza ruotata
randm_shuffe mischia gli elementi a caso, con distribuzione uniforme
Ordinamenti e algoritmi su
sequenza ordinate













sort ordina
stable_sort ordina mantenendo l’ordine precedente degli
elementi uguali
partial_sort ordina la prima parte di una sequenza
partial_sort_copy copia ordinando la prima parte di una
sequenza
nth_element sistema l’n-esimo elemento al proprio posto
lower_bound cerca la prima occorrenza
upper_bound cerca il primo elemento maggiore
equal_range cerca una sequenza con un dato valore
binary_search cerca in una sequenza ordinata
merge fonde sequenze ordinate
inplace_merge fonde sequenze ordinate consecutive
partition muove in testa elementi che soddisfano una
condizione
stable_partition muove in testa elementi che soddisfano una
condizione mantenendo il loro ordine relativo
Algoritmi su insiemi
includes verifica l’inclusione di una
sequenza in un’altra
 set_union unione
 set_intersection intersezione
 set_difference differenza (elementi
nella prima sequenza ma non nella
seconda)
 set_symmetric_difference elementi in
una delle sequenze ma non in
entrambe

Algoritmi su heap
Gli heap sono dei gruppo, non necessariamente
ordinati, che mantengono una sequenza in
maniera che sia facile ordinare.
make_heap costruisce un heap da
una sequenza
 push_heap aggiunge un elemento
 pop_heap rimuove un elemento
 sort_heap ordina

Minimi e massimi; permutazioni







min il minore di due valori
max il maggiore di due valori
min_element il minore di una sequenza
max_element il maggiore di una sequenza
lexicographical_compare confronto
lessicografico
next_permutation permutazione
successiva, in ordine lessicografico
prev_permutation permutazione
precedente, in ordine lessicografico
Funzioni come parametri

Molti algoritmi che operano su
sequenze hanno la possibilità di
accettare un parametro in più che
indica l’operazione da eseguire

es.
bool minoredi2(int i) {
return i < 2;
}
find_if(v.begin(), v.end(), minoredi2);
Oggetti funzione

Istanze di una classe che ridefinisce l’operatore ()
possono essere usate come funzioni

es.
template<class T> class accumulatore {
T a;
public:
accumulatore(T i = 0) : a(i) { }
void operator()(T x) { a += x; }
T valore() const { return a; }
};
accumulatore<float> acc;
vector<float> v;
// …
acc = for_each(v.begin(), v.end(), acc);
cout << “la somma è “ << s.valore() << endl;
Oggetti funzione standard:
predicati
Un predicato è un oggetto funzione che restituisce un
bool









equal_to
not_equal_to
greater
less
greater_equal
less_equal
logical_and
logical_or
logical_not
Oggetti funzione aritmentici
plus
 minus
 multiplies
 divides
 modulus
 negate

Connettori e adattatori
Un binder (connettore) consente di utilizzare un
oggetto funzione a due parametri come oggetto
funzione ad un parametro fissando un argomento
bind2nd
 binf1st
Un adattatore consente di un funzione come
argomento di un algoritmo
 mem_fun usa un puntatore ad un metodo
 mem_fun_ref usa un riferimento ad un
metodo
 ptr_fun usa un puntatore a funzione

Algoritmi che usano funzioni
membro

class Elemento {
string nome;
public:
void print() {
cout << nome;
}
}
list<Elemento> l;
foreach(l.begin(), l.end(),
mem_fun(&Elemento::print));