Exercícios

1.a)  Altere a implementação das classes ListaDouble e Iterador de modo a recorrer unicamente a
ponteiros e não a índices.  Cada elo das cadeias deve guardar, para além do item, ponteiros para os elos anterior e seguinte da cadeia.  A associação entre iteradores e listas deve passar a ser feita usando ponteiros, e não referências como até aqui.  Porquê?

R:
Porque de outra forma não se podem fazer atribuições entre iteradores.  Ou seja,

ListaDouble l1;
ListaDouble::Iterador i = l1.primeiro();
ListaDouble l2;
ListaDouble::Iterador j = l2.final();
j = i;

O que acontece é que o C++ tenta definir a atribuição entre instâncias de classes fazendo automaticamente a atribuição variável membro a variável membro.  Claro está que este esquema falha se existir alguma constante membro de instância, pois constantes não se pode atribuir um valor a uma constante, só se pode inicializá-la (faça uma classe que tenha uma constante membro de instância e experimente atribuir uma instância a outra...).  Mas o problema não é este.

O esquema também falha se existir alguma referência membro de instância.  É o que se passa com os iteradores, que têm uma referência membro lista que em cada iterador referencia a lista a que ele está associado.  Que deveria resultar da atribuição acima?  A referência do iterador j deveria mudar de modo a referir a lista l1 em vez da lista l2?  Acontece que no C++ as referências são imutáveis: uma vez estabelecido um sinónimo, ele durará até ao fim da sua vida.  É o que se passa com os pseudónimos dos escritores.  Álvaro Cunhal escolheu Manuel Tiago como pseudónimo.  Parecer-lhe-ia razoável que de um dia para o outro Manuel Tiago passasse a ser o pseudónimo do Pacheco Pereira?

Se a associação entre iterador e lista for representada por um ponteiro este problema não se põe.  Durante a atribuição o endereço da lista a que o iterador j está associado deixa de ser o endereço de l2 e passa a ser o endereço de l1.  Exactamente como se pretendia.

1.b)  A função membro da classe ListaDouble::Iterador que devolve o item referenciado pelo iterador deve passar a chamar-se operator *, por analogia com os ponteiros:

ListaDouble::Item& ListaDouble::Iterador::operator *() const;

1. Crie uma classe Aluno, capaz de guardar o nome e o número de identificação de um aluno.  As funções e procedimentos membro e não membro a desenvolvor são:
• Construtor da classe Aluno:
Aluno::Aluno(string const& nome = "", int const numero = 0);
• Funções membro de inspecção:
string Aluno::nome() const;
int Aluno::numero() const;
• Operadores relacionais:
bool operator < (Aluno const& a, Aluno const& b);
bool operator <= (Aluno const& a, Aluno const& b);
bool operator > (Aluno const& a, Aluno const& b);
bool operator >= (Aluno const& a, Aluno const& b);
• Operadores de igualdade e diferença:
bool operator == (Aluno const& a, Aluno const& b);
bool operator != (Aluno const& a, Aluno const& b);
• Operador de inserção num canal:
ostream& operator << (ostream& saida, Aluno const& a);
2. Converta as classes ListaDouble e ListaDouble::Iterador de modo a obter listas e iteradores com itens da classe Aluno.
3. Construa um programa que crie (e mostre) uma lista de 20 alunos ordenada pelo seu número.  Preencha a lista com dados lidos do teclado.

1. Remoção de todos os itens da lista:
void ListaAluno::limpa();
2. Implemente novos métodos insere() e remove() mas com o parâmetro Iterador& iterador constante (nada se garante acerca da validade dos iteradores depois da operação):
void ListaAluno::insere(Iterador const& iterador, Item const& item);
void ListaAluno::remove(Iterador const& iterador);
3. Transferência do conteúdo de uma lista para uma outra (de lista para a instância implícita):
void ListaAluno::transfere(ListaAluno& lista);
4. Procura da primeira ocorrência de um determinado item na lista:
Iterador ListaAluno::procuraPrimeiro(Item const& item);
5. Procura da última ocorrência de um determinado item na lista:
Iterador ListaAluno::procuraUltimo(Item const& item);
6. Acrescentar itens de lista à instância implícita (concatenação de duas listas):
ListaDouble& ListaAluno::operator += (ListaDouble const& l);

