Resumo da Aula 5

Sumário

• Instâncias (constantes ou variáveis) dinâmicas e memória livre
  • Construção de instâncias dinâmicas
  • Destruição de instâncias dinâmicas
  • Problemas comuns
    • Instâncias dinâmicas perdidas
    • Dupla destruição
    • Utilização depois da destruição
  • Construtores e destrutores
    • Construtores
    • Destrutores
  • Construção de matrizes dinâmicas
  • Destruição de matrizes dinâmicas
  • Falta de memória
  • Alguns exemplos
  • Classes com instâncias dinâmicas
• Listas com instâncias dinâmicas
• Leitura recomendada
• Referências

1  Instâncias (constantes ou variáveis) dinâmicas e memória livre

int j = 20;

int f()
{
    int const i = 10;
    ...
}

Em C++ há também instâncias (variáveis ou constantes) não declaradas, que não têm nome.  Por exemplo, as instâncias temporárias.  Seja a classe C++ Racional, usada para representar a noção de número racional.  Seja a sobrecarga do operador + para esta classe C++:

Racional const operator + (Racional um_racional, Racional const& outro_racional)
{
    um_racional += outro_racional;

    return um_racional;
}

Que sucede quando se escreve:

Racional r1(1, 3);
Racional r2(2, 3);

cout << r1 + r2 << endl;

É óbvio que surge no ecrã o valor 1.  O que acontece é que o operador + é invocado, devolvendo uma instância constante temporária cujo valor é inserido no canal cout.  Esta constante temporária existe enquanto a instrução estiver a ser executada e não tem nome, pois nunca foi declarada.

Tal como com as instâncias declaradas, também as instâncias não-declaradas temporárias têm uma permanência que é dada pelas regras da linguagem.

Para além das instâncias temporárias usuais, envolvidas em praticamente todas as expressões do C++, existem outras instâncias não-declaradas mas com uma duração arbitrária, controlada directamente pelo programador.  Esta instâncias chamam-se instâncias (constantes ou variáveis) dinâmicas, exactamente porque têm uma duração arbitrária.  

Resumindo:

Até agora só se viu como usar variáveis com nomes associados.  Por exemplo, a definição

int i = 10;

Ao contrário das instâncias que se usaram até agora, as instâncias dinâmicas têm uma duração arbitrária, à escolha do programador.  Uma variável estática global (como se viu no primeiro semestre) existe desde o início até ao fim do programa, ou seja, é construída no início do programa e destruída no seu fim.  Uma variável automática existe desde o momento em que a instrução que a define é executada (altura em que é construída) até que é atingida a chaveta final (}) do respectivo bloco de instruções (altura em que é destruída).  Uma variável dinâmica é construída e destruída quando o programador entender.

1.1  Construção de instâncias dinâmicas

int const* pc = new int const(10);

cout << *pc << endl;

int* p = new int(10);
*p = 20;
cout << *p << endl;

A construção de uma instância dinâmica é feita em dois passos distintos.

O primeiro passo é a reserva ou alocação de memória , e serve para requerer o endereço de uma zona de memória suficientemente grande para colocar uma instância do tipo pretendido.  A reserva e a libertação (ver abaixo) de memória são implementadas através de uma interacção apropriada entre as bibliotecas da linguagem C++ e o sistema operativo utilizado.

O segundo passo é a construção (ou inicialização) da instância nessa zona de memória, para o que se usa um dos construtores do tipo pretendido.  O operador new faz os dois passos automaticamente, muito embora eles possam ser separados.  A separação dos dois passos só é verdadeiramente útil em algumas ocasiões especiais (ver [1, §10.4.11 e §19.4.4]).

1.2  Destruição de instâncias dinâmicas

int const* pc = new int const(10);
cout << *pc << endl;
delete pc;

Existem políticas alternativas de gestão das variáveis dinâmicas:

1. Quem constrói destrói ou, posse única da instância dinâmica, que foi a política descrita.
2. Quem possui destrói, ou posse única, mas transferível, da instância dinâmica.
3. O último fecha a porte, ou posse partilhada da instância dinâmica.

