Aula 5

1  Resumo da matéria

1.1  Classes com memória dinâmica

A utilização de memória dinâmica permite resolver alguns problemas incómodos que surgiram no passado.  Recorda-se das pilhas de inteiros, definidas no semestre passado (Secção 6.4.2 das aulas teóricas de Programação I/Introdução à Programação)?  Repete-se aqui o código (com ligeiras adaptações):
#ifndef PILHA_H
#define PILHA_H

// Módulo das pilhas.  Só tem ficheiro de cabeçalho.

#include <cassert>

class PilhaInt {
  public:
    typedef int Item;
    PilhaInt();          // construtor da classe.
    void põe(Item item); // coloca item no topo da pilha.
    void tira();         // retira item do topo da pilha.
    Item topo() const;   // devolve item no topo da pilha.
    bool vazia() const;  // devolve true sse a pilha estiver vazia.
    bool cheia() const;  // devolve true sse a pilha estiver cheia.
    int tamanho() const; // devolve número de itens na pilha.
  private:
    static const int limite = 100;
    Item itens[limite];
    int quantos;
};

inline PilhaInt::PilhaInt() : quantos(0) {
}

inline int PilhaInt::tamanho() const {
    return quantos;
}

inline bool PilhaInt::vazia() const {
    return tamanho() == 0;
}

inline bool PilhaInt::cheia() const {
    return tamanho() == limite;
}

inline void PilhaInt::põe(Item item) {
    assert(!cheia());
    itens[quantos++] = item;
}

inline void PilhaInt::tira() {
    assert(!vazia());
    quantos--;
}

inline PilhaInt::Item PilhaInt::topo() const {
    assert(!vazia());
    return itens[tamanho() - 1];
}

#endif // PILHA_H

1.1.1  Construtores

Esta classe tem um problema grave, com já se viu antes: as instâncias têm todas o mesmo número máximo de itens.  Seria interessante que o utilizador pudesse especificar no construtor da classe qual o número máximo de itens nessa instância particular da pilha.  Isso permitiria escrever o seguinte código:
PilhaInt p1(10);  // uma pilha com no máximo 10 itens.
PilhaInt p2(100); // uma pilha com no máximo 100 itens.
Mas para o conseguir, não é possível usar matrizes de tamanho fixo.  É necessário usar matrizes dinâmicas.  Assim, pode-se começar por alterar o tipo da variável membro itens de matriz de Item para ponteiro para Item:
class PilhaInt {
  public:
    ...
  private:
    static const int limite = 100;
    Item* itens;
    int quantos;
};
Mas agora é necessário alterar o construtor da classe para passar a aceitar o tamanho limite da pilha como argumento e para criar uma matriz dinâmica com o tamanho requerido.  Mais, limite passa a ser uma variável membro, em vez de uma constante membro.  Assim, a definição da classe fica:
class PilhaInt {
 public:
    typedef int Item;
    PilhaInt(int lim);   // construtor da classe.
    void põe(Item item); // coloca item no topo da pilha.
    void tira();         // retira item do topo da pilha.
    Item topo() const;   // devolve item no topo da pilha.
    bool vazia() const;  // devolve true sse a pilha estiver vazia.
    bool cheia() const;  // devolve true sse a pilha estiver cheia.
    int tamanho() const; // devolve número de itens na pilha.
 private:
    int limite;
    Item* itens;
    int quantos;
};
e o construtor passa a ser
inline PilhaInt::PilhaInt(int lim) : limite(lim), quantos(0) {
    assert(limite > 0);
    itens = new Item[limite];
}
ficando todas as outras funções e procedimentos membro inalterados.

1.1.2  Destrutores

Que acontece quando é executado o seguinte ciclo?
#include "pilha.h"
...
for(int i = 0; i != 10000; i++) {
    PilhaInt p(1000);
    ... // operações com a pilha.
}
Em cada passo do ciclo é criada uma pilha com 1000 itens no máximo.  No fim do passo a pilha é destruída...  Será?  O que é destruído é o espaço ocupado pela instância da pilha em si (que consiste em duas variáveis inteiras, limite e quantos, e num ponteiro, itens).  A memória dinâmica reservado no construtor da classe nunca chega a ser libertada!  Isso significa que, dpois do ciclo, existem em memória (e inacessíveis) 10000 matrizes dinâmicas com 1000 inteiros cada uma.  Se cada inteiro ocupar 4 bytes, isso significa 40 Mbytes de memória perdida.

Como evitar o problema?  Se se recordar que as variáveis, ao serem destruídas, invocam o destrutor da respectiva classe, é claro que a solução é definir um destrutor para a classe PilhaInt que proceda à libertação da memória reservada.  Note-se, a propósito, que o C++ procede à invocação dos destrutores de cada variável membro implicitamente, exista ou não destrutor da classe que as contém.  Acontece, porém, que os ponteiros não são classes e portanto não têm destrutores.  Assim, a definição da classe passa a:

class PilhaInt {
 public:
    typedef int Item;
    PilhaInt(int lim);   // construtor da classe.
    ~PilhaInt();         // destrutor da classe.
    void põe(Item item); // coloca item no topo da pilha.
    void tira();         // retira item do topo da pilha.
    Item topo() const;   // devolve item no topo da pilha.
    bool vazia() const;  // devolve true sse a pilha estiver vazia.
    bool cheia() const;  // devolve true sse a pilha estiver cheia.
    int tamanho() const; // devolve número de itens na pilha.
 private:
    int limite;
    Item* itens;
    int quantos;
};
sendo o destrutor simplesmente
inline PilhaInt::~PilhaInt() {
    delete[] itens; // é uma matriz dinâmica, por isso delete[].
}

