Exercícios

1.a)  O construtor da classe tem um problema.  Se a construção da guarda final falhar é lançada uma excepção bad_alloc e a guarda inicial nunca é destruída!  Corrija o problema capturando a excepção e relançando-a (para relançar uma excepção basta escrever throw;).  Talvez seja necessário passar os ponteiros para as guardas a variáveis (neste momento são constantes).

1.b)  A construção de uma lista à custa de outra usando o construtor por cópia fornecido automaticamente pela linguagem tem os mesmos problemas graves que para a classe PilhaInt discutida acima.  Em particular, a lista construída partilha os seus elos dinâmicos com a que lhe serve de modelo, o que é claramente incorrecto.  Implemente um construtor por cópia que resolva o problema.  Garanta que todas as variáveis dinâmicas são destruídas se a memória faltar a meio da construção.

1.c)  A atribuição entre duas listas é impossível se existirem as duas constantes membro de instância da solução original: inicial e final.  Mesmo que se passem essas constantes a variáveis, a atribuição tem os mesmos problemas da construção por cópia.  Implemente um operador de atribuição por cópia que resolva o problema.  Garanta que os elos dinâmicos dos itens na lista original são destruídos.  Garanta que a lista fica num estado aceitável mesmo que a cópia falhe a meio.

R:
A resolução apresentada vai um pouco mais longe do que se pedia na alínea 1.a) no que diz respeito ao comportamento face a excepções.  Em todas as operações que poderiam lançar alguma excepção (nomeadamente o operador new pode lançar a excepção bad_alloc), garantiu-se que a lista fica num estado apropriado, nomeamente que não sofre qualquer alteração.  Note-se que, se os itens da lista forem não dos tipos double ou int ou de outro tipo básico do C++, mas de uma classe cujos métodos possam lançar excepções, a lista tem de continuar a comportar-se bem.  Assim, é necessário tentar antecipar lançamentos de excepções pelos itens da listas (e.g., durante uma construção ou atribuição por cópia, etc.) e usar blocos de tentativa que capturem qualquer excepção (catch(...)).

lista_double.H

#ifndef LISTA_DOUBLE_H
#define LISTA_DOUBLE_H

#include <iostream>

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

    // Declaração de uma classe embutida que serve para percorrer e manipular listas.
    class Iterador;
    // Idem, mas garante que nem os itens nem a lista são alterados:
    class IteradorConstante;

    // As classes de iteração têm acesso irrestrito às listas:
    friend Iterador;
    friend IteradorConstante;

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

    // Construtor por cópia:
    ListaDouble(ListaDouble const& l);

    // Destrutor da classe:
    ~ListaDouble();

    // Operador de atribuição por cópia:
    ListaDouble& operator = (ListaDouble const& l);

    // 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 os itens da lista l para a lista implícita:
    void transfere(ListaDouble& l);
    // Troca todos os itens da lista l com os da lista implícita:
    void troca(ListaDouble& l);
    // Concatena a lista l com a lista implícita:
    ListaDouble& operator += (ListaDouble 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();
    IteradorConstante primeiro() const;
    // Devolve um iterador referenciando o último item da lista:
    Iterador ultimo();
    IteradorConstante ultimo() const;
    // Devolve um iterador referenciando o item fictício depois do último item da lista:
    Iterador fim();
    IteradorConstante fim() const;
    // Devolve um iterador referenciando o item fictício antes do primeiro item da lista:
    Iterador inicio();
    IteradorConstante inicio() const;

    // 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);
    IteradorConstante procuraPrimeiro(Item const& item) const;
    Iterador procuraUltimo(Item const& item);
    IteradorConstante procuraUltimo(Item const& item) const;

private:
    /* A lista é representada por uma cadeia duplemente ligada de elos guardados na memória livre.  A
      cadeia duplamente ligada tem guardas (correspondentes aos itens fictícios): */
    struct Elo {
        Item item;
        Elo* anterior;
        Elo* seguinte;
        Elo(Elo* anterior = 0, Elo* seguinte = 0,
            Item const& item = Item());
    };

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

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

    // 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);
};

