Resolução dos Exercícios da Aula 5

Exercícios

1. Na Aula 4 a implementação dos conceitos de lista e iterador foi alterada de modo a fazer uso de ponteiros. Os ponteiros foram usados, em particular, para guardar informação acerca dos elos anterior e seguinte de cada elo na cadeia duplamente ligada de elos que se usou para representar a lista. Crie os ficheiros fonte correspondentes à resolução da Aula 4, incluindo o ficheiro de construção do executável. Construa o ficheiro executável teste_aluno usando o comando make.

1.a) Altere a implementação da lista e iteradores de modo a transferir a gestão (reserva e libertação) dos elos para os mecanismos de construção e destruição de variáveis dinâmicas disponibilizados pelo C++:

Os métodos privados reserva() e liberta() deixam de ser necessários. Elimine-os.
Esta alteração implica que a cadeia simplesmente ligada de elos livres (disponíveis para futuras utilizações) deixa de fazer sentido, pois a requisição e a libertação deixa de ser gerada por nós. A variável membro primeiro_livre deixa de ser necessária.
Pela mesma razão deve-se abandonar a utilização da matriz membro elos e da constante membro de classe limite, uma vez que deixa de haver limite pré-estabelecido de itens.
A eliminação do número limite de itens implica alterar a função membro cheia(). Para já adopte a solução simplista de a fazer devolver sempre false.
É conveniente acrescentar um construtor à estrutura Elo. Esse construtor recebe como argumento um ponteiro para o elo anterior, um ponteiro para o elo seguinte, e o valor do item a guardar nesse elo. Se cada um dos parâmetros do construtor tiver um valor por omissão (os ponteiros o valor singular 0 e o item o valor por omissão dos itens, ou seja, Item()), simplifica-se bastante a construção de elos.
O construtor da lista pode ser bastante simplificado, uma vez que deixou de haver cadeia de elos livres. Por isso deve passar a ser inline. O construtor deve construir as guardas da cadeia duplamente ligada.
A utilização de variáveis dinâmicas requer alguns cuidados quando à sua destruição. Faça um destrutor para a lista que destrua todos os elos da cadeia, incluindo as guardas.
Substitua as utilizações dos métodos reserva() e liberta() pelos operadores new e delete. Faça uso do construtor definido para a estrutura Elo.
Refaça o método transfere(). Será possível implementá-lo sem nenhum ciclo?

R:
Apresentam-se os ficheiros fonte do módulo lista_aluno:

lista_aluno.H

#ifndef LISTA_ALUNO_H
#define LISTA_ALUNO_H
#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();
    // Destrutor da classe:
    ~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:
    /* A lista é representada por uma cadeia duplamente 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,
            const Item& item = Item());
    };
    // 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;
    // 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 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

lista_aluno_impl.H

#include <cassert>
// Definição das funções e procedimentos membro inline da classe ListaAluno::Elo:
inline ListaAluno::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 ListaAluno:
inline ListaAluno::ListaAluno()
    : quantos(0), inicial(new Elo), final(new Elo(inicial)) {
    inicial->seguinte = final;
}
inline ListaAluno::~ListaAluno()
{
    limpa();
    delete inicial;
    delete final;
}
// 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 ListaAluno::poe(Elo* anterior, Elo* seguinte, Item const& item) {
    ++quantos;
    Elo* const elo = new Elo(anterior, seguinte, item);
    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 elo da cadeia duplamente ligada, destruindo-o:
inline void ListaAluno::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 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 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 ListaAluno::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 ListaAluno::transfere(ListaAluno& 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 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 {
    /* 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 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:

lista_aluno.C

#include "lista_aluno.H"
// Definição das funções e procedimentos membro não-inline da classe ListaAluno:
/*
   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;
    // Destruir elos dinâmicos (excepto as guardas):
    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;
}
ListaAluno& ListaAluno::operator += (ListaAluno const& l)
{
    // Haverá espaço?
    // assert(limite - comprimento() >= l.comprimento());
    /* Deixou de ser prática esta verificação... Mas era possível. Bastava tentar reservar todos os
    novos elos necessários. Se se conseguisse, punham-se na lista dos livres (ressuscitada). Se não,
    a asserção falhava... Ou outra solução semelhante. */
    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 << ')';
}

1.b) Altere a classe ListaAluno (e iterador correspondente), de modo a guardar ponteiros para aluno (Item passa a ser Aluno*). A classe deve passar a chamar-se ListaPAluno.

R:
A alteração é trivial.