1.1.3  Pilhas de ponteiros

Não confundir memória dinâmica com ponteiros.  Suponha-se que a classe implementando o conceito de pilha era alterada para guardar ponteiros para inteiros passados do exterior, e não inteiros propriamente ditos.   Isso implicava apenas alterar a definição de Item para (e já agora o nome da classe):
typedef int* Item;
Não era necessário alterar mais nada.  Em particular seria muito má ideia libertar a memória associada a esses ponteiros no procedimento membro tira().  Por exemplo:
inline void PilhaPonteiroInt::tira() {
    assert(!vazia());
    delete itens[quantos - 1]; // péssima ideia!
    quantos--;
}
Porque é essa libertação má ideia?  Imagine-se a seguinte utilização:
PilhaPonteiroInt p(10);
int i;
p.põe(&i);
p.tira();
O que acontece ao tentar retirar o item da pilha?  O procedimento tenta libertar memória que não é dinâmica: o ponteiro guarda o endereço da variável i, que não é dinâmica!

1.1.4  Cópias

Regresse-se de novo às pilhas de inteiros.  O que acontece ao executar o seguinte código?
PilhaInt p1(10);
PilhaInt p2(100);
...
p2 = p1; // atribuição por cópia.
Isto é, o que acontece quando se atribui por cópia uma pilha a outra?  O operador de atribuição por cópia é fornecido automaticamente pelo C++ a todas as classes que não o definam explicitamente.  Este operador de atribuição por cópia gerado automaticamente simplesmente copia as variáveis membro uma a uma.

O mesmo se passa para o construtor por cópia, que também é fornecido automaticamente pela linguagem.  Por exemplo, o que resulta do seguinte código?

PilhaInt p1(10);
PilhaInt p2(p1); // ou p2 = p1, construtor por cópia.
Em ambos os casos o resultado é desastroso (mais ainda no primeiro).  Porquê?  Simplesmente porque a variável membro itens do instância p2 passa a conter o mesmo endereço que a variável membro itens da variável p1, o que significa que ambas contêm o endereço da mesma matriz dinâmica.  I.e., alterações numa das pilhas passam a afectar a outra e vice-versa.  Uma situação muito indesejável.

Em geral as classes devem ser implementadas usando semântica de valor.  Isto significa que variáveis diferentes devem ser totalmente independentes, podendo no entanto tomar o mesmo valor.  Por exemplo, depois de

int i = 5;
int j = i;
as duas variáveis continuam perfeitamente independentes embora possuam o mesmo valor.
PilhaInt p1(10);
PilhaInt p2(100);
...
p2 = p1; // atribuição por cópia.
se desejaria que as duas variáveis continuassem independentes, embora com o mesmo valor (que neste caso significa com o mesmo número de itens e com itens de valor idêntico).

É portanto necessário criar explicitamente o construtor por cópia e o operador de atribuição por cópia.

Construtor por cópia

O construtor por cópia é semelhante ao construtor já definido, mas tem um parâmetro que é uma referência constante para uma PilhaInt (no caso do construtor por cópia tem de ser usar uma passagem por referência, pois se se usasse uma passagem por valor o próprio construtor por cópia seria invocado recursivamente para copiar o valor do argumento para o parâmetro respectivo).  Este construtor simplesmente cria uma matriz dinâmica nova (com o mesmo tamanho que a pilha passada como argumento) e enche-a com cópias dos seus itens:
inline PilhaInt::PilhaInt(const PilhaInt& p)
    : limite(p.limite), quantos(p.quantos) {
    itens = new Item[limite];
    for(int i = 0; i != quantos; i++)
        itens[i] = p.itens[i];
}
naturalmente é necessário declarar o novo construtor na definição da classe:
class PilhaInt {
 public:
    PilhaInt(int lim);          // construtor da classe.
    PilhaInt(const PilhaInt& p); // construtor por cópia da classe.
    ....
};

Operador de atribuição por cópia

O caso do operador de atribuição por cópia é uma pouco mais complicado.  Primeiro, é necessário recordar que a pilha à qual é feita a atribuição já possuia ela própria uma matriz dinâmica, com endereço guardado na variável membro itens, matriz essa que, sem ter sido libertada, permanece na memória depois da atribuição, constituindo assim uma fuga de memória.  Assim, no caso da atribuição por cópia é necessário não só fazer a cópia, como no caso do construtor, mas também libertar a matriz dinâmica pré-existente.  Ou seja, é necessário definir a função como:
inline PilhaInt& PilhaInt::operator = (const PilhaInt& p) {
    limite = p.limite;
    quantos = p.quantos;
    delete[] itens;
    itens = new Item[limite];
    for(int i = 0; i != quantos; i++)
            itens[i] = p.itens[i];
    return *this;
}
Mas uma observação atenta do código revela que há um caso para o qual a libertação e subsequente reserva de memória é desnecessária: se ambas as pilhas tiverem o mesmo tamanho limite.  Assim, a função pode-se reescrever como:
inline PilhaInt& PilhaInt::operator = (const PilhaInt& p) {
    if(limite != p.limite) {
        limite = p.limite;
        delete[] itens;
        itens = new Item[limite];
    }
    quantos = p.quantos;
    for(int i = 0; i != quantos; i++)
        itens[i] = p.itens[i];
    return *this;
}
Incidentalmente esta última alteração corrigiu também um erro grave da versão original.  A versão original daria resultados dramáticos se o utilizador se lembrasse de escrever:
p1 = p1;
Tente perceber porquê executando a função passo a passo e lembrando-se que, neste caso particular, limite e p.limite são a mesma variável (a instância implícita *this e a referência p dizem respeito à mesma variável p1), e da mesma forma para as outra variáveis membro da classe.