R:
Apresentam-se a classe ListaAluno já totalmente alterada (módulo lista_aluno), a classe Aluno (módulo aluno) e o programa de teste (módulo teste_aluno).  Note-se que o módulo aluno não tem ficheiro de implementação e o módulo teste_aluno só tem ficheiro de implementação.  Anexa-se ainda o ficheiro de construção do programa (assume configuração de tcsh conforme sugerido no Capítulo 8 das folhas teóricas):

lista_aluno.H

#ifndef LISTA_ALUNO_H
#define LISTA_ALUNO_H

#include <cassert>
#include <iostream>

#include "aluno.H"

// Uma classe para representar listas de itens do tipo Item (actualmente Aluno):
class ListaAluno {
public:
    // Cria-se um sinónimo para simplificar a tarefa de criar listas com itens de outros tipos:
    typedef Aluno Item;

    // Declaração de uma classe embutida que serve para percorrer e manipular listas.
    class Iterador;

    // A classe de iteração tem acesso irrestrito às listas:
    friend Iterador;

    // Construtor da classe, cria uma lista vazia:
    ListaAluno();

    // Acrescenta item no início da lista:
    void poeInicio(Item const& item);
    // Acrescenta item no fim da lista:
    void poeFim(Item const& item);
    // Insere item imediatamente antes da posição indicada pelo iterador i, fazendo com que
    // o iterador continue a referenciar o mesmo item que antes da inserção:
    void insere(Iterador& i, Item const& item);
    // Idem, mas invalida iterador.
    void insere(Iterador const& i, Item const& item);

    // Retira o primeiro item da lista:
    void tiraPrimeiro();
    // Retira o último item da lista:
    void tiraUltimo();
    // Remove o item indicado pelo iterador i, ficando o iterador a referenciar o item logo
    // após o item removido:
    void remove(Iterador& i);
    // Idem, mas invalida iterador.
    void remove(Iterador const& i);

    // Remove todos os itens da lista:
    void limpa();
    // Transfere todos itens da lista l para a lista implícita:
    void transfere(ListaAluno& l);
    // Concatena a lista l com a lista implícita:
    ListaAluno& operator += (ListaAluno const& l);

    // Devolve o primeiro item:
    Item primeiroItem() const;
    Item& primeiroItem();
    // Devolve o último item:
    Item ultimoItem() const;
    Item& ultimoItem();

    // Devolve o comprimento da lista:
    int comprimento() const;
    // Indica se a lista está vazia:
    bool vazia() const;
    // Indica se a lista está cheia:
    bool cheia() const;

    // Devolve um iterador referenciando o primeiro item da lista:
    Iterador primeiro();
    // Devolve um iterador referenciando o último item da lista:
    Iterador ultimo();
    // Devolve um iterador referenciando o item fictício depois do último item da lista:
    Iterador fim();
    // Devolve um iterador referenciando o item fictício antes do primeiro item da lista:
    Iterador inicio();

    // Procura a primeira/última ocorrência de um item.  Devolve iterador referenciando o
    // item final/inicial se não existir:
    Iterador procuraPrimeiro(Item const& item);
    Iterador procuraUltimo(Item const& item);

private:
    // O número máximo de itens na lista:
    static int const limite = 100;

    /*
     A lista é representada por uma cadeia duplemente ligada de elos  guardados numa matriz
     de elos.  A matriz de elos contém elos que estão na cadeia duplamente ligada e que
     portanto contêm itens da lista e outros elos que estão livres, e portanto fazem parte de
     uma cadeia simplesmente ligada.  A cadeia duplamente ligada tem guardas (correspondentes
     aos itens fictícios) mas a cadeia simplesmente ligada não tem guardas:
    */
    struct Elo {
        Item item;
        Elo* anterior;
        Elo* seguinte;
    };

    // Matriz que guarda os elos das cadeias (incluindo as duas guardas da cadeia duplamente
    // ligada de itens):
    Elo elos[limite + 2];

    // Contador do número de itens na lista:
    int quantos;

    // Ponteiros para as guardas da cadeia duplamente ligada de itens:
    Elo* const inicial;
    Elo* const final;

