Aula prática 5

Sumário

• Objectivos
• Resumo
• Material de apoio
• Exercícios
  • 1
  • 2
  • 3

1  Objectivos

Os alunos no final desta aula deverão conhecer:

1. O conceito de instância não declarada ou anónima.
2. Os conceitos de instância (variável ou constante) dinâmica e memória livre.  
3. Os operadores para construção e destruição de instâncias dinâmicas.
4. O princípio básico da utilização de instâncias dinâmicas: o que se constrói destrói-se.
5. A relação entre instâncias dinâmicas e classes.
6. A noção de construção de instâncias dinâmicas como reserva de recursos externos ao programa.
7. O princípio geral de que uma classe que reserve recursos externos deve possuir um destrutor.
8. A política elementar de gestão de instâncias dinâmicas: quem constrói destrói.
9. As vantagens, em termos de flexibilidade da lista resultante, da utilização de instâncias dinâmicas para guardar os elos da cadeia duplamente ligada de elos.
10. A vantagem para o programador de relegar para o sistema operativo a tarefa de lidar com as instâncias dinâmicas logo que deixam de ser necessárias.

Deverão também ser capazes de:

1. Implementar completamente as classes listas e iterador à custa de uma cadeia duplamente ligada, com guardas, de elos dinâmicos contendo os itens da lista.
2. Escrever pequenos programas usando ponteiros e instâncias dinâmicas.

Caso os alunos sintam que os objectivos não foram atingidos na totalidade deverão concluir/repetir os exercícios desta aula autonomamente e ou recorrer aos horários de dúvidas.

2  Resumo

3  Material de apoio

Os ficheiros relativos a esta aula estão disponíveis no arquivo Aula5.zip.

4  Exercícios

1.  Na Aula prática 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.  

No directório ~/POO/Aula5 encontrará os ficheiros fonte lista_de_aluno.H, lista_de_aluno_impl.H e lista_de_aluno.C, do módulo físico lista_de_aluno (tal como foi desenvolvido na Aula prática 4 embora adaptado para os itens serem da classe Aluno), os ficheiros fonte aluno.H e aluno_impl.H (que definem a classe Aluno), do módulo aluno, e o ficheiro fonte ordena_alunos.C, de um módulo com o mesmo nome que contém a função main() do programa.  Estes módulos fazem parte de um programa que lê informação acerca de alguns alunos (nome e número) e os escreve por ordem não-decrescente de número.

Juntamente com os ficheiros acima indicados encontrará um ficheiro de construção de nome Makefile que pode ser usado para construir o programa ordena_alunos.

Construa o ficheiro executável ordena_aluno do programa usando o comando make.  Execute-o.

1.a)  Analise a implementação das listas e iteradores realizada na Aula prática 4 e pense nas alterações a realizar 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++:

1. A matriz elos continua a ser necessária?  Porquê?  Quais as consequências da sua resposta para a representação da lista?  Onde se localizarão os elos necessários à lista?
2. O que acontece às operações privadas ListaDeAluno::reservaElo() e ListaDeAluno::libertaElo()?  Continuam a ser necessárias?  Porquê?
3. O que acontece à operação ListaDeAluno::estaCheia()?  Será que o melhor é eliminá-la?  Ou a lista pode estar mesmo cheia?
4. Quais os cuidados a atender na destruição de instâncias da classe ListaDeAluno?

1.b)  Altere a implementação das listas e iteradores da Aula prática 4 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++:

