Guião da 2ª Aula Teórica

Sumário

Noção de lista e iterador.
1. Listas como sequências de itens com ordem relevante.
2. Iteradores como ferramenta para percorrer e referenciar itens em listas.
Operações com listas e iteradores.
Implementação parcial em C++.
Classes embutidas.

Guião

Atenção! É muito importante usar os termos de uma forma consistente. Assim:

Listas têm itens.
Iteradores associam-se a listas.
Iteradores referenciam item na lista a que estão associados.
Os itens não-fictícios extremos de uma lista são o item na frente e o item atrás!
Itens fictícios são itens que não existem mas que dá jeito poder referenciar.
As palavras primeiro, último, fim e início são reservadas para os iteradores.
Primeiro (iterador) é o iterador que referencia o item na frente.
Último (iterador) é o iterador que referencia o item atrás.
Iterador inicial é o iterador que referencia o item fictício antes do da frente.
Iterador final é o iterador que referencia o item fictício após o de trás.

Explicar noção de lista. Exemplificar com lista de afazeres.

Todos nós, ou pelo menos os mais organizados, já fizeram listas de afazeres. Por exemplo:

Estudar POO
Comprar CD "100th Window" dos Massive Attack
Fazer trabalho de SO
Combinar ida ao concerto dos Sigur Rós

Lista como sequência de itens em que a ordem é relevante mas não é dada pelos itens em si: é determinada por uma entidade exterior à lista que insere os itens pela ordem que entende.

Pedir para eles dizerem operações que se realizam com uma lista.

Ir listando e discutindo até surgir:

Construir nova lista.
Pôr item na frente da lista.
Pôr item na traseira da lista.
Tirar item da frente da lista.
Tirar item de trás da lista.
Saber item da frente.
Saber item de trás.
Saber comprimento.
Saber se está vazia.
Saber se está cheia (se tiver limite).
Esvaziar.
As restantes que surgirem devem ser descartadas por: a) Não serem atómicas nem particularmente úteis; b) não nos dar jeito avançar por aí (ser honesto!). Talvez se possa dar um lamiré sobre interfaces gordas e interfaces magras.

Falta uma operação fundamental... Inserir a meio! Como o fazer?

Suponham que a lista continha:

1 2 3 11 20 0 345 2 3 45 12 34 30 4 4 23 3 77 4 -1 -20 45

E suponham que o próximo item a inserir era 111.

Escolher um deles (da primeira fila e em frente ao quadro) e pedir-lhe para escolher mentalmente uma posição. Dizer-lhe para me referenciar a posição. Discutir com eles a melhor forma de o referenciar. Se necessário chamá-lo ao quadro. Normalmente isto acaba por resultar em o aluno apontar a posição no quadro. Se não resultar, transformar a coisa numa brincadeira.

Para além da lista em si, temos agora algo a que poderíamos chamar.... dedo.... Não... Eu podia referenciar com o cotovelo... Um bom nome poderia ser cursor, ou referência, ou indicador, mas o que vamos usar é o nome típico destas coisas: Iterador.

Conclusão: podem-se associar iteradores a listas!

Que operações se podem realizar com iteradores?

Discutir e chegar à seguintes:

Construir iterador... Discutir: associado a que lista? E referenciando que item?
Saber item referenciado pelo iterador.
Passar ao próximo item.
Recuar ao item anterior.
Comparar iteradores (igualdade e diferença).

E que operações se podem realizar com iteradores e listas?

Obter primeiro iterador, i.e., referenciando item na frente.
Obter último iterador, i.e., referenciando item atrás.
Inserir item antes do item referenciado pelo iterador. Discutir que isto é solução para o problema. Dizer que também poderia ser inserir depois, mas que inserir antes dá muito mais jeito... (porque os itens inseridos aparecem por ordem de inserção).
Remover item referenciado pelo iterador.

Discutir: que item referencia um iterador depois de uma remoção? Se se altera uma lista os seus iteradores ainda são válidos?

A resposta é nim. Sim, é o que é desejável, sempre que possível. Não, a nossa primeira versão invalidará os iteradores existentes...

Discutir: qual é o primeiro iterador de uma lista vazia?

Suponham que se pretende inserir um item numa lista ordenada:

1 3 4 6

Suponham que o item é 5. Que fazer?

Discutir algoritmo.

Suponham que o item é 7...