    // Ponteiro para o primeiro elo da matriz livre (se não existir nenhum contém final.
    // É onde começa a cadeia simplesmente ligada dos elos livres:
    Elo* primeiro_livre;

    // Procedimentos auxiliares para inserir e remover um item da cadeia duplamente ligada dos itens:
    void poe(Elo* anterior, Elo* seguinte, Item const& item);
    void tira(Elo* elo);

    // Função que retira o primeiro elo da cadeia dos elos livres e devolve um ponteiro para ele.
    // É usada pelo procedimento poe() acima para obter um elo livre onde colocar o novo
    // item da lista:
    Elo* reserva();

    // Procedimento que coloca o elo cujo ponteiro é passado como argumento na cadeia dos elos
    // livres.  É usado pelo procedimento tira() quando tira um item da lista (ou melhor,
    // um elo da cadeia duplamente ligada):
    void liberta(Elo* elo);
};

// Uma classe para representar iteradores para itens de listas ListaAluno:
class ListaAluno::Iterador {
public:
    // Construtor da classe.  Associa o iterador com a lista lista e põe-no a referenciar o seu
    // primeiro item:
    explicit Iterador(ListaAluno& lista);

    // Incrementação prefixa de iteradores (avança para o próximo item):
    Iterador& operator ++ ();
    // Decrementação prefixa de iteradores (recua para o item anterior):
    Iterador& operator -- ();

    // Incrementação sufixa de iteradores (avança para o próximo item):
    Iterador operator ++ (int);
    // Decrementação sufixa de iteradores (recua para o item anterior):
    Iterador operator -- (int);

    // Devolve o item referenciado pelo iterador:
    Item& operator *() const;

    // Operadores de igualdade e diferença entre iteradores:
    bool operator == (Iterador const& i) const;
    bool operator != (Iterador const& i) const;

    // A classe ListaAluno tem acesso irrestrito a todos os membros da classe Iterador:
    friend ListaAluno;

private:
    // Construtor privado da classe.  Associa o iterador com a lista lista e põe-no a referenciar
    // o item no elo indicado:
    Iterador(ListaAluno& lista, Elo* elo);

    // Ponteiro para a lista a que o iterador está associado:
    ListaAluno* lista;
    // Ponteiro para o elo do item referenciado:
    Elo* elo;
};

// Declaração de funções e procedimentos não membro:

std::ostream& operator << (std::ostream& saida, ListaAluno& l);

// Inclusão do ficheiro auxiliar de implementação (definição de inline):
#include "lista_aluno_impl.H"

#endif // LISTA_ALUNO_H

// Definição das funções e procedimentos membro inline da classe ListaAluno:

inline ListaAluno::Elo* ListaAluno::reserva() {
    Elo* const elo = primeiro_livre;
    primeiro_livre = elo->seguinte;
    return elo;
}

inline void ListaAluno::liberta(Elo* elo) {
    elo->seguinte = primeiro_livre;
    primeiro_livre = elo;
}

// Coloca um novo elo, contendo o item item e retirado da cadeia de elos livres, na cadeia
// duplamente ligada.  O novo elo é colocado entre o elo anterior e o seguinte.
inline void ListaAluno::poe(Elo* anterior, Elo* seguinte, Item const& item) {
    ++quantos;

    Elo* const elo = reserva();

    elo->item = item;
    elo->anterior = anterior;
    elo->seguinte = seguinte;
    anterior->seguinte = elo;
    seguinte->anterior = elo;
}

// Os procedimentos poeInicio(), poeFim() e insere() são todos implementados à custa do
// procedimento membro privado poe():

inline void ListaAluno::poeInicio(Item const& item) {
    assert(!cheia());

    poe(inicial, inicial->seguinte, item);
}

inline void ListaAluno::poeFim(Item const& item) {
    assert(!cheia());

    poe(final->anterior, final, item);
}