1. As operações privadas listaDeAluno::reservaElo() e listaDeAluno::libertaElo() deixam de ser necessárias.  Elimine-os.
2. Esta alteração implica que a cadeia simplesmente ligada de elos livres (disponíveis para futuras utilizações) deixa de fazer sentido, pois a reserva e a libertação de elos deixa de ser gerida pela própria lista.  A variável membro primeiro_elo_livre deixa de ser necessária.
3. Pela mesma razão deve-se abandonar a utilização da matriz membro elos e da constante membro de classe numero_maximo_de_itens, uma vez que deixa de haver um número máximo de itens pré-estabelecido.
4. A eliminação do número máximo de itens implica eliminar a função membro listaDeAluno::estaCheia().
5. É 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.
6. O construtor da lista pode ser bastante simplificado, uma vez que deixou de haver cadeia de elos livres.  O construtor deve construir as guardas da cadeia duplamente ligada.
7. 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.
8. Substitua as utilizações das operações listaDeAluno::reservaElo() e listaDeAluno::libertaElo() pelos operadores new e delete.  Faça uso do construtor definido para a estrutura Elo.

1.c)  Recorde a implementação do método listaDeAluno::transfereDe() realizada na Aula prática 4.  Use o cenário da Figura 5.1 para descrever o seu funcionamento.

1.d)  Use o cenário da Figura 5.2 para pensar numa implementação do referido método que tire partido da nova implementação das listas com elos dinâmicos.

1.e)  Re-implemente o método listaDeAluno::transfereDe() com as ideias desenvolvidas.

2.a)  Altere a classe listaDeAluno (e iterador correspondente), de modo a guardar ponteiros para aluno (Item passa a ser Aluno*).  A classe deve passar a chamar-se ListaDePonteiroAluno.

2.b)  Altere o módulo físico ordena_alunos.C de modo a 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.  

2.c)  Quem se deverá encarregar de destruir os alunos^* (que são variáveis dinâmicas)?

2.d)  Que sentido têm as operações ListaDePonteiroAluno::primeiraOcorrenciaDe() e ListaDePonteiroAluno::ultimaOcorrenciaDe() quando os itens na lista são ponteiros?

^*  Salvo seja.

3.  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 iteradores, os chamados iteradores constantes, que o garantam.  Siga os passos abaixo:

1. Crie uma nova classe embutida chamada listaDeAluno::IteradorConstante igual à classe listaDeAluno::Iterador.  Não se esqueça de definir os respectivos métodos!
2. Altere os construtores da classe de modo a receberem uma referência para uma lista constante e um ponteiro para um elo não-constante.  Desse modo fica claro que o iterador não alterará directamente a lista*.
3. Compile...  Interprete os erros.
4. Mude o tipo do atributo que aponta a lista associada para apontar uma lista constante.  Desse modo o compilador deixa de se preocupar com as inicializações.
5. Mude o tipo devolvido pelo operador * para Item const&.  Alternativamente Item (devolução por valor, menos eficiente).
6. Mude o tipo do segundo operando do operador de inserção de uma lista num canal para listaDeAluno const&.
7. Compile.  O compilador acha (bem) que primeiro() pode alterar a lista [indirectamente].
8. Defina um construtor que permita construir um iterador constante a partir de um iterador normal.  Esse construtor deve definir uma conversão implícita.  É necessária uma amizade para isso...  As classes listaDeAluno, listaDeAluno::Iterador e listaDeAluno::IteradorConstante formam um casamento a três...
9. Defina alternativas a ListaAluno::primeiro(), etc. que devolvam um iterador constante.
10. Defina os operadores de igualdade e diferença entre um iterador normal e um iterador constante (por esta ordem).  É precisa uma outra amizade..
11. Acrescente versões das operações ListaAluno::insereAntes() e ListaAluno::remove() que recebam iteradores constantes.  Estas operações fazem sentido por, apesar de os iteradores garantirem a não alteração das listas associadas, as listas em si não serem constantes.  Pode-se dizer que a autorização de mudança vem da lista e não do iterador, que se limita a indicar uma posição.  É por causa destas novas operações que os iteradores constantes, apesar de garantirem a constância dos itens referenciados, contêm ponteiros para elos não constantes.
12. Compile.

*  Na realidade não é claro que não altere os seus elos.  O programador produtor se encarregará de garantir que tal não se passa.