// Uma classe para representar iteradores para itens de listas ListaDouble:
class ListaDouble::Iterador {
public:
    // Construtor da classe.  Associa o iterador com a lista lista e põe-no a referenciar o seu primeiro item:
    explicit Iterador(ListaDouble& 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 == (IteradorConstante const& i) const;
    bool operator != (Iterador const& i) const;
    bool operator != (IteradorConstante const& i) const;

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

    friend IteradorConstante;

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

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

// Uma classe para representar iteradores para itens de listas ListaDouble.  Mas estes iteradores
// não permitem alterações nem na lista nem nos seus itens:
class ListaDouble::IteradorConstante {
public:
    // Construtor da classe.  Associa o iterador com a lista lista e põe-no a referenciar o seu primeiro item:
    explicit IteradorConstante(ListaDouble const& lista);

    // Construtor por cópia de um iterador não constante.  Permite converter implicitamente de um
    // tipo noutro:
    IteradorConstante(Iterador const& i);

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

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

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

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

    // A classe ListaDouble tem acesso irrestrito a todos os membros da classe IteradorConstante:
    friend ListaDouble;

    friend Iterador;

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

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

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

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

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

#endif // LISTA_DOUBLE_H

#include <cassert>
#include <algorithm>

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

inline ListaDouble::Elo::Elo(Elo* anterior, Elo* seguinte, Item const& item)
    : item(item), anterior(anterior), seguinte(seguinte) {
}

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

inline ListaDouble::ListaDouble()
    : quantos(0), inicial(new Elo) {
    // Captura-se qualquer excepção, pois pode ser o construtor de algum item a falhar...
    try {
        inicial->seguinte = final = new Elo(inicial);
    } catch(...) {
        delete inicial;
        throw;
    }
}

inline ListaDouble::~ListaDouble()
{
    limpa();
    delete inicial;
    delete final;
}

inline ListaDouble& ListaDouble::operator = (ListaDouble const& l) {
    /*
      O problema aqui é fazer com que isto funcione apesar de possíveis excepções.  Podem ocorrer excepções:

      1.  Ao construir os elos.

      2.  Ao construir os itens nos elos.  Se Item for o mesmo que int, isto não acontece, mas nós
      queremos poder mudar Item para outro tipo qualquer, que pode lançar uma excepção ao ser
      construído...

      3.  Ao atribuir os itens nos elos, se se reciclarem os elos.  Mais uma vez com Item sendo int,
      isto não acontece, mas nós queremos poder mudar Item à vontade...

      Se alguma coisa falhar, então considera-se que toda a operação de atribuição falhou e portanto
      a lista implícita deve ficar intacta, tal como estava no início...  Isso implica que não se pode
      reciclar, pois reciclar implica perder os valores dos itens...

      A melhor solução (proposta por Stroustrup) é simples.  Construir uma nova lista por cópia
      de l (o construtor por cópia comporta-se bem em caso de erro) e depois trocar os elos dessa
      cópia com os da lista implícita.  Quando o operador terminar, a cópia é destruída junto com
      todos os elos que estavam na lista implícita originalmente.  Para simplificar a solução
      enriqueceu-se a interface da classe com um procedimento membro troca().
    */
    ListaDouble copia(l);
    // Se a copia falhar a troca não chega a ser feita.  Logo, a instância implícita não é alterada!
    troca(copia);
    return *this;
    // Explique porque não é necessário o habitual teste if(this != &l)...
}

/*
    Alternativa mais simples...

    inline ListaDouble& ListaDouble::operator = (ListaDouble l) {
        troca(l);
        return *this;
    }
*/

// Coloca um novo elo dinâmico, contendo o item item, na cadeia duplamente ligada.  O novo elo é
// colocado entre o elo anterior e o seguinte.
inline void ListaDouble::poe(Elo* anterior, Elo* seguinte, Item const& item) {
    // Só se fazem alterações depois de construído o elo.  Assim, se a construção falhar fica tudo
    // como estava...
    Elo* const elo = new Elo(anterior, seguinte, item);
    anterior->seguinte = elo;
    seguinte->anterior = elo;
    ++quantos;
}

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

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

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

inline void ListaDouble::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 ListaDouble::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 ListaDouble::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 elo da cadeia duplamente ligada, destruindo-o:
inline void ListaDouble::tira(Elo* elo) {
    --quantos;

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

    delete elo;
}

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

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

    tira(inicial->seguinte);
}

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

    tira(final->anterior);
}

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