/*
Note-se que o iterador é passado por referência apesar de não ser alterado.  Será que isto é inconsistente?  A verdade é que o iterador só não precisa de ser alterado devido à implementação particular do conceito de lista e iterador usado aqui.  Com outra implementação (ver resolução da Aula 2), o iterador não poderia ser constante.  A utilização de uma referência constante aqui levaria o utilizador da classe a crer que o procedimento insere() não altera nunca o iterador, o que só é verdade para esta implementação em particular.  Assim, alterar a implementação poderia obrigar a alterar a interface da classe (o cabeçalho do procedimento faz parte da interface da classe), com efeitos potencialmente desastrosos sobre o código do utilizador da classe.  Moral: a interface deve reflectir os conceitos e não a implementação em particular.
*/
inline void ListaAluno::insere(Iterador& iterador, Item const& item)
{
    assert(!cheia());

    // Só se pode inserir se o iterador estiver associado a esta lista!
    assert(this == iterador.lista);

    // Não se pode inserir se o iterador referir o item antes do primeiro:
    assert(iterador.elo != inicial);

    poe(iterador.elo->anterior, iterador.elo, item);
    // O iterador mantém-se válido!
}

inline void ListaAluno::insere(Iterador const& iterador, Item const& item)
{
    assert(!cheia());

    // Só se pode inserir se o iterador estiver associado a esta lista!
    assert(this == iterador.lista);

    // Não se pode inserir se o iterador referir o item antes do primeiro:
    assert(iterador.elo != inicial);

    poe(iterador.elo->anterior, iterador.elo, item);
}

// Retira o elo i da cadeia duplamente ligada, colocando-o na cadeia simplesmente ligada de elos livres:
inline void ListaAluno::tira(Elo* elo) {
    --quantos;

    elo->anterior->seguinte = elo->seguinte;
    elo->seguinte->anterior = elo->anterior;

    liberta(elo);
}

// Os procedimentos tiraPrimeiro(), tiraUltimo() e remove() são todos implementados
// à custa do procedimento membro privado tira():

inline void ListaAluno::tiraPrimeiro() {
    assert(!vazia());

    tira(inicial->seguinte);
}

inline void ListaAluno::tiraUltimo() {
    assert(!vazia());

    tira(final->anterior);
}

inline void ListaAluno::remove(Iterador& iterador)
{
    assert(iterador.elo != inicial && iterador.elo != final);

    // Só se pode inserir se o iterador estiver associado a esta lista!
    assert(this == iterador.lista);

    Elo* const elo = iterador.elo->seguinte;
    tira(iterador.elo);

    // Avançar iterador!
    iterador.elo = elo;
}

inline void ListaAluno::remove(Iterador const& iterador)
{
    assert(iterador.elo != inicial && iterador.elo != final);

    // Só se pode inserir se o iterador estiver associado a esta lista!
    assert(this == iterador.lista);

    tira(iterador.elo);
}

inline ListaAluno::Item ListaAluno::primeiroItem() const {
    assert(!vazia());

    return inicial->seguinte->item;
}

inline ListaAluno::Item& ListaAluno::primeiroItem() {
    assert(!vazia());

    return inicial->seguinte->item;
}

inline ListaAluno::Item ListaAluno::ultimoItem() const {
    assert(!vazia());

    return final->anterior->item;
}

inline ListaAluno::Item& ListaAluno::ultimoItem() {
    assert(!vazia());

    return final->anterior->item;
}

inline int ListaAluno::comprimento() const {
    return quantos;
}

inline bool ListaAluno::vazia() const {
    return comprimento() == 0;
}

inline bool ListaAluno::cheia() const {
    return comprimento() == limite;
}

inline ListaAluno::Iterador ListaAluno::primeiro() {
    return Iterador(*this);
}

inline ListaAluno::Iterador ListaAluno::ultimo() {
    return Iterador(*this, final->anterior);
}

inline ListaAluno::Iterador ListaAluno::inicio() {
    return Iterador(*this, inicial);
}

inline ListaAluno::Iterador ListaAluno::fim() {
    return Iterador(*this, final);
}

// Definição das funções e procedimentos membro inline da classe ListaAluno::Iterador:

inline ListaAluno::Iterador::Iterador(ListaAluno& l)
    : lista(&l), elo(l.inicial->seguinte) {
}

inline ListaAluno::Iterador::Iterador(ListaAluno& l, Elo* elo)
    : lista(&l), elo(elo) {
}

inline ListaAluno::Iterador& ListaAluno::Iterador::operator ++ () {
    assert(elo != lista->final);

    elo = elo->seguinte;

    return *this;
}

inline ListaAluno::Iterador& ListaAluno::Iterador::operator -- () {
    assert(elo != lista->inicial);

    elo = elo->anterior;

    return *this;
}