Para resolver este problema é típico envolver o corpo do operador de atribuição por cópia num teste que verifica se a instância implícita e a referência p se referem à mesma instância.  Isso faz-se comparando os seus endereços, pois instâncias diferentes estão sempre em zonas de memória diferentes.  Ou seja, a versão definitiva da função passa a ser:

inline PilhaInt& PilhaInt::operator = (const PilhaInt& p) {
    if(this != &p) {
        if(limite != p.limite) {
            limite = p.limite;
            delete[] itens;
            itens = new Item[limite];
        }
        quantos = p.quantos;
        for(int i = 0; i != quantos; i++)
            itens[i] = p.itens[i];
    }
    return *this;
}
Estas técnicas são muito importantes e devem ser percebidas ao pormenor.

1.1.5  Versão completa das pilhas

#ifndef PILHA_H
#define PILHA_H

// Módulo das pilhas.  Só tem ficheiro de cabeçalho.

#include <cassert>

class PilhaInt {
 public:
    typedef int Item;
    PilhaInt(int lim);          // construtor da classe.
    ~PilhaInt();                // destrutor da classe.
    PilhaInt(const PilhaInt& p); // construtor por cópia da classe.
    PilhaInt& operator = (const PilhaInt& p); // atribuição por cópia.
    void põe(Item item);        // coloca item no topo da pilha.
    void tira();                // retira item do topo da pilha.
    Item topo() const;          // devolve item no topo da pilha.
    bool vazia() const;         // devolve true sse a pilha estiver vazia.
    bool cheia() const;         // devolve true sse a pilha estiver cheia.
    int tamanho() const;        // devolve número de itens na pilha.
 private:
    int limite;
    Item* itens;
    int quantos;
};

inline PilhaInt::PilhaInt(int lim) : limite(lim), quantos(0) {
    assert(limite > 0);
    itens = new Item[limite];
}

inline PilhaInt::PilhaInt(const PilhaInt& p)
    : limite(p.limite), quantos(p.quantos) {
    itens = new Item[limite];
    for(int i = 0; i != quantos; i++)
        itens[i] = p.itens[i];
}

inline PilhaInt& PilhaInt::operator = (const PilhaInt& p) {
    if(this != &p) {
        if(limite != p.limite) {
            limite = p.limite;
            delete[] itens;
            itens = new Item[limite];
        }
        quantos = p.quantos;
        for(int i = 0; i != quantos; i++)
            itens[i] = p.itens[i];
    }
    return *this;
}

inline PilhaInt::~PilhaInt() {
    delete[] itens;
}

inline int PilhaInt::tamanho() const {
    return quantos;
}

inline bool PilhaInt::vazia() const {
    return tamanho() == 0;
}

inline bool PilhaInt::cheia() const {
    return tamanho() == limite;
}

inline void PilhaInt::põe(Item item) {
    assert(!cheia());
    itens[quantos++] = item;
}

inline void PilhaInt::tira() {
    assert(!vazia());
    quantos--;
}

inline PilhaInt::Item PilhaInt::topo() const {
    assert(!vazia());
    return itens[tamanho() - 1];
}

#endif // PILHA_H

1.2  Introdução às excepções

Como lidar com erros?  Esta é uma pergunta muito importante em programação, e a que não é fácil responder duma forma taxativa.  Existem várias abordagens possíveis, das quais já se utilizaram:
  1. Os erros são assinalados devolvendo valores especiais (no caso das funções) ou fazendo os procedimentos devolverem um valor booleano indicando sucesso ou insucesso.
  2. Os erros conduzem à terminação imediata do programa com uma mensagem de erro (uma versão sofisticada é a utilização de asserções [assert]).
A primeira solução usava-se muito na biblioteca padrão da linguagem C (disponível na biblioteca padrão do C++ através dos ficheiros de cabeçalho começados por 'c', como cstdlib).  Tem a vantagem de ser flexível, pois permite ao utilizador (utilizador programador, bem entendido) lidar com os erros da forma que lhe parecer mais conveniente.  Mas, como normalmente verificar todos os possíveis erros leva a programas muito complexos ("cheios de ifs"), os programadores tendem a ignorar os valores devolvidos.  Na prática, portanto, esta é uma não solução.

A segunda solução é demasiado drástica.  É verdade que muitas vezes é preferível abortar o programa a continuar depois de um erro grave.  Mas esta solução não deixa qualquer possibilidade ao utilizador programador de lidar com o erro.

O C++ fornece um mecanismo que tem as vantagens de ambas as soluções: as excepções.  Ao ocorrer um erro diz-se que se "lança uma excepção" de uma dado tipo.  Se o utilizador programador nada tiver feito, o programa aborta com uma mensagem apropriada.  Se o utilizador programador tiver preparado o seu código para "capturar a excepção", o programa não aborda, sendo executado código específico para lidar com o erro.

(Note-se que não se discutiu acima o que é um erro.  Será um valor inválido introduzido pelo utilizador do programa um erro, sendo o programa interactivo?  Provavelmente não.  Mas será um erro violar as pré-condições de uma função ou procedimento, passando argumentos inválidos?  Provavelmente sim.)