Discutir. Concluir que dá jeito que os iteradores possam referenciar itens fictícios! Chamar-lhes "final" e "inicial" ("fim" e "início" são os respectivos iteradores).

Representar sempre as listas a partir de agora no formato:

(! 1 3 4 6 !)

Faltam pois duas operações com iteradores:

Obter iterador para início, i.e., referenciando o item para aquém da frente da lista.
Obter iterador para o fim, i.e., referenciando o item para além da traseira da lista.

Vamos então desenhar a interface destas classes. Vamos supor que a lista guarda inteiros. Chamar-lhe-emos ListaDeInt e à classe dos seus iteradores Iterador.

Discutir passo a passo!

A classe que representa as listas propriamente ditas:

class ListaDeInt {
public:

Cria-se um sinónimo para simplificar a tarefa de criar listas para itens de outros tipos:

typedef int Item;

Declara-se uma classe embutida que implementa o conceito de iterador (serve para percorrer e manipular listas). Explicar o que significa embutida. Discutir vantagem de ser embutida! O conceito de iterador faz sentido para listas mas também para outros tipos de contentor. Assim evitam-se colisões de nomes...

class Iterador;

O construtor da classe (que cria uma lista vazia):

ListaDeInt();

Inspectores para saber os itens na frente e atrás da lista:

Item const& frente() const;
Item const& trás() const;

Inspector que devolve o comprimento da lista:

int comprimento() const;

Inspectores para saber se a lista está vazia ou cheia:

bool estáVazia() const;
bool estáCheia() const;

Cheia? Pois... Esqueci-me de dizer que a nossa primeira versão das listas tem um limite fixo para o número de itens.

Modificadores para inserir e retirar itens da lista dos seus locais de mais fácil acesso:

    void põeNaFrente(Item const& novo_item);
    void põeAtrás(Item const& novo_item);
    void tiraDaFrente();
    void tiraDeTrás();

Modificador para inserir um item imediatamente antes da posição referenciada pelo iterador, fazendo com que o iterador continue a referenciar o mesmo item. Discutir necessidade de passagem por referência não-constante!

void insereAntes(Iterador& iterador, Item const& novo_item);

Modificador para remover o item referenciado pelo iterador iterador, ficando o iterador a referenciar o item logo após o item removido. Mesma discussão!

void remove(Iterador& iterador);

Modificador para esvaziar a lista:

void esvazia();

Métodos para devolver iteradores referenciando os locais cabalísticos da lista :

    Iterador primeiro();
    Iterador ultimo();
    Iterador inicio();
    Iterador fim();

São inspectores ou modificadores?

private:

Já lá vamos!

Dá-se à classe de iteração acesso às listas. Discutir porque é que isto é boa ideia! Explicar que o conceito de lista é representado na realidade por duas classes: ListaDeInt e Iterador. Quando assim é não devemos ter receio de usar as amizades, pois não são promiscuidades: são intimidades perfeitamente legítimas...

friend class Iterador;

};

A classe para representar iteradores que referenciam itens em listas ListaDeInt:

class ListaDeInt::Iterador {
public:

O construtor da classe. Constrói um iterador associado à lista lista e põe-no a referenciar o seu primeiro item. Discutir explicit.

Para não escrevermos i == lista sem que o compilador dê erro!

explicit Iterador(ListaDeInt& lista_associada);

Inspector que devolve o item referenciado pelo iterador:

Item& item() const;

Explicar que é inspector do iterador, pois não o altera, mas que permite alterar o item referenciado.

Os operadores de comparação entre itens.

bool operator==(Iterador const& outro_iterador) const;
bool operator!=(Iterador const& outro_iterador) const;

Incrementação e decrementação prefixa e sufixa de iteradores (avança e recua para o próximo/anterior item):

    Iterador& operator ++();
    Iterador& operator--();
    Iterador operator++(int);
    Iterador operator--(int);

private:

Já lá vamos!

A classe ListaDeInt tem acesso a todos os membros da classe Iterador. Notar que a amizade é recíproca! E que não é nenhuma promiscuidade! É um casamento! Por amor, e não por conveniência...

friend class ListaDeInt; };

Usando estas classes, como mostrar os itens de uma lista no ecrã?

Usar uma lista que ainda esteja no quadro e explicar informalmente o algoritmo. Discutir condição de paragem.