1.c) Altere o módulo físico de teste (teste_aluno.C) de modo que, usando duas listas de ponteiros para alunos, leia 5 alunos do teclado e os guarde na memória livre, colocando ponteiros para eles nas duas listas. A primeira lista conterá os ponteiros para os alunos por ordem crescente de nome. A segunda conterá ponteiros para os mesmos alunos mas por ordem crescente de número. No final os alunos deverão ser mostrados duas vezes: por ordem de nome e por ordem de número. Quem se deverá encarregar de destruir os alunos (que são variáveis dinâmicas)?

R:
Apresenta-se apenas o módulo com a função main():

teste_aluno.C

#include <iostream>
#include <string>
using namespace std;
#include "aluno.H"
#include "lista_ponteiro_aluno.H"
int main()
{
    ListaPAluno alunos_por_nome;
    ListaPAluno alunos_por_numero;
    for(int i = 0; i != /*20*/5; ++i) {
        cout << "Aluno? ";
        string nome;
        int numero;
        cin >> nome >> numero;
        Aluno* paluno = new Aluno(nome, numero);
        ListaPAluno::Iterador i = alunos_por_nome.primeiro();
        while(i != alunos_por_nome.fim() && (**i).nome() < nome)
            ++i;
        alunos_por_nome.insere(i, paluno);
        i = alunos_por_numero.primeiro();
        while(i != alunos_por_numero.fim() && (**i).numero() < numero)
            ++i;
        alunos_por_numero.insere(i, paluno);
    }
    for(ListaPAluno::Iterador i = alunos_por_nome.primeiro();
        i != alunos_por_nome.fim(); ++i)
        cout << **i << endl;
    for(ListaPAluno::Iterador i = alunos_por_numero.primeiro();
        i != alunos_por_numero.fim(); ++i)
        cout << **i << endl;
    for(ListaPAluno::Iterador i = alunos_por_numero.primeiro();
        i != alunos_por_numero.fim(); ++i)
        delete *i;
}

Exercícios propostos

1. O operador de inserção de uma lista no canal recebe a lista por referência não constante. Altere de modo a que passe a receber a lista por referência constante. Recompile. A mensagem de erro surge porque não existem iteradores que garantam que não alteram os itens referenciados nem a lista associada. O objectivo deste exercício é construir um novo tipo de iterador que o garanta. Siga os passos abaixo:

Crie uma nova classe embutida chamada ListaAluno::IteradorConstante igual à classe ListaAluno::Iterador. Não se esqueça de definir os respectivos métodos.
Altere os construtores da classe de modo a receberem uma referência para uma lista constante e um ponteiro para um elo constante. Desse modo fica claro que o iterador não os alterará.
Compile... Interprete os erros.
Mude o tipo das variáveis membro para ponteiros para constantes. Desse modo o compilador deixa de ser preocupar com as inicializações.
Mude o tipo devolvido pelo operador * para Item simplesmente (não referência). Alternativamente altere para Item const& (referência constante).
Mude o tipo do segundo operando do operador de inserção de uma lista num canal para ListaAluno const&.
Compile. O compilador acha (bem que primeiro() pode alterar a lista [indirectamente]).
Defina um construtor que permita construir um iterador constante a partir de um iterador normal. Esse construtor deve definir uma conversão implícita. É precisa uma amizade para isto... As classes ListaAluno, ListaAluno::Iterador e ListaAluno::IteradorConstante formam um casamento a três...
Defina alternativas a primeiro(), etc. que devolvam um iterador constante.
Defina um operador de comparação de um iterador normal com um iterador constante (por esta ordem). É precisa uma outra amizade...

R:
Apresentam-se os ficheiros fonte do módulo lista_double (não se incluem os comentários que se encontram já no módulo lista_aluno acima):

lista_double.H