1.2.1  Definindo excepções

As excepções são instências de classes como outras quaisquer.  Por exemplo, uma excepção para assinalar que se tentou retirar um item duma pinha vazia ou aceder ao valor do item no topo de uma pilha vazia poderia ser simplesmente uma instância da classe:
class PilhaIntVazia {};
Ou, usando classes embutidas:
class PilhaInt {
  public:
    class Vazia {};
    ...
};
Como se utilizam as excepções?

1.2.2  Lançando excepções

Suponha-se que se pretende assinalar um erro na função tira() da classe PilhaInt quando a pilha estiver vazia.  Pode-se definir a função como se segue:
inline void PilhaInt::tira() {
    if(vazia())
        throw Vazia();
    quantos--;
}


Ou seja, se a lista estiver vazia é lançada uma excepção que é uma instância da classe PilhaInt::Vazia.  Note-se bem: uma instância da classe, e não uma classe, daí a necessidade dos parênteses após o nome da classe, que provocam a invocação do construtor da classe e portanto a criação duma nova instância da classe.

Muitas vezes os construtores das classes de excepções têm parâmetros que identificam melhor o erro.

1.2.3  Capturando excepções

Suponha-se agora o seguinte programa usando a classe PilhaInt:
#include "pilha.h"

int main() {
    PilhaInt p(10); // nova pilha vazia.
    p.tira();
}

Tentar retirar um item da pilha vazia leva ao lançamento da excepção.  Como o utilizador nada fez para lidar com essa excepção, o programa aborta.

Se o utilizador (programador de main()) quisesse capturar a excepção, deveria envolver o código onde o erro pode ocorrer num "bloco  de tentativa", dizendo explicitamente o que fazer quando uma excepção dum determinado tipo fosse capturado*:

#include <iostream>

using namespace std;

#include "pilha.h"

int main() {
    PilhaInt p(10); // nova pilha vazia.
    try {
        p.tira();
    } catch(PilhaInt::Vazia) {
        cerr << "A pilha estava vazia!" << endl;
    }
}

Outro exemplo seria, por exemplo, a verificação do tamanho limite da pilha no seu construtor.  Pode-se definir uma classe para a excepção como se segue:
class PilhaInt {
  public:
    ...
    class LimiteInválido {
      public:
        int limite;
        LimiteInválido(int l) : limite(l) {}
    };
    ...
};
Nesse caso o construtor seria:
inline PilhaInt::PilhaInt(int lim) : limite(lim), quantos(0) {
    if(limite <= 0)
        throw LimiteInválido(limite);
    itens = new Item[limite];
}
e a sua captura poderia ser feita como se segue:
#include <iostream>

using namespace std;

#include "pilha.h"

int main() {
    try {
        PilhaInt p(-1);
    } catch(PilhaInt::LimiteInválido e) {
        cerr << "Limite " << e.limite << " inválido" << endl;
    }
    try {
        p.tira();
    } catch(PilhaInt::Vazia) {
        cerr << "A pilha estava vazia!" << endl;
    }
}

Note-se que neste caso se passaram argumentos ao construtor da excepção e que portanto o código que lida com erro recebe mais informação, nomeadamente qual o valor do limite que conduziu à excepção PilhaInt::LimiteInválido.

É de notar que o mesmo bloco de tentativa pode capturar tipos de excepção diferentes.  Por exemplo:

#include <iostream>

using namespace std;

#include "pilha.h"

int main() {
    try {
        PilhaInt p(-1);
        p.tira();
    } catch(PilhaInt::LimiteInválido e) {
        cerr << "Limite " << e.limite << " inválido" << endl;
    } catch(PilhaInt::Vazia) {
        cerr << "A pilha estava vazia!" << endl;
    }
}

Finalmente, todo o corpo duma função pode consistir num grande bloco de tentativa.  Por exemplo:
#include <iostream>

using namespace std;

#include "pilha.h"

int main()
    try {
        PilhaInt p(-1);
        p.tira();
    } catch(PilhaInt::LimiteInválido e) {
        cerr << "Limite " << e.limite << " inválido" << endl;
    } catch(PilhaInt::Vazia) {
        cerr << "A pilha estava vazia!" << endl;
    }

Como é óbvio, um bloco de tentativa pode constar em qualquer função (e não apenas em main()).
* Para capturar qualquer tipo de excepção, usar catch(...).

1.2.4  Módulo das pilhas com excepções

#ifndef PILHA_H
#define PILHA_H

// Módulo das pilhas.  Só tem ficheiro de cabeçalho.

class PilhaInt {
 public:
    typedef int Item;
    PilhaInt(int lim);          // construtor da classe.
    PilhaInt(const PilhaInt& p); // construtor por cópia da classe.
    PilhaInt& operator = (const PilhaInt& p); // atribuição por cópia.
    ~PilhaInt();                // destrutor da classe.
    void põe(Item item);        // coloca item no topo da pilha.
    void tira();                // retira item do topo da pilha.
    Item topo() const;          // devolve item no topo da pilha.
    bool vazia() const;         // devolve true sse a pilha estiver vazia.
    bool cheia() const;         // devolve true sse a pilha estiver cheia.
    int tamanho() const;        // devolve número de itens na pilha.
    // Excepções:
    class Vazia {};
    class Cheia {};
    class LimiteInválido {
      public:
        int limite;
        LimiteInválido(int l) : limite(l) {}
    };
 private:
    int limite;
    Item* itens;
    int quantos;
};

