Guião da 6ª Aula Teórica

Sumário

Classes que reservam recursos externos:
1. Problemas comuns.
2. Construtores e destrutores.
3. Construção por cópia. Fornecimento automático.
4. Semântica de valor vs. semântica de referência.
5. Atribuição por cópia. O problema da auto-atribuição.
6. O exemplo das pilhas.

Guião

Escrever implementação das pilhas da Aula 5.

/** Representa pilhas de double.   @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 estaVazia().*/     PilhaDeInt();

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

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

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

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

    /** 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 ¬estaVazia().       @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;

    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;
}
PilhaDeInt::Item const& PilhaDeInt::topo() const {     assert(cumpreInvariante());

    return itens[número_de_itens - 1]; }

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

    return altura() == 0; }

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

    return número_de_itens; }

void PilhaDeInt::põe(Item const& novo_item) {
    assert(cumpreInvariante());
    if(número_de_itens == capacidade_actual) {
        Item* 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()); }
void PilhaDeInt::tiraItem() {     assert(cumpreInvariante());     assert(not estáVazia());
    --número_de_itens;
    assert(cumpreInvariante()); }
bool PilhaDeInt::cumpreInvariante() const {     return capacidade_inicial <= capacidade_actual and            0 <= número_de_itens <= capacidade_actual; }

Terminámos a aula passada reimplementando a classe PilhaDeInt usando uma matriz dinâmica de modo a poder crescer à medida das necessidades.

Explicar calmamente a implementação. Dizer que o esquema de crescimento garante ocupação de 50%... Perguntar porque é que isso não é verdade. Discutir possível alteração do tira().

Durante a implementação usámos dos dois princípios básicos das variáveis dinâmicas:

Todas as variáveis dinâmicas construídas devem ser destruídas.
A entidade encarregue de construir deve tipicamente responsabilizar-se pela destruição: política quem constrói destrói.

Estes princípios aplicam-se mais genericamente. Aplicam-se sempre que as instâncias de uma classe reservam recursos exteriores para seu uso exclusivo. A memória é apenas um desse recursos. Poderia ser, por exemplo, um ficheiro. A política mais genérica é: quem reserva liberta.

A nossa classe PilhaDeInt segue estes princípios, pois é ela que constrói e reconstrói a matriz dinâmica e é também ela que a destrói, em particular no destrutor da classe.

Mas a classe PilhaDeInt está longe de estar completa. Que sucede depois de:

PilhaDeInt p1;
PilhaDeInt p2 = p1;
// ou PilhaDeInt p1(p2);

Discutir. Concluir qual o problema. Fazer diagramas UML de objectos no quadro. Mostrar que as duas pilhas "partilham órgãos internos".

O que acontece é que o C++ fornece às classes sempre que possível um construtor por cópia. Este construtor por cópia implícito limita-se a construir os atributos de instância da classe copiando-os um a um.

Neste caso a cópia simples dos atributos tem resultados desastrosos! Ao contrário do que seria de esperar, depois da construção de p2, p1 e p2 partilham a matriz dinâmica! Nós queríamos que a classe tivesse semântica de valor, i.e., depois da construção de p2, p2 e p1 fossem rigorosamente iguais mas independentes, ou seja, não idênticas!

Note-se que igualdade não é o mesmo que mesma identidade! Lembrem-se dos gémeos (ou dos clones). Têm o mesmo código genético: são rigorosamente iguais. Mas são diferentes entidades: não têm a mesma identidade e, portanto, não são idênticas.

Ou seja, quando há semântica de referência, uma cópia gera um novo nome para aceder à mesma coisa (identidade). Quando há semântica de valor, uma cópia gera um novo objecto, igual mas não idêntico ao original.

Aquilo que sucedeu neste caso das pilhas foi que em vez de criarmos gémeos, criámos siameses! As pilhas não são idênticas, pois têm variáveis membro distintas, mas partilham uma parte dos dados, em particular a matriz dinâmica... Claramente a partilha de órgãos internos é indesejável: que o diga o Doutor Gentil Martins! Neste caso, não há operação que as salve...

Temos que proceder a algumas operações (não médicas...) para garantir que isto não acontece: é preciso definirmos um construtor por cópia explicitamente, já que o que o C++ fornece implicitamente não presta...

Um construtor por cópia recebe uma instância da própria classe como argumento e sempre por referência!

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

    ...
    /** Constrói pilha igual a original.       @pre V.       @post *this = original.*/     PilhaDeInt(PilhaDeInt const& original);

    ...
  private:

    ...
};