inline ListaAluno::Iterador ListaAluno::Iterador::operator ++ (int) {
    ListaAluno::Iterador resultado = *this;
    operator ++ ();
    return resultado;
}

inline ListaAluno::Iterador ListaAluno::Iterador::operator -- (int) {
    ListaAluno::Iterador resultado = *this;
    operator -- ();
    return resultado;
}

inline bool ListaAluno::Iterador::operator == (Iterador const& i) const {
    assert(lista == i.lista);

    return elo == i.elo;
}

inline bool ListaAluno::Iterador::operator != (Iterador const& i) const {
    assert(lista == i.lista);

    return elo != i.elo;
}

inline ListaAluno::Item& ListaAluno::Iterador::operator * () const {
    assert(elo != lista->inicial && elo != lista->final);

    return elo->item;
}

// Definição de funções e procedimentos não membro e inline:

#include "lista_aluno.H"

// Definição das funções e procedimentos membro não-inline da classe ListaAluno:

ListaAluno::ListaAluno()
    : quantos(0), inicial(elos + limite), final(elos + limite + 1),
      primeiro_livre(elos) {

    // Cria lista de itens vazia (itens fictícios):
    inicial->seguinte = final;
    final->anterior = inicial;

    // Cria lista de nós livres com todos os nós da matriz (excepto guardas):
    for(Elo* elo = elos; elo != elos + limite - 1; ++elo)
        elo->seguinte = elo + 1;
    // O elo limite - 1 não precisa de ter seguinte válido!  Porquê?
}

/*
Aqui podia-se resolver o problema de várias formas.  Com iteradores, por exemplo.  Ou chamando tiraPrimeiro() até a lista estar vazia.  A solução escolhida é da baixo nível, e é também mais eficiente...  Mas é a que exige maiores alterações se se mudar a implementação da lista...
*/
void ListaAluno::limpa()
{
    quantos = 0;

    // Passar ocupados a livres:
    for(Elo* elo = inicial->seguinte; elo != final; ) {
        Elo* seguinte = elo->seguinte;
        liberta(elo);
        elo = seguinte;
    }

    // A cadeia duplamente ligada tem de ficar vazia:
    inicial->seguinte = final;
    final->anterior = inicial;
}

void ListaAluno::transfere(ListaAluno& l)
{
    // O ciclo só funciona se l e *this não forem a mesma lista!  Se forem a mesma lista
    // transferir é... não fazer nada!
    if(this != &l) {
        // Haverá espaço?
        assert(limite - comprimento() >= l.comprimento());

        // A implementação escolhida não é a mais eficiente para a Aula 5!  Com memória
        // dinâmica isto poderia ser muito mais simples!
        for(; !l.vazia(); l.tiraPrimeiro())
            poeFim(l.primeiroItem());
    }
}

ListaAluno& ListaAluno::operator += (ListaAluno const& l)
{
    // Haverá espaço?
    assert(limite - comprimento() >= l.comprimento());

    if(this != &l)
        // Este ciclo só funciona se l e *this não forem a mesma lista!
        for(Elo* elo = l.inicial->seguinte; elo != l.final;
            elo = elo->seguinte)
            poeFim(elo->item);
    else {
        Elo* const ultimo = l.final->anterior;
        for(Elo* elo = l.inicial->seguinte; elo != ultimo->seguinte;
            elo = elo->seguinte)
            poeFim(elo->item);
    }

    return *this;
}

ListaAluno::Iterador ListaAluno::procuraPrimeiro(Item const& item)
{
    Iterador i = primeiro();
    while(i != fim() && *i != item)
        ++i;
    return i;
}

ListaAluno::Iterador ListaAluno::procuraUltimo(Item const& item)
{
    Iterador i = ultimo();
    while(i != inicio() && *i != item)
        --i;
    return i;
}

// Definição das funções e procedimentos membro não inline da classe ListaAluno::Iterador:

// Definição de funções e procedimentos não membro e não inline:

// Definição do operador << para escrita de listas num canal.  ListaAluno& deveria ser
// ListaAluno const&, mas isso implicaria a definição de uma classe de iterador para listas
// constantes:
std::ostream& operator << (std::ostream& saida, ListaAluno& l)
{
    saida << '(';
    for(ListaAluno::Iterador i = l.primeiro(); i != l.fim(); ++i) {
        saida << *i;
        if(i != l.ultimo())
            saida << ", ";
    }
    return saida << ')';
}