inline PilhaInt::PilhaInt(int lim) : limite(lim), quantos(0) {
    if(limite <= 0)
        throw LimiteInválido(limite);
    itens = new Item[limite];
}

inline PilhaInt::PilhaInt(const PilhaInt& p)
    : limite(p.limite), quantos(p.quantos) {
    itens = new Item[limite];
    for(int i = 0; i != quantos; i++)
        itens[i] = p.itens[i];
}

inline PilhaInt& PilhaInt::operator = (const PilhaInt& p) {
    if(this != &p) {
        if(limite != p.limite) {
            limite = p.limite;
            delete[] itens;
            itens = new Item[limite];
        }
        quantos = p.quantos;
        for(int i = 0; i != quantos; i++)
            itens[i] = p.itens[i];
    }
    return *this;
}

inline PilhaInt::~PilhaInt() {
    delete[] itens;
}

inline int PilhaInt::tamanho() const {
    return quantos;
}

inline bool PilhaInt::vazia() const {
    return tamanho() == 0;
}

inline bool PilhaInt::cheia() const {
    return tamanho() == limite;
}

inline void PilhaInt::poe(Item item) {
    if(cheia())
        throw Cheia();
    itens[quantos++] = item;
}

inline void PilhaInt::tira() {
    if(vazia())
        throw Vazia();
    quantos--;
}

inline PilhaInt::Item PilhaInt::topo() const {
    if(vazia())
        throw Vazia();
    return itens[tamanho() - 1];
}

#endif // PILHA_H

1.3  Revisitando as listas

Viu-se na Secção 1.1 como se podiam implementar as pilhas recorrendo a matrizes dinâmicas.  Mas haverá melhor forma de usar memória dinâmica para implementar as pilhas?  Certamente.  Usando listas ligadas, por exemplo, o que permitiria que as pilhas não tivessem qualquer dimensão pré-estabelecida, podendo crescer à medida das necessidades (tendo como única limitação a memória disponível).

Mas regresse-se às listas, que se definiram originalmente na Aula 2.  A implementação original fazia uso de matrizes não dinâmicas e portanto com tamanho fixo.  Poder-se-ia resolver o problema do tamanho fixo através da utilização de matrizes dinâmicas, mas isso não resolveria outros tipos de problemas.  Por exemplo, listas implementadas com matrizes são sempre muito ineficientes na inserção e remoção de itens no início e a meio da lista.  Mas esse é um problema que deixará de existir se se implementar o conceito de lista recorrendo às listas ligadas definidas na aula anterior.

As secções seguintes mostram uma reimplementação do módulo das listas recorrendo às listas ligadas.  Esta reimplementação não altera a interface da classe, pelo que o utilizador da classe não se aperceberá da diferença (excepto quanto à ausência se limites para o número de elementos na lista [... ou quase ausência...] e quanto a um melhor desempenho para inserções e remoções sem ser no final da lista).

1.3.1  Ficheiro de interface (lista.h)

// lista.h: ficheiro de interface do módulo das listas.
#ifndef LISTA_H
#define LISTA_H

#include <cassert>
#include <iostream>

#include "lista_ligada.h"

/*
   Uma classe para representar listas de itens do tipo 'Item' (actualmente
   int).  Esta classe fornece os serviços mais simples de uma lista e
   iteradores associados.

   A implementação desta lista difere da versão original.  A versão original
   usava uma matriz interna, de tamanho fixo, para guardar os itens.  A nova
   versão usa o conceito de lista duplamente ligada, em que os itens são
   guardados em nós que têm referências (ponteiros) para os itens anterior e
   seguinte na lista.  Estes nós são guardados em memória dinâmica.  A
   implementação faz ainda uso de duas guardas: uma inicial e outra final.  A
   vantagem da utilização de guardas é, por um lado, a simplicidade acrescida
   que se consegue para todas as operações de inserção e remoção, pois todas
   essas operações passam a ser tratadas duma uniformemente, sem quaisquer
   casos particulares nos extremos da lista.  Por outro lado estas guardas
   correspondem a itens fictícios extremos referenciáveis pelos iteradores, o
   que simplifica a implementação de ciclos para percorrer listas.

   A lista ligada é implementada usando o módulo lista_ligada.
**/

class ListaInt {
public:
    // Cria-se um sinónimo de ListaLigada::No::item, chamado Item, para
    // simplificar a tarefa de criar listas com itens de outros tipos:
    typedef ListaLigada::No::Item Item;

    /*
      Declaração de duas classes embutidas públicas que servem para
      percorrer e manipular listas.  A primeira serve para percorrer
      listas que se podem alterar.  A segunda para percorrer listas
      que não se podem alterar, i.e., listas constantes.
    **/
    class Iterador;
    class IteradorConstante;

    // Ambas as classes de iteração têm acesso completo às listas,
    // pelo que são amigas:
    friend class Iterador;
    friend class IteradorConstante;

    // Construtor por omissão da classe, cria uma lista vazia:
    ListaInt();
    /*
      Construtor por cópia, cria uma lista idêntica à passada como
       argumento.  É muito importante criar este tipo de construtor, em
      classes que recorrem a memória dinâmica, pois caso contrário o
      compilador fornece um automaticamente e que se limita a copiar
      as variáveis membro uma a uma, incluindo os ponteiros.  O
      resultado prático de tal construtor seria uma nova lista que
      partilharia os nós da lista copiada!  Isso implicava que as
      alterações numa lista teriam repercussões na outra.  A definição
      explícita deste construtor evita o problema.  Ver comentário na
      definição deste construtor (em lista.cpp).
    **/
    ListaInt(const ListaInt& l);
    /*
      Destrutor.  De igual modo, é fundamental definir um destrutor
      para as classes para que a memória dinâmica associada aos nós da
      lista seja devolvida à memória livre.
    **/
    ListaInt::~ListaInt();