Explicar porque é por referência! Evita invocação recursiva!

Vamos então definir o construtor.

PilhaDeInt::PilhaDeInt(PilhaDeInt const& original)
    : capacidade_actual(?), itens(?), número_de_itens(?)
{     assert(original.cumpreInvariante());

    ...

    assert(cumpreInvariante());     // assert(*this == original) se definirmos o operador ==.
}

O que se deve começar por inicializar? Claramente número_de_itens deve ser inicializado com o mesmos valor que tem na pilha original:

PilhaDeInt::PilhaDeInt(PilhaDeInt const& outra_pilha)
    : capacidade_actual(?), itens(?),
      número_de_itens(original.número_de_itens)
{
    assert(original.cumpreInvariante());

    ...

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

Que fazer ao ponteiro para a matriz dinâmica itens? Se o inicializássemos com original.itens reproduziríamos o problema original! Cada pilha tem a sua própria matriz dinâmica!

Então é preciso construir uma nova matriz dinâmica. Mas com que dimensão? A única restrição é que a dimensão deve ser superior ou igual ao número de itens. Uma solução simples é construir a matriz com a mesma dimensão que a matriz na outra pilha, ficando ambas com a mesma capacidade.

Notar que a capacidade da pilha construída não tem de ser igual ao da pilha modelo! Conceptualmente só interessa que as pilhas fiquem exactamente com os mesmos itens. Na prática, porém, pode ser importante que se comportem exactamente da mesma forma do ponto vista da sua eficiência. Aí convém que usem uma matriz com a mesma dimensão...

PilhaDeInt::PilhaDeInt(PilhaDeInt const& original)
    : capacidade_actual(original.capacidade_actual),
      itens(new Item[capacidade_actual]),
      número_de_itens(original.número_de_itens)
{
    assert(original.cumpreInvariante());

    ...

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

Os elementos da nova matriz dinâmica foram construídos usando o construtor por omissão do tipo Item. Aliás, como Item é neste caso int, os elementos nem sequer foram inicializados! Se queremos que a pilha em construção seja uma cópia da pilha original temos de copiar os itens:

PilhaDeInt::PilhaDeInt(PilhaDeInt const& original)
    : capacidade_actual(original.capacidade_actual),
      itens(new Item[capacidade_actual]),
      número_de_itens(original.número_de_itens)
{
    assert(original.cumpreInvariante());

    for(int i = 0; i != número_de_itens; ++i)
        itens[i] = original.itens[i];

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

Dizer que este código tem um erro subtil: se a cópia falhar, há uma fuga de memória (se for lançada uma excepção durante a cópia dos itens, coisa que só acontece, de resto, se deixarem de ser int)!

Já está! Agora as instruções:

PilhaDeInt p1;
PilhaDeInt p2 = p1; // ou PilhaDeInt p1(p2);

já têm o efeito pretendido.

Fazer pequeno traçado e diagrama com o que acontece.

Problema resolvido? Não... Infelizmente, ainda há um caso bicudo:

PilhaDeInt p1;

for(int i = 0; i != 100; ++i)
p1.põe(i);

PilhaDeInt p2;

p2 = p1;

Explicar problema. Discutir diferença entre inicialização e atribuição. Fazer desenho.

É muito importante distinguir entre inicialização (ou construção) e atribuição. Na inicialização não existia nenhum objecto antes. Na atribuição já existia um objecto, que tem de mudar de valor. A haver alguma relação entre atribuição e inicialização pode ser posta nestes termos: a atribuição funciona conceptualmente como uma destruição do objecto existente seguida de uma construção por cópia!

Mas não vamos por aí.

Explicar que se construção por cópia é clonagem, a atribuição por cópia é uma operação plástica destinada a fazer um ser existente igual (mas não idêntico) a outro tomado como modelo.

O C++ fornece implicitamente às classes, sempre que possível, um operador de atribuição por cópia. O que ele faz é simplesmente atribuir cada uma das variáveis membro de instância (se existirem constantes ou referências de instância este operador não é fornecido). Neste caso o resultado é trágico:

A plástica acabou por unir o paciente ao modelo e, no processo, perderam-se para sempre alguns órgão internos que já existiam no paciente...

É normalmente assim quando as instâncias de uma classe reservam para seu uso exclusivo um recurso externo: neste caso é a memória onde se coloca a matriz dinâmica. A solução passa por implementarmos explicitamente o operador de atribuição por cópia de modo a fazer o desejado. Começa-se por declarar o operador na classe:

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

    ...
    /** Torna *this igual a modelo.       @pre V.       @post *this = modelo.*/     PilhaDeInt& operator=(PilhaDeInt const& modelo);

    ...
private:

    ...
};

Explicar brevemente o cabeçalho.

Vamos então definir o operador:

PilhaDeInt& PilhaDeInt::operator=(PilhaDeInt const& modelo)
{    assert(cumpreInvariante() and modelo.cumpreInvariante());

    ...

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

Há alguma parte correcta naquilo que o operador fornecido implicitamente pelo C++ faz?

Discutir.

PilhaDeInt& PilhaDeInt::operator = (PilhaDeInt const& modelo)
{    assert(cumpreInvariante() and modelo.cumpreInvariante());

    ...

    capacidade_actual = modelo.capacidade_actual;
    número_de_itens = modelo.número_de_itens;

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

e a matriz dos itens? Que fazer? Destruir e construir uma nova? Ok.

PilhaDeInt& PilhaDeInt::operator = (PilhaDeInt const& modelo)
{    assert(cumpreInvariante() and modelo.cumpreInvariante());

    delete[] itens;
    itens = new Item[modelo.capacidade_actual];

    ...

    capacidade_actual = modelo.capacidade_actual;
    número_de_itens = modelo.número_de_itens;

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

E agora? Falta copiar os itens!

PilhaDeInt& PilhaDeInt::operator = (PilhaDeInt const& modelo)
{    assert(cumpreInvariante() and modelo.cumpreInvariante());

    delete[] itens;
    itens = new Item[modelo.capacidade_actual];

    for(int i = 0; i != modelo.número_de_itens; ++i)
        itens[i] = modelo.itens[i];

    capacidade_actual = modelo.capacidade_actual;
    número_de_itens = modelo.número_de_itens;

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

E pronto. Perfeito! Já funciona.

Dizer que tem um erro subtil, que será resolvido na aula prática! E se for lançada uma excepção durante a cópia dos itens, ou mesmo durante a construção da nova matriz dinâmica?

Fazer traçado. Mostrar que funciona.

Acabado... Nem pensem! Vamos ver o que acontece no código:

PilhaDeInt p;
p.põe(1);
p.põe(2);
p = p;

O que devia acontecer? Ficar tudo na mesma, não era? E fica?

Desenhar. Fazer traçado mostrando que a pilha fica na mesma com dois itens mas com... lixo! Dizer que a plástica em que dá como modelo o próprio paciente devia corresponder a não fazer (nem pagar) nada, mas como as coisas estão o cirurgião desfigura o paciente e ainda cobra!

E agora? A questão é que se a instância implícita e modelo forem iguais, então não vale a pena fazer nada! Logo:

PilhaDeInt& PilhaDeInt::operator = (PilhaDeInt const& modelo)
{    assert(cumpreInvariante() and modelo.cumpreInvariante());

    if(*this != modelo) {
        delete[] itens;
        itens = new Item[modelo.capacidade_actual];

        for(int i = 0; i != modelo.número_de_itens; ++i)
            itens[i] = modelo.itens[i];

        capacidade_actual = modelo.capacidade_actual;
        número_de_itens = modelo.número_de_itens;     }

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

Mas, calma lá! Como é que o C++ sabe se duas pilhas são diferentes? Temos de definir o operador !=? Que faria ele? Comparar o número de itens e, caso fosse o mesmo, percorrer os itens das duas pilhas para saber há algum par de itens correspondentes diferentes... Temos que distinguir aqui duas coisas muito diferentes:

Uma coisa é a igualdade: se dois humanos são absolutamente iguais, significa que são gémeos ou clones.

Outra é a individualidade: dois gémeos não são o mesmo indivíduo.

Pensem em:

int i = 0;
int& j = i;
int k = i;

Nota: optar por um personagem com pseudónimo de acordo com as sensibilidades :-)

Qual a diferença entre i e j? São nomes diferentes para o mesmo indivíduo, que é uma variável inteira. Numa analogia humana, diria que j é um pseudónimo de i, como Manuel Tiago é pseudónimo de Álvaro Cunhal. Dar um murro no olho de um é dar um murro no olho do outro. Qual a diferença entre i e k? São nomes diferentes para indivíduos que não o mesmo, embora sejam iguais. Numa analogia humana diria que i e k são gémeos. Se o Paulo e o Miguel Portas fossem gémeos, dar um murro no olho do Paulo Portas não poria o olho do Miguel Portas negro...

Identidade - Alteridade
Igualdade - Desigualdade

Se duas coisas são diferentes (não igualdade), então são outras (não identidade).
Se duas coisas são iguais (igualdade), podem ou não ser a mesma (identidade ou não).
Se duas coisas são a mesma (identidade), então são iguais (igualdade).

É muito importante perceber que se dois nomes se referem ao mesmo indivíduo, então é óbvio que se referem a coisas iguais! Mas se dois nomes se referem a coisas iguais, não se pode dizer que se refiram um mesmo indivíduo!

Ou seja, se a pilha modelo é igual à pilha destino, então a atribuição não tem qualquer efeito. Mas dá muito trabalho saber se são iguais... Além disso, o problema da desfiguração ocorre quando paciente e modelo são a mesma pessoa, e não simplesmente pessoas iguais. É muito fácil saber se duas instâncias são na realidade o mesmo indivíduo: todas as variáveis estão na memória e portanto têm um endereço!

Uma forma simples de verificar se dois humanos são ou não idênticos é ver onde estão num dado instante de tempo. Se ocuparem exactamente a mesma posição são o mesmo humano. A posição (num dado instante de tempo) é o que marca a individualidade dos humanos e o endereço é o que marca a identidade das variáveis (do mesmo tipo)!

Sejam i e j dois nomes de int. Poderiam ser:

int i = 0;
int& j = i;

int i = 0;
int j = i;

Os nomes i e j referem-se a variáveis iguais. Como saber se i e j são a mesma variável?

Fácil! São-no se e só se tiverem o mesmo endereço!

Ou seja:

&i == &j é o mesmo que dizer que i e j são o mesmo indivíduo ou instância.

Logo:

i == j não implica &i == &j

mas

&i == &j implica i == j

Então no nosso caso:

PilhaDeInt& PilhaDeInt::operator = (PilhaDeInt const& modelo)
{    assert(cumpreInvariante() and modelo.cumpreInvariante());

    if(&*this != &modelo) {
        delete[] itens;
        itens = new Item[modelo.capacidade_actual];

        for(int i = 0; i != modelo. número_de_itens; ++i)
            itens[i] = modelo.itens[i];

        capacidade_actual = modelo.capacidade_actual;
        número_de_itens = modelo.número_de_itens;     }

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

Como & e * são o inverso um do outro:

PilhaDeInt& PilhaDeInt::operator = (PilhaDeInt const& modelo)
{    assert(cumpreInvariante() and modelo.cumpreInvariante());

    if(&*this != &modelo) {
        delete[] itens;
        itens = new Item[modelo.capacidade_actual];

        for(int i = 0; i != modelo. número_de_itens; ++i)
            itens[i] = modelo.itens[i];

        capacidade_actual = modelo.capacidade_actual;
        número_de_itens = modelo.número_de_itens;     }

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

Mas, e se o tamanho das duas matrizes dinâmicas for igual antes da atribuição? Não podemos reciclar a matriz? Para quê destruí-la se depois temos de a construir de novo? O cirurgião durante a plástica também aproveita o que puder.

PilhaDeInt& PilhaDeInt::operator = (PilhaDeInt const& modelo)
{     assert(cumpreInvariante() and modelo.cumpreInvariante());

    if(this != &modelo) {
        if(capacidade_actual != modelo.capacidade_actual) {
            delete[] itens;
            itens = new Item[modelo.capacidade_actual];         }

        for(int i = 0; i != modelo. número_de_itens; ++i)
            itens[i] = modelo.itens[i];

        capacidade_actual = modelo.capacidade_actual;
        número_de_itens = modelo.número_de_itens;     }

    assert(cumpreInvariante());
    // assert(*this == original) se definirmos o operador ==.
}

E pronto. Agora sim, temos o problema resolvido.

Concluir. Pontos importantes: reserva de recursos para uso exclusivo de cada instância de uma classe implica cuidados na construção, destruição e cópia. O operador de atribuição por cópia é talvez o mais delicado, pois tem de se portar bem com auto-atribuições e deve, se possível, reciclar o valor antigo, para evitar perdas de tempo. É também muito importante distinguir entre igualdade e individualidade. E entre semântica de cópia e semântica de referência (dar de novo exemplo dos iteradores para semântica de referência).