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.3
La libreria standard: implementazione di
alcuni algoritmi.
for_each

Il for_each è un algoritmo molto semplice
generico
consente di applicare un oggetto funzione ad
ogni membro di una sequenza
 restituisce l’oggetto funzione stesso
template<class In, class Op>
Op for_each(In first, In last, Op f) {
while (first != last)
f(*first++);
return f;
}

count


Conta il numero di occorrenze di un elemento in
una sequenza
Una versione molto semplice, usando un int come
contatore, è:
template<class In, class T>
int count(In first, In last, const T& val) {
int result = 0;
while (first != last)
if (*first++ == val)
result++;
return result;
}
 La versione nella libreria standard utilizza come tipo di
ritorno iterator_traits<In>::difference_type
mismatch

Cerca la prima coppia di elementi non corrispondenti in due
sequenza

La prima sequenza è definita da una coppia di iteratori, mentre
della seconda è riportato solo l’inizio
template<class In1, class In2>
pair<In1, In2> mismatch(In1 first1, In1 last1,
In2 first2) {
while (first1 != last1 && *first1 == *first2)
{
first1++;
first2++;
}
return pair<In1, In2>(first1, first2);
}
copy

Copia una sequenza in un’altra
Della seconda sequenza viene specificato solo l’inizio: deve essere lunga lameno
quanto la prima
template<class In, class Out>
Out copy(In first, In last, Out result) {
while (first != last)
*result++ = *first++;
return result;
}


Non viene definito dalla libreria standard, ma è immediato da definire, un
copy_if che copia gli elementi che soddisfano un predicato
template<class In, class Out, class Pred>
Out copy_if(In first, In last, Out result, Pred p) {
while (first != last) {
if (p(*first))
*result++ = *first;
first++;
}
return result;
}
transform

Produce una sequenza applicando
una operazione ad ogni elemento di
una sequenza
template<class In, class Out,
class Op>
Out transform(In first, In last,
Out result, Op op) {
while (first != last)
*result++ = op(*first++);
return result;
}
replace

Sostituisce le occorrenze di un valore in
una sequenza con un altro valore
template<class For, class T>
void replace(For first, For last, const
T& val, const T& new_val) {
while (first != last) {
if (*first == val)
*first = new_val;
first++;
}
}
swap
Tramite i template viene definita nella
libreria standard una versione generica
della funzione che scambia il valore di due
variabili, passate tramite riferimenti
template<class T>
void swap(T& a, T& b) {
T temp = a;
a = b;
b = temp;
}

lexicographical_compare

L’algoritmo di ordinamento lessicografico, usato per ordinare
alfabeticamente i dizionari, può essere generalizzato a
sequenze qualsiasi
template<class In1, class In2>
bool lexicographical_compare(In1 first1, In1 last1,
In2 first2, In2 last2) {
while (first1 != last1 && first2 != last2) {
if (*first1 < *first2)
return true;
if (*first2++ << *first1++)
return false;
}
return first1 == last1 && first2 != last2;
}


Utilizza solo l’operatore <
Restituisce true se la prima sequenza è “minore” della seconda