    // Só se pode remover 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 ListaDouble::remove(Iterador const& iterador)
{
    assert(iterador.elo != inicial && iterador.elo != final);

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

    tira(iterador.elo);
}

inline void ListaDouble::transfere(ListaDouble& l)
{
    // Se forem a mesma lista transferir é... não fazer nada!  Se l estiver vazia não é preciso fazer nada:
    if(this != &l && !l.vazia()) {
        // Basta trocar ponteiros!
        final->anterior->seguinte = l.inicial->seguinte;
        l.inicial->seguinte->anterior = final->anterior;
        l.final->anterior->seguinte = final;
        final->anterior = l.final->anterior;
        l.inicial->seguinte = l.final;
        l.final->anterior = l.inicial;

        quantos += l.quantos;
        l.quantos = 0;
    }
}

inline void ListaDouble::troca(ListaDouble& l)
{
    // Este procedimento swap() troca o valor de duas variáveis do mesmo tipo.  Está declarado
    // em #include <algorithm>:
    swap(inicial, l.inicial);
    swap(final, l.final);
    swap(quantos, l.quantos);
}

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

    return inicial->seguinte->item;
}

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

    return inicial->seguinte->item;
}

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

    return final->anterior->item;
}

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

    return final->anterior->item;
}

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

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

inline bool ListaDouble::cheia() const {
    /* Má solução para o problema.  Que fazer?  Eliminar esta função altera a interface a que os
      utilizadores da classe se habituaram.  Devolver false sempre é má ideia, visto que em
      algumas circunstâncias pode mesmo não haver espaço.  O ideal era voltar à lista dos livres
      e voltar a usar o procedimento reserva (o liberta não é necessário).  Esta função devolveria
       true se a lista dos livres estivesse vazia e o operador new falhasse.  O reserva tiraria da
      lista dos livres se lá existisse algum e usaria new se não existisse. */
    return false;
}

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

inline ListaDouble::IteradorConstante ListaDouble::primeiro() const {
    return IteradorConstante(*this);
}

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

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

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

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

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

inline ListaDouble::IteradorConstante ListaDouble::fim() const {
    return IteradorConstante(*this, final);
}

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

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

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

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

    elo = elo->seguinte;

    return *this;
}

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

    elo = elo->anterior;

    return *this;
}

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

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

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

    return elo == i.elo;
}

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

    return elo == i.elo;
}

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

    return elo != i.elo;
}

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

    return elo != i.elo;
}

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

    return elo->item;
}

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

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

inline ListaDouble::IteradorConstante::IteradorConstante(Iterador const& i)
    : lista(i.lista), elo(i.elo) {
}

inline
ListaDouble::IteradorConstante::IteradorConstante(ListaDouble const& l,
                                                  Elo const* elo)
    : lista(&l), elo(elo) {
}

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

    elo = elo->seguinte;

    return *this;
}

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

    elo = elo->anterior;

    return *this;
}

inline ListaDouble::IteradorConstante
ListaDouble::IteradorConstante::operator ++ (int) {
    ListaDouble::IteradorConstante resultado = *this;
    operator ++ ();
    return resultado;
}

inline ListaDouble::IteradorConstante
ListaDouble::IteradorConstante::operator -- (int) {
    ListaDouble::IteradorConstante resultado = *this;
    operator -- ();
    return resultado;
}

inline bool ListaDouble::IteradorConstante::
operator == (IteradorConstante const& i) const
{
    assert(lista == i.lista);

    return elo == i.elo;
}

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

    return elo != i.elo;
}

inline ListaDouble::Item ListaDouble::IteradorConstante::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_double.H"

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