Da mesma forma que para o operador new, o operador delete também realiza duas operações bem distintas.  Primeiro destrói a variável dinâmica usando o destrutor do tipo (ver mais abaixo).  Depois liberta, "dealoca" ou devolve ao sistema operativo a memória por ela ocupado, que fica assim livre para posteriores reutilizações.  É possível separar a destruição da libertação da memória, mas mais uma vez tal prática só é verdadeiramente útil em raras ocasiões (ver [1, §10.4.11]).

1.3  Problemas comuns

1.3.1  Instâncias dinâmicas perdidas

void f() 
{
    int* p = new int(0);
}

Outro caso comum é a reserva de memória de que depois se perde a referência.  Normalmente isso acontece por se fazer uma atribuição descuidada ao respectivo ponteiro.  Por exemplo:

int const* p = new int const(11);
int i;
p = &i; // e perdeu-se a referência da constante dinâmica...

^* Se feliz ou infelizmente é uma grande discussão...

1.3.2  Dupla destruição

double* p = new double(30.0);
delete p;
delete p; // erro dramático!

1.3.3  Utilização depois da destruição

int* p = new int(12);
*p = 20;
delete p;
*p = 30; // erro dramático (com sorte o programa aborta).

1.4  Construtores e destrutores

1.4.1  Construtores

tipo* nome = new tipo;

É possível invocar um dos construtores do tipo explicitamente.  Por exemplo, para obrigar à invocação do construtor por omissão (útil no caso de uma instância dinâmica de um tipo básico) pode-se escrever:

tipo* nome = new tipo();

int* p = new int(10);

Racional const* pr = new Racional const(6, 14);

1.4.2  Destrutores

#include <iostream>

class C {
    C() {
        std::cout << "Construtor!" << std::endl;
    }
    ~C() {
        std::cout << "Destrutor!" << std::endl;
    }
};

int main()
{
    C* p = new C; // aparece "Construtor!".
    delete p;     // aparece "Destrutor!".
}

1.5  Construção de matrizes dinâmicas

cout << "Introduza tamanho: " << endl;
int n;
if(cin >> n && n > 0) {
    int* m = new int[n];

    // Utilização de m como outra matriz qualquer:
    for(int i = 0; i != n; i++)
        m[i] = 0;
}

1.6  Destruição de matrizes dinâmicas

Racional* mr =
    new Racional[100]; // constrói matriz com 100 racionais com valor zero (0).
delete[] mr;           // destrói a matriz.

É um erro grave usar o operador delete em vez do operador delete[] para uma matriz dinâmica, mesmo que esta possua apenas um elemento.

1.7  Falta de memória

Há uma forma alternativa do operador new (que não se recomenda) que, caso não haja memória disponível, se limita a devolver o valor singular dos ponteiros (o valor 0):

#include <new>

...

Classe* p = new(std::nothrow) Classe;
if(p == 0) {
    cerr << "Não havia memória..." << endl;
    ...
}

1.8  Alguns exemplos

Aluno* p = new Aluno("Ambrósio Amaral", 1234);
cout << p->nome() << endl;
delete p;

Aluno* p = new Aluno[20];
p[3].nome("Xisto Ximenes");
delete[] p;

1.9  Classes com variáveis dinâmicas

Suponha-se uma classe PilhaDeInt contendo uma matriz dinâmica de itens:

/** Representa pilhas de int.
    @invariant itens aponta matriz com capacidade_actual itens e
              capacidade_inicial <= capacidade_actual e
               0 <= número_de_itens <= capacidade_actual. */
class PilhaDeInt {
  public:
    typedef int Item;

    /** Constrói pilha vazia.
        @pre V.
        @post estáVazia(). */
    PilhaDeInt();

    /** Destrói a pilha.
        @pre V.
        @post recursos externos reservados foram libertados. */
    ~PilhaDeInt();

    /** Devolve o item que está no topo da pilha.
        @pre ¬estáVazia().
        @post topo idêntico ao item no topo de *this. */
    Item const& topo() const;

