Aula 2
Listas e iteradores
1
O que é uma lista?

Exemplo:




2
Estudar POO
Comprar prenda para o dia do pai
Fazer trabalho de SO
Comprar bilhete para o Rock in Rio
2003/2004
Programação Orientada para
Objectos
Uma lista é…



3
Sequência de itens
Ordem é relevante
Ordem determinada por entidade exterior à
lista
2003/2004
Programação Orientada para
Objectos
Operações com listas







4
Construir
Pôr item na frente
Pôr item na traseira
Tirar item da frente
Tirar item de trás
Saber item da frente
Saber item de trás




2003/2004
Saber comprimento
Saber se está vazia
Saber se está cheia
(caso exista limite)
Esvaziar
Programação Orientada para
Objectos
Iterador

Ferramenta para percorrer e referenciar itens
em listas




5
Estudar POO
Comprar prenda para o dia do pai
Fazer trabalho de AC II
Comprar bilhete para o Rock in Rio
2003/2004
Programação Orientada para
Objectos
Operações com iteradores





6
Construir
Saber item referenciado
Passar ao próximo item
Recuar para o item anterior
Comparar iteradores (igualdade e diferença)
2003/2004
Programação Orientada para
Objectos
Operações: listas e iteradores




7
Iterador que
referencia o primeiro
item da lista.
Obter iterador primeiro
Obter iterador último
Inserir item antes do item referenciado pelo
iterador
Remover item referenciado pelo iterador
2003/2004
Programação Orientada para
Objectos
Itens fictícios

Item inicial



Item final


8
Item aquém da frente da lista
Referenciado pelo iterador início
Item além da traseira da lista
Referenciado pelo iterador fim
2003/2004
Programação Orientada para
Objectos
Exemplo
Itens regulares.
(!1346!)
Item fictício
inicial.
9
Item fictício
final.
2003/2004
Programação Orientada para
Objectos
Operações: listas e iteradores
(actualização)