#ifndef ALUNO_H
#define ALUNO_H

#include <string>
#include <iostream>

class Aluno {
  public:
    Aluno(std::string const& nome = "", int const numero = 0);
    std::string nome() const;
    int numero() const;
  private:
    std::string nome_;
    int numero_;
};
 

// Declaração de funções e procedimentos não membro:

bool operator < (Aluno const& a, Aluno const& b);
bool operator > (Aluno const& a, Aluno const& b);
bool operator <= (Aluno const& a, Aluno const& b);
bool operator >= (Aluno const& a, Aluno const& b);
bool operator != (Aluno const& a, Aluno const& b);
bool operator == (Aluno const& a, Aluno const& b);

std::ostream& operator << (std::ostream& saida, Aluno const& aluno);

// Inclusão do ficheiro auxiliar de implementação (definição de funções e procedimentos inline):
#include "aluno_impl.H"

#endif // ALUNO_H

// Definição de funções e porcedimentos inline:

inline Aluno::Aluno(std::string const& nome, int const numero)
    : nome_(nome), numero_(numero) {
}

inline std::string Aluno::nome() const {
    return nome_;
}

inline int Aluno::numero() const {
    return numero_;
}

// Basta alterar o operador < que todos os outros se adaptam automaticamente:
inline bool operator < (Aluno const& a, Aluno const& b) {
    return a.numero() < b.numero();
}

inline bool operator > (Aluno const& a, Aluno const& b) {
    return b < a;
}

inline bool operator <= (Aluno const& a, Aluno const& b) {
    return !(a > b);
}

inline bool operator >= (Aluno const& a, Aluno const& b) {
    return !(a < b);
}

inline bool operator != (Aluno const& a, Aluno const& b) {
    return a < b || a > b;
}

inline bool operator == (Aluno const& a, Aluno const& b) {
    return !(a != b);
}

inline std::ostream& operator << (std::ostream& saida, Aluno const& aluno) {
    return saida << '(' << aluno.nome() << ", " << aluno.numero() << ')';
}

#include <iostream>
#include <string>

using namespace std;

#include "aluno.H"
#include "lista_aluno.H"

int main()
{
    ListaAluno alunos;
    for(int i = 0; i != /*20*/5; ++i) {
        cout << "Aluno? ";
        string nome;
        int numero;
        cin >> nome >> numero;
        Aluno aluno(nome, numero);
        ListaAluno::Iterador i = alunos.primeiro();
        while(i != alunos.fim() && *i < aluno)
            ++i;
        alunos.insere(i, aluno);
    }
    for(ListaAluno::Iterador i = alunos.primeiro(); i != alunos.fim(); ++i)
        cout << *i << endl;
}

teste_alunos: teste_alunos.o lista_aluno.o
lista_aluno.o: lista_aluno.H lista_aluno_impl.H
teste_alunos.o: lista_aluno.H lista_aluno_impl.H aluno.H aluno_impl.H

Exercícios propostos

1.  Escreva o seguinte programa e execute-o.  Interprete e comente o resultado.

int main()
{
    int* p1;
    int* p2;
    int i = 2;
    p1 = p2 = &i;
    *p1 = 3;
    cout << *p1 << " " << *p2 << " " << i << endl;
}

#include <iostream>
using namespace std;

void mostraMatriz(int const m[], int const n)
{
    for(int *p = m; p != m + n; ++p) {
        cout << *p;
        if(p != m + n - 1)
            cout << ' ';
    }
    cout << endl;
}

int main()
{
    int a = 1;
    int m[] = {1, 2, 3, 4, 5};
    int b = 2;

    mostraMatriz(m,5);
    cout << "Tamanho de um int: " << sizeof(int) << endl;
    cout << "a: " << a << endl;
    cout << "b: " << b << endl;

    cout << "&a:    " << &a << endl;
    cout << "&b:    " << &b << endl;
    cout << "&m[0]: " << m  << endl;

    m[5] = 10;
    m[6] = 20;

    cout << "a: " << a << endl;
    cout << "b: " << b << endl;
}