    /** Indica se a pilha está vazia.
        @pre V.
        @post estáVazia = *this está vazia. */
    bool estáVazia() const;

    /** Devolve altura da pilha.
        @pre V.
        @post altura = altura de *this. */
    int altura() const;

    /** Devolve o item que está no topo da pilha.
        @pre ¬estáVazia().
        @post topo idêntico ao item no topo de *this. */
    Item& topo();

    /** Põe um novo item na pilha (no topo).
        @pre V.
        @post *this contém um item adicional no topo igual a novo_item. */
    void põe(Item const& novo_item);

    /** Tira o item que está no topo da pilha.
        @pre ¬estáVazia().
        @post *this contém os itens originais menos o do topo. */
    void tiraItem();
 
  private:
    static int const capacidade_inicial = 32;
    int capacidade_actual;
    Item* itens;
    int número_de_itens;

    /** Indica se a pilha verifica a condição invariante da classe.
        @pre V.
        @post cumpreInvariante = (itens <> 0 e 
              capacidade_inicial <= capacidade_actual e
              0 <= número_de_itens <= capacidade_actual). */
    bool cumpreInvariante() const;
};

inline PilhaDeInt::PilhaDeInt()
    : capacidade_actual(capacidade_inicial), 
      itens(new Item[capacidade_actual]), 
      número_de_itens(0)
{
    assert(cumpreInvariante());
}

inline PilhaDeInt::~PilhaDeInt()
{
    assert(cumpreInvariante());

    delete[] itens;
}

inline bool PilhaDeInt::estáVazia() const
{
    assert(cumpreInvariante());

    return altura() == 0;
}

inline int PilhaDeInt:: altura() const
{
    assert(cumpreInvariante());

    return número_de_itens;
}

inline PilhaDeInt::Item const& PilhaDeInt::topo() const
{
    assert(cumpreInvariante());
    assert(not estáVazia());

    return itens[número_de_itens - 1];
}

inline PilhaDeInt::Item& PilhaDeInt::topo()
{
    assert(cumpreInvariante());
    assert(not estáVazia());

    return itens[número_de_itens - 1];
}

void PilhaDeInt::põe(Item const& novo_item)
{
    assert(cumpreInvariante());

    if(número_de_itens == capacidade_actual) {
        Item* const novos_itens = new Item[capacidade_actual * 2];
        for(int i = 0; i != número_de_itens; ++i)
            novos_itens[i] = itens[i];
        capacidade_actual *= 2;
        delete[] itens;
        itens = novos_itens;
    }
    itens[número_de_itens] = novo_item;
    ++número_de_itens;

    assert(cumpreInvariante());
}

inline void PilhaDeInt::tiraItem()
{
    assert(cumpreInvariante());
    assert(not estáVazia());

    --número_de_itens;

    assert(cumpreInvariante());
}

inline bool PilhaDeInt::cumpreInvariante() const
{
    return itens != 0 and
           capacidade_inicial <= capacidade_actual and
           0 <= número_de_itens <= capacidade_actual;
}

inline PilhaDeInt::PilhaDeInt()
    : capacidade_actual(capacidade_inicial), 
      itens(new Item[capacidade_actual]), 
      número_de_itens(0)
{
    assert(cumpreInvariante());
}

inline PilhaDeInt::~PilhaDeInt()
{
    assert(cumpreInvariante());

    delete[] itens;
}

...

void PilhaDeInt::põe(Item const& novo_item)
{
    assert(cumpreInvariante());

    if(número_de_itens == capacidade_actual) {
        Item* const novos_itens = new Item[capacidade_actual * 2];
        for(int i = 0; i != número_de_itens; ++i)
            novos_itens[i] = itens[i];
        capacidade_actual *= 2;
        delete[] itens;
        itens = novos_itens;
    }
    itens[número_de_itens] = novo_item;
    ++número_de_itens;

    assert(cumpreInvariante());
}

...

2  Listas com variáveis dinâmicas

