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.4
La libreria standard: iteratori e allocatori.
Iteratori

L’iteratore è un’astrazione della nozione di
puntatore ad un elemento di un array

Non c’è nessun iteratore “NULL”


Un iteratore fa riferimento ad un elemento valido se è
diverso dall’iteratore che segnala la fine della
sequenza
Un iteratore valido può essere dereferenziato
con *, ->, []

Un iteratore può non essere valido perché non è stato
inizializzato, oppure il contenitore a cui fa riferimento
è stato ridimensionato o distrutto, o infine se si tratta
del demarcatore di fine sequenza
Categorie di iteratori

Gli iteratori vengono classificati sulla base delle
operazioni che consentono di effettuare in tempo
costante







Complessità O(1)
Ingresso (In): solo letture e avanzamento
Uscita (Out): solo scrittura e avanzamento
In avanti (For): come In e Out insieme
Bidirezionali (Bi): come For, ma consentono di scorrere la
sequenza anche all’indietro
Ad accesso casuale (Ran): consentono l’accesso
indicizzato
Non sono delle classi con una nozione di
ereditarietà

Se es. un template della libreria standard ha come
argomento di tipo “In”, si presuppone che si tratti un
iteratore che supporta operazioni di lettura ed
avanzamento
Operazioni su categorie di iteratori
Out
In
For
Bi
Ran
lettura
= *p = *p = *p = *p
accesso
scrittura
->
->
->
-> []
*p = *p = *p =
iterazione ++
++
++
++
--
confronto
==
!=
==
!=
==
!=
*p =
++ -+ - +=
-=
== !=
< >
<= >=
const e non const

Indipendentemente dalla loro
categoria, gli iteratori possono essere
const o non const
Distanza tra iteratori


Solo gli iteratori ad accesso casuale
definiscono l’operatore –
La distanza tra iteratori può essere
calcolata mediante una funzione
template<class In>
int dinstance(In first, In last) {
int result = 0;
while (first++ != last)
d++;
return result;
}
iterator_traits

Il tipo di ritorno di difference() non
dovrebbe essere int ma
In::difference_type


tipo numerico con segno in grado di
contenere la differenza tra iteratori
… non funzionerebbe però con i
puntatori
iterator_traits

La libreria standard definisce un template
iterator_traits, che contiene tra l’altro:
template<class I>
struct iterator_traits {
typedef typename I::difference_type
difference_type;
};

Si può usare iterator_traits<I>::difference_type
anche su puntatori perché viene definita una
specializzazione per i puntatori
template<class T>
struct iterator_traits<T*> {
typedef ptrdiff_t diffference_type;
};
 la differenza tra puntatori viene rappresentata dal tipo
ptrdiff_t dichiarato in <cstddef>
Inseritori


Una sequenza di destinazione deve essere valida e
sufficientemente capiente
Per poter avere come destinazione un iteratore
che sottintende dei nuovi elementi che vengono
inseriti, nella libreria standard vengono definiti tre
classi template di iteratori e tre funzioni che ne
semplificano l’uso
template <class C> back_insert_iterator<C>
back_inserter(C& c);
template <class C> front_insert_iterator<C>
front_inserter(C& c);
template <class C, class Out> insert_iterator<C>
inserter(C& c, Out o);

Consentono l’uso es. di copy(v.begin(), v.end(),
back_inserter(l)) per ocpiare il contenuto del vector v in
coda alla lista l
reverse_iterator

i contenitori standard forniscono i
metodi rbegin() e rend() per ottenere
degli iteratori che scorrono la
sequenza all’incontrario

Partendo da rbegin(), con applicazioni
successive dell’operatore ++ si va dalla
fine all’inizio del contenitore
Iteratori e I/O

È possibile costruire un iteratore che
opera su un certo tipo di dato e
applicarlo ad un flusso
ostream_iterator<string> oo(cout);
*oo = “Salve ”;
oo++;
*oo = “e buona giornata”;
 istream_iterator<string> ii(cin);

 l’istream_iterator
predefinito indica la fine
del flusso, es.
istream_iterator<string> eos;
Allocatori


Un allocatore fornisce un metodo per allocare e
deallocare memoria
La libreria standard definisce in <memory> un
allocatore standard che fa uso degli operatori
predefiniti new() e delete
template<class T> class std::allocator {
typedef size_t size_type;
typedef T* pointer;
typedef const T* const_pointer;
pointer allocate(size_type n,
allocator<void>::const_pointer hint = 0);
void deallocate(pointer p, size_type n);
}