ListaDouble::ListaDouble(ListaDouble const& l)
    // A construção da cópia é uma construção simples...
    : quantos(0), inicial(new Elo)
{
    // Captura-se qualquer excepção, pois reimplementações podem levar poeFim() a lançar outro
    // tipo de excepção que não bad_alloc, e além disso pode ser o construtor de algum item a falhar...

    try {
        inicial->seguinte = final = new Elo(inicial);
    } catch(...) {
        delete inicial;
        throw;
    }

    // ...seguida do acrescento dos itens da lista modelo:
    try {
        for(Elo* elo = l.inicial->seguinte; elo != l.final;
            elo = elo->seguinte)
            poeFim(elo->item);
    } catch(...) {
        // Se não se conseguiu colocar algum item a construção falhou e é necessário destruir
        // tudo o que entretanto foi construído:
        limpa();
        delete inicial;
        delete final;
        // Finalmente é necessário relançar a excepção!  Afinal, houve um erro e por isso a construção
        // falhou...
        throw;
    }
}

/*
   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 ListaDouble::limpa()
{
    // Destruir elos dinâmicos:
    for(Elo* elo = inicial->seguinte; elo != final; ) {
        Elo* seguinte = elo->seguinte;
        delete elo;
        elo = seguinte;
    }

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

ListaDouble& ListaDouble::operator += (ListaDouble const& l)
{
    // Captura-se qualquer excepção, pois reimplementações podem levar poeFim() a lançar
      outro tipo de excepção que não bad_alloc, e além disso pode ser o construtor de algum
      item a falhar...

    Elo* const ultimo = final->anterior;
    try {
        // Este ciclo funciona mesmo se l e *this forem a mesma lista!
        Elo* const lultimo = l.final->anterior;
        for(Elo* elo = l.inicial->seguinte; elo != lultimo->seguinte;
            elo = elo->seguinte)
            poeFim(elo->item);
    } catch(...) {
        // A operação falhou.  Logo, o melhor é repor tudo como estava.  Começa por se destruir
          todos os elos entretanto construídos (e vai-se descontando o quantos)...
        for(Elo* elo = ultimo->seguinte; elo != final; --quantos) {
            Elo* seguinte = elo->seguinte;
            delete elo;
            elo = seguinte;
        }
        // ...religa-se o último ao final...
        ultimo->seguinte = final;
        final->anterior = ultimo;
        // ...e relança-se a excepção...
        throw;
    }
    return *this;
}

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

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

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

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

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

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

// Definição do operador << para inserção de listas num canal:
std::ostream& operator << (std::ostream& saida, ListaDouble const& l)
{
    saida << '(';
    for(ListaDouble::IteradorConstante i = l.primeiro(); i != l.fim(); ++i)
    {
        saida << *i;
        if(i != l.ultimo())
            saida << ", ";
    }
    return saida << ')';
}

2.a)  Passe para um procedimento auxiliar o código de aumento da matriz dinâmica.  Simplifique o procedimento põe() e passe-o a inline.

2.b)  Melhore a função cheia().  Use o procedimento desenvolvido na alínea anterior para verificar se há memória para mais um item (e, de passagem, para a reservar), no caso de a matriz estar cheia.  Como se pode verificar se o procedimento teve sucesso?

2.c)  Reescreva o procedimento tira() de modo a reduzir o tamanho da matriz a metade sempre que a matriz dinâmica ficar ocupada a 25% ou menos do seu tamanho.  Não deixe nunca que a matriz seja reduzida abaixo do tamanho mínimo.

2.d)  Escreva um programa que permita verificar o lançamento da excepção PilhaInt::Cheia.  NÃO TESTE O PROGRAMA!  Porquê?

R:
pilha_int.H

#ifndef PILHA_INT_H
#define PILHA_INT_H

class PilhaInt {
public:
    typedef int Item;
    PilhaInt(int tamanho_inicial = tamanho_minimo); // construtor da classe.
    PilhaInt(PilhaInt const& p);// construtor por cópia da classe.
    ~PilhaInt();                // destrutor da classe.
    PilhaInt& operator = (PilhaInt const& p); // atribuição por cópia da classe.
    void troca(PilhaInt& p);    // troca conteúdo de p com o da instância implícita.
    void poe(Item const& item); // coloca item no topo da pilha.
    void tira();                // retira item do topo da pilha.
    Item topo() const;          // devolve item no topo da pilha.
    Item& topo();               // 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 altura() const;         // devolve número de itens na pilha.

    // Excepções:
    class Vazia {};
    class Cheia {};
    class TamanhoInvalido {
      public:
        int tamanho;
        TamanhoInvalido(int t)
            : tamanho(t) {
        }
    };

 private:
    void aumenta() const;
    void reduz() const;
    static int const tamanho_minimo = 32; // tamanho mínimo da matriz (tem de ser > 0).
    mutable int tamanho;        // tamanho corrente da matriz.
    int quantos;                // número de itens actualmente na pilha.
    mutable Item* itens;        // matriz dinâmica dos itens.
};

#include "pilha_int_impl.H"

#endif // PILHA_INT_H

#include <algorithm>

inline PilhaInt::PilhaInt(int tamanho_inicial)
    : tamanho(tamanho_inicial < tamanho_minimo? tamanho_minimo :
                                                tamanho_inicial),
      quantos(0), itens(new Item[tamanho]) {
    if(tamanho_inicial <= 0) {
        delete[] itens;
        throw TamanhoInvalido(tamanho_inicial);
    }
}

inline PilhaInt::~PilhaInt() {
    delete[] itens; // é uma matriz dinâmica, por isso delete[].
}

inline PilhaInt& PilhaInt::operator = (const PilhaInt& p) {
    /* O problema aqui é fazer com que isto funcione apesar de possíveis excepções.  Podem
      ocorrer excepções:

      1.  Ao construir a nova matriz dinâmica, se a antiga não tiver espaço.

      2.  Ao atribuir os itens.  Isto acontece quer se recicle o espaço quer não.  Se Item for o mesmo
      que int, isto não acontece, mas nós queremos poder mudar Item para outro tipo qualquer, que
      pode lançar uma excepção ao ser construído...

      Se alguma coisa falhar, então considera-se que toda a operação de atribuição falhou e portanto
      a pilha implícita deve ficar intacta, tal como estava no início...  Isso implica que não se pode
      reciclar, pois reciclar implica perder os valores dos itens...

      A melhor solução (proposta por Stroustrup) é simples.  Construir uma nova pilha por cópia
      de p (o construtor por cópia comporta-se bem em caso de erro) e depois trocar a matriz
      dinâmica dessa cópia com a da pilha implícita.  Quando o operador terminar, a cópia é destruída
      junto com a matriz dinâmica que esta na pilha implícita originalmente.  Para simplificar a solução
      enriqueceu-se a interface da classe com um procedimento membro troca().
    */
    PilhaInt copia(p);
    // Se a cópia falhar a troca não chega a ser feita.  Logo, a instância implícita não é alterada!
    troca(copia);
    return *this;
    // Explique porque não é necessário o habitual teste if(this != &l)...
}