ListaDeInt l;
... // aqui inserem-se vários itens.
for(ListaDeInt::Iterador i = l.primeiro(); i != l.fim(); ++i)
cout << i.item() << endl;

Usando estas classes, como inserir um novo item com valor n numa lista lista por ordem?

Usar uma lista que ainda esteja no quadro e explicar (de novo) informalmente o algoritmo. Discutir condição de paragem.

ListaDeInt lista;
... // aqui inserem-se vários itens.
int n;
cin >> n;

ListaDeInt::Iterador i = lista.primeiro(); while(i != lista.fim() && i.item() < n) ++i;

lista.insere(i, n);

Mostrar que funciona bem mesmo que o item tenha de ser inserido no fim da lista. Mostrar que funciona bem mesmo que o item tenha que ser inserido numa lista vazia...

Falta-nos discutir a implementação disto... Comecemos pela classe ListaDeInt. Onde guardar os itens?

Discutir e concluir que, se a lista tiver um número finito constante de itens, então os itens podem ser colocados numa matriz. Dizer que podia ser um vector, mas dá-nos jeito que seja uma matriz para as próximas aulas...

class ListaDeInt {
    ...
private:
    static int const número_máximo_de_itens = 100;

    Item itens[número_máximo_de_itens];
    int número_de_itens;
};

Qual a condição invariante desta classe?

Discutir. Concluir que é:

CIC: 0 <= número_de_itens <= número_máximo_de_itens.

Pode-se pôr um método privado para verificar o invariante!

class ListaDeInt {
    ...
private:
    static int const número_máximo_de_itens = 100;

    Item itens[limite];
    int número_de_itens;
    bool cumpreInvariante() const;
};
bool ListaDeInt::cumpreInvariante() const {
    return 0 <= número_de_itens and número_de_itens <= número_máximo_de_itens;
}

E a classe Iterador? Como implementá-la?

Discutir que os iteradores têm de saber: (a) a posição do item e (b) a lista onde estão! Pode haver mais do que uma lista! Necessidade de referência!

class ListaDeInt::Iterador {
    ... private:
    ListaDeInt& lista_associada;
    int indice_do_item_referenciado;
};

Qual a condição invariante de instância desta classe?

Discutir. Deixar claro que os iteradores podem ficar inválidos... Concluir que é:

-1 <= índice_do_item_referenciado.

Pode-se pôr um método privado para verificar o invariante:

class ListaDeInt::Iterador {
    ... private:
    ListaDeInt& lista_associada;
    int indice_do_item_referenciado;
    bool cumpreInvariante() const;
};

bool ListaDeInt::Iterador::cumpreInvariante() const {
    return -1 <= índice_do_item_referenciado;
}

Faltam as operações! Comecemos pelo construtor da lista:

inline ListaDeInt::ListaDeInt()
: número_de_itens(0) {

assert(cumpreInvariante());
}

Simples, não?

Vamos agora para o põeNaFrente().

Discutir algoritmo: empurrar itens para a frente. A lista não pode estar cheia! Discutir assert(). Lembrar #include <cassert>.

void ListaDeInt::põeNaFrente(Item const& novo_item) {

Verificar se cumpre condição invariante!

assert(cumpreInvariante());

Só se pode inserir se ainda houver espaço:

assert(not estáCheia());

Inserir no início implica rearranjar todos os itens já na lista:

for(int i = comprimento(); i != 0; --i)
itens[i] = itens[i - 1];

Agora já há espaço:

itens[0] = novo_item;

E convém incrementar o contador de elementos...

++número_de_itens;

Confirmar que no final também cumpre invariante!

assert(cumpreInvariante());
}

Vamos agora ao procedimento tiraDeTrás(). Sugestões? É simples:

inline void ListaDeInt::tiraDeTrás() {
    assert(cumpreInvariante());
    assert(!vazia());

    --numero_de_itens;
    assert(cumpreInvariante());
}

Saltámos uns quantos métodos que ficam para a aula prática. Mas vamos agora ver o procedimento de inserção antes de um iterador. A ideia é parecida com a inserção no início, só que não é preciso, em geral, rearranjar todos os itens...