#ifndef LISTA_DOUBLE_H
#define LISTA_DOUBLE_H
#include <iostream>
class ListaDouble {
public:
    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;
    ListaDouble();
    ~ListaDouble();
    void poeInicio(Item const& item);
    void poeFim(Item const& item);
    void insere(Iterador& i, Item const& item);
    void insere(Iterador const& i, Item const& item);
    void tiraPrimeiro();
    void tiraUltimo();
    void remove(Iterador& i);
    void remove(Iterador const& i);
    void limpa();
    void transfere(ListaDouble& l);
    ListaDouble& operator += (ListaDouble const& l);
    Item primeiroItem() const;
    Item& primeiroItem();
    Item ultimoItem() const;
    Item& ultimoItem();
    int comprimento() const;
    bool vazia() const;
    bool cheia() const;
    Iterador primeiro();
    IteradorConstante primeiro() const;
    Iterador ultimo();
    IteradorConstante ultimo() const;
    Iterador fim();
    IteradorConstante fim() const;
    Iterador inicio();
    IteradorConstante inicio() const;
    Iterador procuraPrimeiro(Item const& item);
    IteradorConstante procuraPrimeiro(Item const& item) const;
    Iterador procuraUltimo(Item const& item);
    IteradorConstante procuraUltimo(Item const& item) const;
private:
    struct Elo {
        Item item;
        Elo* anterior;
        Elo* seguinte;
        Elo(Elo* anterior = 0, Elo* seguinte = 0,
            Item const& item = Item());
    };
    int quantos;
    Elo* const inicial;
    Elo* const final;
    void poe(Elo* anterior, Elo* seguinte, Item const& item);
    void tira(Elo* elo);
};
class ListaDouble::Iterador {
public:
    explicit Iterador(ListaDouble& lista);
    Iterador& operator ++ ();
    Iterador& operator -- ();
    Iterador operator ++ (int);
    Iterador operator -- (int);
    Item& operator *() const;
    bool operator == (Iterador const& i) const;
    bool operator == (IteradorConstante const& i) const;
    bool operator != (Iterador const& i) const;
    bool operator != (IteradorConstante const& i) const;
    friend ListaDouble;
    friend IteradorConstante;
private:
    Iterador(ListaDouble& lista, Elo* elo);
    ListaDouble* lista;
    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:
    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);
    IteradorConstante& operator ++ ();
    IteradorConstante& operator -- ();
    IteradorConstante operator ++ (int);
    IteradorConstante operator -- (int);
    Item operator *() const;
    bool operator == (IteradorConstante const& i) const;
    bool operator != (IteradorConstante const& i) const;
    friend ListaDouble;
    friend Iterador;
private:
    IteradorConstante(ListaDouble const& lista, Elo const* elo);
    ListaDouble const* lista;
    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

lista_double_impl.H

#include <cassert>
// 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), final(new Elo(inicial)) {
    inicial->seguinte = final;
}
inline ListaDouble::~ListaDouble()
{
    limpa();
    delete inicial;
    delete final;
}
inline void ListaDouble::poe(Elo* anterior, Elo* seguinte, Item const& item) {
    ++quantos;
    Elo* const elo = new Elo(anterior, seguinte, item);
    anterior->seguinte = elo;
    seguinte->anterior = elo;
}
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);
}
inline void ListaDouble::insere(Iterador& iterador, Item const& item)
{
    assert(!cheia());
    assert(this == iterador.lista);
    assert(iterador.elo != inicial);
    poe(iterador.elo->anterior, iterador.elo, item);
}
inline void ListaDouble::insere(Iterador const& iterador, Item const& item)
{
    assert(!cheia());
    assert(this == iterador.lista);
    assert(iterador.elo != inicial);
    poe(iterador.elo->anterior, iterador.elo, item);
}
inline void ListaDouble::tira(Elo* elo) {
    --quantos;
    elo->anterior->seguinte = elo->seguinte;
    elo->seguinte->anterior = elo->anterior;
    delete elo;
}
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);
    assert(this == iterador.lista);
    Elo* const elo = iterador.elo->seguinte;
    tira(iterador.elo);
    iterador.elo = elo;
}
inline void ListaDouble::remove(Iterador const& iterador)
{
    assert(iterador.elo != inicial && iterador.elo != final);
    assert(this == iterador.lista);
    tira(iterador.elo);
}
inline void ListaDouble::transfere(ListaDouble& l)
{
    if(this != &l && !l.vazia()) {
        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 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!
    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:

lista_double.C

#include "lista_double.H"
// Definição das funções e procedimentos membro não inline da classe ListaDouble:
void ListaDouble::limpa()
{
    quantos = 0;
    for(Elo* elo = inicial->seguinte; elo != final; ) {
        Elo* seguinte = elo->seguinte;
        delete elo;
        elo = seguinte;
    }
    inicial->seguinte = final;
    final->anterior = inicial;
}
ListaDouble& ListaDouble::operator += (ListaDouble const& l)
{
    if(this != &l)
        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;
}
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 das funções e procedimentos membro não inline da classe
// ListaDouble::IteradorConstante:
// Definição de funções e procedimentos não membro e não inline:
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 << ')';
}