    /*
      Atribuição por cópia.  Este tipo de atribuição também é
      definido automaticamente pelo compilador, a não ser que o
      programador o faça.  É importante fazê-lo sempre que a classe
      usar memória dinâmica, pelas mesmas razões que se define o
      contrutor por cópia.
    **/
    ListaInt& operator = (const ListaInt& l);

    // Acrescenta item no início da lista:
    void poeInicio(const Item& item);
    // Retira o primeiro item da lista:
    void tiraPrimeiro();
    // Acrescenta item no fim da lista:
    void poeFim(const Item& item);
    // Retira o último item da lista:
    void tiraUltimo();
    // Insere item imediatamente antes da posição indicada pelo iterador
    // i, fazendo com que o iterador continue a referenciar o mesmo item:
    void insere(Iterador& i, const Item& item);
    // Remove o item indicado pelo iterador i, ficando o iterador a
    // referenciar o item logo após o item removido:
    void remove(Iterador& i);
    // Devolve o comprimento da lista:
    int comprimento() const;

    // Remove todos os itens da lista:
    void limpa();

    // Acrescenta os itens da lista passada como argumento:
    ListaInt& operator += (const ListaInt& l);

    // Transfere itens da lista passada como argumento para a lista:
    void transfere(ListaInt& l);

    // 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();
    // Devolve iterador referenciando o primeiro item da lista igual ao item
    // dado ou o item fictício final se não existir:
    Iterador procura(const Item& item);
    // Devolve iterador referenciando o último item da lista igual ao item
    // dado ou o item fictício inicial se não existir:
    Iterador procuraUltimo(const Item& item);

    // Idem para iteradores constantes.  Estas versões são invocadas
    // quando a lista em causa (a instância implícita) for const:
    IteradorConstante primeiro() const;
    IteradorConstante ultimo() const;
    IteradorConstante fim() const;
    IteradorConstante inicio() const;
    IteradorConstante procura(const Item& item) const;
    IteradorConstante procuraUltimo(const Item& item) const;

private:
    // Ponteiros para os nós inicial e final, que são "fictícios", ou
    // seja, usados como guardas:
    ListaLigada::No *inicial;
    ListaLigada::No *final;

    // Contador do número de itens (e nós) na lista:
    int quantos;
};
 