1. O número limite de itens numa lista é fixado a priori.
2. Pode, por isso, ser insuficiente.
3. Se não for insuficiente corre o risco de ser excessivo (se só se usarem 1% do limite permitido, há muitos elos que ocupam memória e não chegam nunca a ser usados).

Note-se que, ao passar a usar variáveis dinâmicas (na memória livre), pode-se relegar para o sistema a tarefa de lidar com os elos livres.  Para isso serve o operador delete!  Logo, todo o código relativo à cadeia dos elos livres, que era fundamental na implementação anterior, torna-se agora desnecessário.  (Mas note-se que, por razões técnicas, pode ser necessário mais tarde recuperar esse código...)

Que passos é necessário dar?

Em primeiro lugar, é necessário eliminar a matriz de elos e a constante que representava o número de máximo de itens por lista.  Com variáveis dinâmicas o número limite de itens por lista vai depender da memória livre disponível em cada momento.  Por outro lado, como já não é necessário lidar com uma cadeia de elos livres, podem-se eliminar a variável membro primeiro_elo_livre e os procedimentos reservaElo() e libertaElo().

Depois, há que decidir o que fazer com a operação ListaDeInt::estáCheia().  É que agora não é fácil saber se ainda há espaço disponível sem tentar construir um novo elo dinâmico.  Mas, se se optar por esta solução, não se deve destruí-lo logo em seguida, pois no tempo que medeia entre o programador consumidor chamar a função ListaDeInt::estáCheia() e de facto proceder a uma inserção pode deixar de haver espaço disponível (não esquecer que os programas correm, tipicamente, em concorrência uns com os outros, e usando a mesma memória física).  Logo, há apenas três possíveis soluções:

1. Fazer a função devolver sempre false.  É a pior das soluções porque há situações em que não corresponde à verdade.
2. Eliminar a operação.  É má solução, pois pode haver já código que usa a operação ListaDeInt::estáCheia() e que terá de ser rescrito.  Deve-se sempre pensar três vezes antes de alterar a interface de uma classe (ou, em geral de um módulo).
3. A operação ListaDeInt::estáCheia() tenta construir um novo elo da cadeia.  Se conseguir, guarda-o para usar na próxima operação de inserção e devolve false.  Senão devolve true.  Note-se que há uma mudança no contrato da classe.  Dantes, se ListaDeInt::estáCheia() devolvesse true era certo que a próxima operação de inserção (se não fosse precedida por nenhuma de remoção) falharia.  O novo contrato estabelece que se ListaDeInt::estáCheia() devolver true nada pode ser garantido (pois pode passar a haver memória disponível por um outro programa concorrente ter libertado memória).

1. A interface da classe não está ainda completamente congelada.  Afinal, ela começou a ser desenhada quando ainda não se conheciam os conceitos de instâncias dinâmicas e de lançamento de excepções.  Assim, é ainda aceitável proceder a uma alteração da interface da classe...
2. Finalmente, o lançamento de excepções é a melhor forma de lidar com este tipo de problemas.  A falta de memória, que é um recurso externo ao programa, deverá ser assinalada através do lançamento de uma excepção.  Aliás, já o é, pois uma falta de memória é assinalada pelo operador new através do lançamento da excepção bad_alloc.

É 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, simplifica-se bastante a construção de elos.

Uma vez que a cadeia de livres desapareceu, passando-se a guardar os elos na memória livre, há que eliminar as chamadas das funções membro reservaElo() e libertaElo() (entretanto desaparecidas), e substitui-las por utilizações dos operadores new e delete.

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.

O destrutor da lista deve destruir todos os elos da cadeia, incluindo as guardas.

Há um procedimento que pode ser muito simplificado: transfereDe().  Este procedimento pode passar a ser inline, pois a sua implementação já não precisa de nenhum ciclo, limitando-se a manipular ponteiros.

Finalmente, há que tentar perceber o que se passa quando, depois das alterações sugeridas, se copiam duas listas...

3  Leitura recomendada

Recomenda-se a leitura dos Capítulos 4 e 5 de [2].

4  Referências

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