/*
    Alternativa mais simples...

    inline PilhaInt& PilhaInt::operator = (PilhaInt p) {
        troca(p);
        return *this;
    }
*/

inline void PilhaInt::troca(PilhaInt& l)
{
    // Este procedimento swap() troca o valor de duas variáveis do mesmo tipo.  Está declarado
      em #include <algorithm>:
    swap(itens, l.itens);
    swap(tamanho, l.tamanho);
    swap(quantos, l.quantos);
}

inline void PilhaInt::poe(Item const& item) {
    if(quantos == tamanho)
        // Se não há espaço, constrói-se nova matriz dinâmica com o dobro do tamanho:
        aumenta();
    // Agora já há espaço, pode-se inserir normalmente:
    itens[quantos++] = item;
}

inline void PilhaInt::tira() {
    if(vazia())
        throw Vazia();
    --quantos;
    // Se for caso disso tenta reduzir tamanho da matriz dinâmica:
    if(quantos <= tamanho / 4 && tamanho / 2 >= tamanho_minimo)
        reduz();
}

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

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

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

inline bool PilhaInt::cheia() const {
    if(quantos < tamanho)
        return false;
    // Matriz cheia...  Há que tentar aumentá-la...
    try {
        aumenta();
    } catch(Cheia) {
        /* Se aumenta lançar excepção, então não há memória.  Note-se que não é usual nem
          desejável em geral usar excepções como se de um if se tratasse, mas neste caso não
          há outra solução mais simples... */
        return true;
    }
    return false;
}

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