// Uma classe para representar iteradores para itens de listas ListaInt:
class ListaInt::Iterador {
    // Cada iterador guarda uma referência para lista a que está associado:
    ListaInt& lista;
    // Guarda também um ponteiro para o nó contendo o item referenciado:
    ListaLigada::No *no;
    // Define-se um construtor privado (acessível só por funções
    // membro da classe ListaInt) que indica logo o nó referenciado
    // pelo iterador.  Compare-se com o construtor público.
    Iterador(ListaInt& lista, ListaLigada::No* no);

public:
    // Construtor público da classe.  Associa o iterador com a lista
    // lista e põe-no a referenciar o seu primeiro item:
    explicit Iterador(ListaInt& 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 -- ();
    // Devolve o item referenciado pelo iterador:
    Item& item();
    // O operador de comparação entre itens tem acesso aos membros privados da
    // classe Iterador:
    friend bool operator == (const Iterador& i1, const Iterador& i2);
    // A classe ListaInt tem acesso a todos os membros da classe Iterador:
    friend class ListaInt;
    friend class ListaInt::IteradorConstante;
};
 

/*
 Definição da classe para iteradores constantes, i.e., iteradores
 através dos quais não é possível alterar os itens da lista associada:
**/
class ListaInt::IteradorConstante {
    const ListaInt& lista;
    const ListaLigada::No *no;
    IteradorConstante(const ListaInt& lista, const ListaLigada::No* no);
public:
    explicit IteradorConstante(const ListaInt&);
    // Há conversão implícita de iteradores não constantes para constantes:
    IteradorConstante(const ListaInt::Iterador&);
    IteradorConstante& operator ++ ();
    IteradorConstante& operator -- ();
    /*
       Note-se que, neste caso, não se devolve uma referência para o
       item, ao contrário do que acontece com os iteradores normais,
       pois isso permitiria alterá-lo, o que deve ser impossível
       através dum IteradorConstante:
    **/
    Item item();
    friend bool operator == (const IteradorConstante& i1,
                             const IteradorConstante& i2);
    friend class ListaInt;
};
 

/*
  Definição das funções e procedimentos membro inline da classe ListaInt.

  Note-se que, como se usam as ferramentas do módulo das listas ligada, os
  procedimentos membro (públicos) de inserção, remoção, cópia e transferência
  de itens ficam muito simplificados.  Daí que sejam definidos inline.
**/

// O construtor por omissão cria uma lista vazia.  Mas uma lista ligada com
// guardas tem guardas mesmo quando vazia!
inline ListaInt::ListaInt() : quantos(0) {
    // A completar!
}

// O construtor por cópia tem de criar uma cópia exacta da lista passada como
// argumento (note-se a inicialização de quantos!):
inline ListaInt::ListaInt(const ListaInt& l) : quantos(l.quantos) {
    // A completar!
}

/*
 A atribuição por cópia tem um papel mais complicado.  Se a lista passada
 como argumento for a mesma lista que a instância implícita, isso significa
 que o utilizador escreveu algo como:

     ListaInt l1;
     ...
     l1 = l1;

 Portanto, há que verificar se foi esse o caso.  Se foi, não é necessário
 fazer nada.  Se não foi, é necessário: (a) limpar a lista, (b) copiar todos
 os itens de l.
**/
inline ListaInt& ListaInt::operator = (const ListaInt& l) {
    // A completar!
}

// O destrutor deve devolver todos os nós na lista à memória livre:
inline ListaInt::~ListaInt() {
    ListaLigada::finaliza(inicial, final);
}

inline void ListaInt::limpa() {
    ListaLigada::esvazia(inicial, final);
    quantos = 0;
}
 

inline ListaInt& ListaInt::operator += (const ListaInt& l) {
    // Lista::concatena não tem problema mesmo que l seja a instância
    // implícita, i.e.:
    //     ListaInt l;
    //     ...
    //     l += l;
    // não traz problemas.

    // Copia lista l:
    ListaLigada::concatena(inicial, final, l.inicial->seguinte, l.final);

    // Actualiza quantos:
    quantos += l.quantos;

    return *this;
}

inline void ListaInt::transfere(ListaInt& l) {
    // A completar!
}

inline void ListaInt::poeInicio(const Item& item) {
    ListaLigada::insere(inicial, final, item, inicial->seguinte);
    quantos++;
}

inline void ListaInt::poeFim(const Item& item) {
    // A completar!
}

inline void ListaInt::insere(Iterador& iterador, const Item& item) {
    // A completar!
}

inline void ListaInt::tiraPrimeiro() {
    // Só se pode retirar se existir algum item:
    assert(comprimento() != 0);
    ListaLigada::remove(inicial, final, inicial->seguinte);
    quantos--;
}

inline void ListaInt::tiraUltimo() {
    assert(comprimento() != 0);
    ListaLigada::remove(inicial, final, final->anterior);
    quantos--;
}

inline void ListaInt::remove(Iterador& iterador) {
    // A completar!
}

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

inline ListaInt::Iterador ListaInt::primeiro() {
    // Cria-se um iterador para esta lista, que referencia logo o primeiro
    // item da lista (ver construtor privado de ListaInt::Iterador):
    return Iterador(*this, inicial->seguinte);
}

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

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

inline ListaInt::Iterador ListaInt::fim() {
    // A completar!
}

inline ListaInt::Iterador ListaInt::procura(const Item& item) {
    // A completar!
}

inline ListaInt::Iterador ListaInt::procuraUltimo(const Item& item) {
    return Iterador(*this,
                    ListaLigada::procuraUltimo(inicial, final, item));
}

inline ListaInt::IteradorConstante ListaInt::primeiro() const {
    return IteradorConstante(*this, inicial->seguinte);
}

inline ListaInt::IteradorConstante ListaInt::ultimo() const {
    return IteradorConstante(*this, final->anterior);
}

inline ListaInt::IteradorConstante ListaInt::inicio() const {
    return IteradorConstante(*this, inicial);
}

inline ListaInt::IteradorConstante ListaInt::fim() const {
    // A completar!
}

inline ListaInt::IteradorConstante ListaInt::procura(const Item& item) const {
    return IteradorConstante(*this,
                             ListaLigada::procura(inicial, final, item));
}

inline ListaInt::IteradorConstante
ListaInt::procuraUltimo(const Item& item) const {
    return IteradorConstante(*this,
                             ListaLigada::procuraUltimo(inicial, final,
                                                        item));
}
 

// Definição das funções e procedimentos membro inline das classes
// ListaInt::Iterador e ListaInt::IteradorConstante:

// O construtor público coloca o iterador referenciando o primeiro
// item da lista:
inline ListaInt::Iterador::Iterador(ListaInt& l)
    : lista(l), no(l.inicial->seguinte) {}

// O construtor privado coloca o iterador referenciando um item
// arbitrário da lista:
inline ListaInt::Iterador::Iterador(ListaInt& l, ListaLigada::No* n)
    : lista(l), no(n) {}

inline ListaInt::Iterador& ListaInt::Iterador::operator ++ () {
    // A completar!
}

inline ListaInt::Iterador& ListaInt::Iterador::operator -- () {
    // A completar!
}

inline bool operator == (const ListaInt::Iterador& i1,
                         const ListaInt::Iterador& i2) {
    return i1.no == i2.no;      // porque não é necessário comparar as listas?
}

inline bool operator != (const ListaInt::Iterador& i1,
                         const ListaInt::Iterador& i2) {
    return !(i1 == i2);
}

inline ListaInt::Item& ListaInt::Iterador::item() {
    // O item só existe se o iterador não se referir a um iterador fictício:
    assert(no != lista.inicial && no != lista.final);
    return no->item;
}

inline ListaInt::IteradorConstante::IteradorConstante(const ListaInt& l)
    : lista(l), no(l.inicial->seguinte) {}

inline
ListaInt::IteradorConstante::IteradorConstante(const ListaInt::Iterador& i)
    // A completar!

inline
ListaInt::IteradorConstante::IteradorConstante(const ListaInt& l,
                                               const ListaLigada::No* n)
    : lista(l), no(n) {}

inline
ListaInt::IteradorConstante& ListaInt::IteradorConstante::operator ++ ()
{
    assert(no != lista.final);
    no = no->seguinte;
    return *this;
}

inline ListaInt::IteradorConstante
operator ++ (ListaInt::IteradorConstante& iterador, int) {
    ListaInt::IteradorConstante resultado = iterador;
    ++iterador;
    return resultado;
}

inline ListaInt::IteradorConstante&
ListaInt::IteradorConstante::operator -- () {
    // A completar!
}

inline ListaInt::IteradorConstante
operator -- (ListaInt::IteradorConstante& iterador, int) {
    // A completar!
}

inline bool operator == (const ListaInt::IteradorConstante& i1,
                         const ListaInt::IteradorConstante& i2) {
    return i1.no == i2.no;
}

inline bool operator != (const ListaInt::IteradorConstante& i1,
                  const ListaInt::IteradorConstante& i2) {
    return !(i1 == i2);
}

inline ListaInt::Item ListaInt::IteradorConstante::item() {
    assert(no != lista.inicial && no != lista.final);
    return no->item;
}
 

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

// Operador para soma de duas listas:
inline ListaInt operator + (ListaInt l1, const ListaInt& l2) {
    // A completar!
}

// O operador de incrementação sufixa não é membro da classe ListaInt:
inline ListaInt::Iterador operator ++ (ListaInt::Iterador& iterador, int) {
    ListaInt::Iterador resultado = iterador;
    ++iterador;
    return resultado;
}

// O operador de decrementação prefixa também não é membro da classe
// ListaInt:
inline ListaInt::Iterador operator -- (ListaInt::Iterador& iterador, int) {
    ListaInt::Iterador resultado = iterador;
    --iterador;
    return resultado;
}
 

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

// Operador << para escrita de ListaInt num canal:
std::ostream& operator << (std::ostream& saida, const ListaInt& l);

#endif // LISTA_H

1.3.2  Ficheiro de implementação (lista.cpp)

// lista.cpp: ficheiro de implementação do módulo das listas.
#include "lista.h"
 

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

std::ostream& operator << (std::ostream& saida, const ListaInt& l) {
    // A completar!
}

1.3.3  Um programa de teste

#include <iostream>
#include "lista.h"

int main()
{
    ListaInt l;

    cout << "Preenche com 1 2 3 4." << endl;
    l.poeFim(1);
    l.poeFim(2);
    l.poeFim(3);
    l.poeFim(4);

    for(ListaInt::Iterador i = l.primeiro();
        i != l.fim(); ++i)
        std::cout << i.item() << ' ';
        std::cout << std::endl;

    cout << "Por ordem inversa:" << endl;
    for(ListaInt::Iterador i = l.ultimo();
        i != l.inicio();
        --i)
        std::cout << i.item() << ' ';
    std::cout << std::endl;

    cout << "Por ordem:" << endl;
    std::cout << l << std::endl;

    cout << "Insere 10 antes do 3:" << endl;
    ListaInt::Iterador i = l.primeiro();
    i++;
    ++i;
    l.insere(i, 10);

    std::cout << l << std::endl;

    cout << "Remove 3:" << endl;
    l.remove(i);

    std::cout << l << std::endl;

    ListaInt ll = l;

    cout << "Cópia da lista:" << endl;
    std::cout << ll << std::endl;
 

    cout << "Sem o primeiro (a cópia):" << endl;
    ll.tiraPrimeiro();

    std::cout << ll << std::endl;

    cout << "Copia para o original:" << endl;
    l = ll;

    std::cout << l << std::endl;

    cout << "Tira primeiro:" << endl;
    l.tiraPrimeiro();
    std::cout << l << std::endl;

    cout << "Tira último:" << endl;
    l.tiraUltimo();
    std::cout << l << std::endl;

    cout << "Tira primeiro:" << endl;
    l.tiraPrimeiro();
    std::cout << l << std::endl;

    cout << "Comprimento: " << l.comprimento() << endl;

    cout << "Tira último:" << endl;
    l.tiraUltimo();
    std::cout << l << std::endl;

    cout << "Tira último:" << endl;
    l.tiraUltimo();
}

1.4  Leitura recomendada

Recomenda-se a leitura do Capítulo 5 de [2].

2  Exercícios

1.  Complete o módulo da classe ListaInt.  Escreva um programa de teste (ou altere o fornecido acima) para testar o módulo.  Experimente casos patológicos (mas que cumpram as pré-condições) tais como concatenar uma lista com ela própria, etc.

2.  Retire todas as asserções (assert) e substitua-as pelo mecanismo de lançamento excepções.  Experimente-as escrevendo um programa com erros e capturando as respectivas excepções.

3.  A utilização de uma referência para a lista como membro dos iteradores torna o seu uso muito restrito (por exemplo, não é possível atribuir um iterador a outro).  O problema pode ser resolvido se em vez de uma referência se usar um ponteiro.  Proceda às alterações necessárias.  O seguinte código deve deixar de produzir um erro de compilação:

ListaInt::Iterador i = l.primeiro();
ListaInt::Iterador j = l.ultimo();
j = i; // passa a funcionar!

3  Referências

[1]  Bjarne Stroustrup, "The C++ Programming Language", 3ª edição, Addison-Wesley, Reading, Massachusetts, 1997. *

[2]  Michael Main e Walter Savitch, "Data Structures and Other Objects Using C++", Addison-Wesley, Reading Massachusetts, 1997. #

* Existe um exemplar na biblioteca do ISCTE.

# Existem 10 exemplares na biblioteca do ISCTE.