void ListaDeInt::insereAntes(Iterador& iterador, const Item& novo_item) {
assert(cumpreInvariante());
assert(not cheia());

Não se pode inserir se o iterador referir o elemento antes do primeiro!

assert(iterador != inicio());

Há que rearranjar todos os itens a partir do referenciado pelo iterador:

for(int i = comprimento(); i != iterador.indice_do_item_referenciado; --i)
itens[i] = itens[i - 1];

Agora já há espaço. Discutir revalidação do iterador!

    itens[iterador.índice_do_item_referenciado] = novo_item;

    ++iterador.índice_do_item_referenciado;

    assert(iterador.cumpreInvariante());
    ++número_de_itens;
    assert(cumpreInvariante());
}

E outros métodos simples:

inline int ListaDeInt::comprimento() const {
    assert(cumpreInvariante());

    return numero_de_itens;
}

inline bool ListaDeInt::estáVazia() const {
    assert(cumpreInvariante());
    return comprimento() == 0;
}

Agora vamos a métodos mais interessantes! Que tal o que devolve o primeiro iterador? Como resolver?

Discutir construtor do iterador.

inline ListaDeInt::Iterador ListaDeInt::primeiro() {
    assert(cumpreInvariante());

    Iterador iterador(*this);

    assert(cumpreInvariante());

    return iterador;
}

ou simplesmente:

inline ListaDeInt::Iterador ListaDeInt::primeiro() {
assert(cumpreInvariante());

return Iterador(*this);
}

E o último? É parecido, mas temos de alterar o índice!

inline ListaDeInt::Iterador ListaDeInt::ultimo() {
assert(cumpreInvariante());

Iterador iterador(*this);

O iterador deve referenciar o item na traseira da lista:

    iterador.indice_do_item_referenciado = comprimento() - 1;

    assert(iterador.cumpreInvariante());     assert(cumpreInvariante());
    return iterador;
}

E o mesmo para as outras...

inline ListaDeInt::Iterador ListaDeInt::inicio() {
assert(cumpreInvariante());

Iterador iterador(*this);

O iterador deve referenciar o item fictício antes da frente da lista:

    iterador.indice_do_item_referenciado = -1;

    assert(iterador.cumpreInvariante());     assert(cumpreInvariante());
    return iterador;
}
inline ListaDeInt::Iterador ListaDeInt::fim() {
    assert(cumpreInvariante());
    Iterador iterador(*this);

O iterador deve referenciar o item fictício após o último item da lista:

    iterador.indice_do_item_referenciado = comprimento();

    assert(iterador.cumpreInvariante());     assert(cumpreInvariante());
    return iterador;
}

Já só faltam os procedimentos e funções da classe Iterador. Comecemos pelo construtor.

Discutir índice 0. Discutir necessidade de lista de inicializadores.

inline ListaDeInt::Iterador::Iterador(ListaDeInt& l)
: lista_associada(l), indice_do_item_referenciado(0) {

assert(cumpreInvariante());
}

E agora o operador de decrementação, que serve para recuar na lista.

Discutir recuo para aquém do primeiro: válido. E para aquém do início: inválido!

inline ListaDeInt::Iterador& ListaDeInt::Iterador::operator--() {
    assert(cumpreInvariante());
    assert(*this != lista_associada.inicio());

    --indice_de_item_referenciado;
    assert(cumpreInvariante());
    return *this;
}

Falta uma função importante: a comparação entre iteradores. Quando são dois iteradores iguais?

Discutir e concluir que são iguais quando se referem ao mesmo item. E que além disso não faz sentido comparar iteradores associados a listas diferentes! Mas como comparar as listas? Fica p'rá próxima...

inline bool ListaDeInt::Iterador::operator==(const Iterador& outro_iterador) const {
    assert(cumpreInvariante() and outro_iterador.cumpreInvariante());
    // assert(iteradores associados à mesma lista...);

    return indice_do_item_referenciado == outro_iterador.indice_do_item_referenciado;
}
inline bool ListaDeInt::Iterador::operator!=(const Iterador& outro_iterador) const {
    assert(cumpreInvariante() and outro_iterador.cumpreInvariante());
    // assert(iteradores associados à mesma lista...);
    return indice_do_item_referenciado != outro_iterador.indice_do_item_referenciado;
}

E há outra interessante: saber qual o item referenciado pelo iterador. Quando é tal operação possível?

Discutir!

ListaDeInt::Item& ListaDeInt::Iterador::item() {
    assert(cumpreInvariante());
    assert(*this != lista_associada.inicio() and
           *this != lista_associada.fim());

    return lista_associada.itens[indice_do_item_referenciado];
}