#include "pilha_int.H"

#include <new>

PilhaInt::PilhaInt(PilhaInt const& p)
    : tamanho(p.tamanho), quantos(p.quantos), itens(new Item[tamanho]) {

    // A atribuição dos itens pode falhar, sendo lançada alguma excepção.  Nesse caso a construção da
    // pilha falha.  Assim, é necessário destruir a matriz dinâmica para evitar fugas de memória:

    // Copia itens:
    try {
        for(int i = 0; i != quantos; ++i)
            itens[i] = p.itens[i];
    } catch(...) {
        // Se a cópia falhar destruir matriz dinâmica...
        delete itens;
        // ...e relançar excepção...
        throw;
    }
}

void PilhaInt::aumenta() const
{
    // Note-se que a instância implícita só é alterada quando há a certeza de que o aumento teve sucesso:

    // Captura-se qualquer excepção, pois pode ser a atribuição de algum item a falhar...
    Item* novos;
    try {
        novos = new Item[2 * tamanho];
    } catch(...) {
        // Para todos os efeitos práticos não conseguir aumentar é como se a pilha estivesse cheia...
        throw Cheia();
    }

    // É necessário um bloco de tentativa à parte porque se as atribuições falharem é necessário destruir
    // a nova matriz dinâmica:
    try {
        // Copia-se para a nova matriz os itens que estavam na matriz dos itens:
        for(int i = 0; i != quantos; ++i)
            novos[i] = itens[i];
    } catch(...) {
        delete[] novos;
        // Para todos os efeitos práticos não conseguir aumentar é como se a pilha estivesse cheia...
        throw Cheia();
    }

    // Daqui para baixo já nada pode falhar.  Se falhar algo antes, não há problema, pois nada
    // sofreu alterações:

    // Novo tamanho:
    tamanho *= 2;
    // Destrói-se a matriz dos itens original:
    delete[] itens;
    // A matriz dos itens passa a ser a nova matriz construída (já com os itens antigos):
    itens = novos;
}

// PC: tamanho / 2 >= quantos
void PilhaInt::reduz() const
{
    // Se algo correr mal durante a redução, não se faz nada.  É estranho, mas pode não haver memória
    // para a redução ter sucesso.  As atribuições dos itens também podem falhar.

    // Note-se que a instância implícita só é alterada quando há a certeza de que a redução teve sucesso:

    // Captura-se qualquer excepção, pois pode ser a atribuição de algum item a falhar...
    Item* novos;
    try {
        novos = new Item[tamanho / 2];
    } catch(...) {
        return;                 // falhou? desiste-se da redução.
    }

    // É necessário um bloco de tentativa à parte porque se as atribuições falharem é necessário destruir
    // a nova matriz dinâmica:
    try {
        // Copia-se para a nova matriz os itens que estavam na matriz dos itens:
        for(int i = 0; i != quantos; ++i)
            novos[i] = itens[i];
    } catch(...) {
        delete[] itens;
        return;                 // falhou? desiste-se da redução depois de destruir a nova
                                // matriz dinâmica.
    }

    // Daqui para baixo já nada pode falhar.  Se falhar algo antes, não há problema, pois nada sofreu alterações:

    // Novo tamanho:
    tamanho /= 2;
    // Destrói-se a matriz dos itens original:
    delete[] itens;
    // A matriz dos itens passa a ser a nova matriz construída (já com os itens antigos):
    itens = novos;
}

R:
Em rigor é discutível se o devem ser lançadas excepções nestes casos (e o mesmo se passa com a classe PilhaInt!  Sim, isso significa que a solução do exercício 2 não é a melhor.  E sim, isso significa que o exemplo do resumo teórico não é o melhor...).  Ver discussão nas folhas teóricas.