10
Obter iterador primeiro
Obter iterador último
Inserir item antes do item referenciado pelo
iterador
Remover item referenciado pelo iterador
Obter iterador início
Obter iterador fim
2003/2004
Programação Orientada para
Objectos
Interface das listas
class ListaDeInt {
public:
typedef int Item;
void
void
void
void
põeNaFrente(Item const& item);
põeAtrás(Item const& item);
tiraDaFrente();
tiraDeTrás();
class Iterador;
ListaDeInt();
Item const& frente() const;
Item const& trás() const;
int comprimento() const;
bool estáVazia() const;
bool estáCheia() const;
11
void insereAntes(Iterador& iterador,
Item const& item);
void remove(Iterador& iterador);
void esvazia();
Iterador
Iterador
Iterador
Iterador
2003/2004
primeiro();
último();
início();
fim();
Programação Orientada para
Objectos
Classes dentro de classes

Classes embutidas




12
Definidas dentro de uma classe envolvente
Membro da classe envolvente
Evitam repetições de nomes
Relação íntima com classe envolvente
2003/2004
Programação Orientada para
Objectos
Interface dos iteradores
class ListaDeInt::Iterador {
public:
explicit Iterador(ListaDeInt& lista_associada);
Item& item() const;
bool operator==(Iterador const& outro_iterador) const;
bool operator!=(Iterador const& outro_iterador) const;
Iterador& operator++();
Iterador& operator--();
Iterador operator++(int);
Iterador operator--(int);
13
2003/2004
Programação Orientada para
Objectos
Mostrar itens no ecrã
ListaDeInt lista;
// Inserção de itens…
for(ListaDeInt::Iterador i = lista.primeiro();
i != lista.fim();
++i)
cout << i.item() << endl;
14
2003/2004
Programação Orientada para
Objectos
Inserir por ordem
ListaDeInt lista;
// Inserção de itens…
int n;
cin >> n;
ListaDeInt::Iterador i = lista.primeiro();
while(i != lista.fim() and i.item() < d)
++i;
lista.insere(i, d);
15
2003/2004
Programação Orientada para
Objectos
Implementação das listas
class ListaDeInt {
…
return 0 <= número_de_itens and
número_de_itens <= número_máximo_de_itens;
private:
static int const número_máximo_de_itens = 100;
Item itens[número_máximo_de_itens];
int número_de_itens;
bool cumpreInvariante() const;
friend class Iterador;
};
16
2003/2004
Programação Orientada para
Objectos
Implementação dos iteradores
class ListaDeInt::Iterador {
…
return -1 <= índice_do_item_referenciado;
private:
ListaDeInt& lista_associada;
int índice_do_item_referenciado;
bool cumpreInvariante() const;
friend class ListaDeInt;
};
17
2003/2004
Programação Orientada para
Objectos
ListaDeInt: métodos (I)
inline
ListaDeInt::ListaDeInt()
: número_de_itens(0)
{
assert(cumpreInvariante());
}
inline bool
ListaDeInt::estáVazia() const
{
assert(cumpreInvariante());
inline int
ListaDeInt::comprimento() const
{
assert(cumpreInvariante());
}
return comprimento() == 0;
return número_de_itens;
}
18
2003/2004
Programação Orientada para
Objectos
ListaDeInt: métodos (II)
void ListaDeInt::põeNaFrente(Item const& item)
{
assert(cumpreInvariante());
assert(not estáCheia());
for(int i = comprimento(); i != 0; --i)
itens[i] = itens[i – 1];
itens[0] = item;
++número_de_itens;
assert(cumpreInvariante());
}
19
2003/2004
Programação Orientada para
Objectos
ListaDeInt: métodos (III)
void ListaDeInt::tiraDeTrás()
{
assert(cumpreInvariante());
assert(not estáVazia());
--número_de_itens;
assert(cumpreInvariante());
}
20
2003/2004
Programação Orientada para
Objectos
ListaDeInt: métodos (IV)
void ListaDeInt::insereAntes(Iterador& iterador, Item const& item)
{
assert(cumpreInvariante());
assert(not estáCheia());
assert(iterador != início());
for(int i = comprimento();
i != iterador.índice_do_item_referenciado;
--i)
itens[i] = itens[i – 1];
itens[iterador.índice_do_item_referenciado] = item;
(continua…)
21
2003/2004
Programação Orientada para
Objectos
ListaDeInt: métodos (V)
(continuação)
++iterador.índice_do_item_referenciado;
assert(iterador.cumpreInvariante());
++número_de_itens;
assert(cumpreInvariante());
}
22
2003/2004
Programação Orientada para
Objectos
ListaDeInt: métodos (VI)
inline ListaDeInt::Iterador
ListaDeInt::primeiro()
{
assert(cumpreInvariante());
Iterador iterador(*this);
assert(cumpreInvariante());
Ou simplesmente:
inline ListaDeInt::Iterador
ListaDeInt::primeiro()
{
assert(cumpreInvariante());
return iterador;
}
23
return Iterador(*this);
}
2003/2004
Programação Orientada para
Objectos
ListaDeInt: métodos (VI)
inline ListaDeInt::Iterador ListaDeInt::último()
{
assert(cumpreInvariante());
Iterador iterador(*this);
iterador.índice_do_item_referenciado = comprimento() – 1;
assert(iterador.cumpreInvariante());
assert(cumpreInvariante());
return iterador;
}
24
2003/2004
Programação Orientada para
Objectos
ListaDeInt: métodos (VII)
inline ListaDeInt::Iterador ListaDeInt::início()
{
assert(cumpreInvariante());
Iterador iterador(*this);
iterador.índice_do_item_referenciado = –1;
assert(iterador.cumpreInvariante());
assert(cumpreInvariante());
return iterador;
}
25
2003/2004
Programação Orientada para
Objectos
ListaDeInt: métodos (VIII)
inline ListaDeInt::Iterador ListaDeInt::fim()
{
assert(cumpreInvariante());
Iterador iterador(*this);
iterador.índice_do_item_referenciado = comprimento();
assert(iterador.cumpreInvariante());
assert(cumpreInvariante());
return iterador;
}
26
2003/2004
Programação Orientada para
Objectos
ListaDeInt::Iterador:
métodos (I)
inline ListaDeInt::Iterador::Iterador(ListaDeInt& lista)
: lista_associada(lista), índice_do_item_referenciado(0)
{
assert(cumpreInvariante());
}
inline ListaDeInt::Iterador& ListaDeInt::Iterador::operator--()
{
assert(cumpreInvariante());
assert(*this != lista_associada.início());
--índice_do_item_referenciado;
assert(cumpreInvariante());
return *this;
}
27
2003/2004
Programação Orientada para
Objectos
ListaDeInt::Iterador:
métodos (II)
inline
bool ListaDeInt::Iterador::operator==(Iterador const& outro) const
{
assert(cumpreInvariante() and outro.cumpreInvariante());
// assert(iteradores associados à mesma lista…);
return índice_do_item_referenciado ==
outro.índice_do_item_referenciado;
}
28
2003/2004
Programação Orientada para
Objectos
ListaDeInt::Iterador:
métodos (III)
inline
bool ListaDeInt::Iterador::operator!=(Iterador const& outro) const
{
assert(cumpreInvariante() and outro.cumpreInvariante());
// assert(iteradores associados à mesma lista…);
return índice_do_item_referenciado !=
outro.índice_do_item_referenciado;
}
29
2003/2004
Programação Orientada para
Objectos
ListaDeInt::Iterador:
métodos (IV)
ListaDeInt::Item& ListaDeInt::Iterador::item()
{
assert(cumpreInvariante());
assert(*this != lista_associada.início() and
*this != lista_associada.fim());
return lista_associada.itens[índice_do_item_referenciado];
}
30
2003/2004
Programação Orientada para
Objectos
Aula 2

Noção de lista e de iterador





31
Listas como sequências de itens com ordem
relevante
Iteradores como ferramentas para percorrer e
referenciar itens em listas
Operações com listas e iteradores
Implementação parcial
Classes embutidas
2003/2004
Programação Orientada para
Objectos