Aula 19 - Técnicas Avançadas de C++ - Parte III

Conceitos-Chave:

- estrutura de dados, com o objectivo de proporcionar ao programador a forma mais eficiente de armazenar dados
- vector, uma estrutura de dados da STL, semelhante a um array, mas que permite a expansão e diminuição da sua capacidade
- lista ligada, uma estrutura de dados que permite a eficiente inserção e eliminação de dados, através do uso de apontadores e memória dinâmica

Estruturas de dados

Nesta aula irei focar o estudo sobre estruturas de dados. As estruturas de dados têm o objectivo de proporcionar ao programador a forma mais eficiente (em termos de velocidade, memória) de armazenar dados. Estes dados podem ser o HP de uma personagem, ou as texturas de um nível de jogo. Um programador de jogos precisa da maior velocidade e memória que conseguir obter e, por isso, saber implementar estruturas de dados é fundamental.

Felizmente, existe a STL que implementou de forma genérica grande parte das estruturas de dados mais úteis. Com bastantes anos de desenvolvimento é quase impossível fazer melhor do que a STL para dados genéricos. No entanto, a STL poderá não ser a melhor solução em determinados casos, mas na maior parte deles é a melhor solução disponível.

Limitações de um array

Vamos supor que precisamos de um array de uma determinada estrutura (Monster) que contenha todos os monstros no ecrã. Como o número de monstros ao mesmo tempo pode variar ao longo do programa, podemos optar por armazenar espaço para, digamos, 10 monstros (estamos a colocar este número como o máximo de monstros que poderá aguentar o nosso array). Isso está implementado no seguinte código:

#include <iostream>
using namespace std;

struct Monstro
{
    int hp;
    int mp;
};

int main()
{
    const int MAX_MONSTROS_ECRA = 10;
    Monstro monstros_ecra[MAX_MONSTROS_ECRA];
    
    //...
}

Esta seria uma solução razoável, se tivéssemos a certeza que nunca iríamos passar o limite dos 10 monstros no ecrã. Imaginemos que fizemos alguns testes e que verificámos que num certo nível do nosso jogo, poderão estar até 1000 monstros no ecrã. Poderíamos definir a capacidade máxima do array para 1000. No entanto, este método pode gerar uma enorme carga no programa. A estrutura Monster necessita de 8 bytes de memória (porque possui duas variáveis do tipo int, de 4 bytes cada), ou seja o array iria necessitar de 8000 bytes, ou seja quase 8 KB (KiloBytes). Isto parece pouco, mas isso é porque a nossa estrutura tem só 2 variáveis. Se a nossa estrutura de dados ocupasse 1 KB, precisaríamos quase 1 MB só para armazenar esta variável. Este valor é demasiado elevado para uma variável, principalmente se tivermos em conta que só irá necessitar de tanto espaço num determinado nível, mas mesmo assim irá ocupar este espaço durante todo o tempo de execução do programa.

Existem várias soluções para este problema. Primeiro iremos ver uma implementação muito simples (uma classe feita por mim) e outra implementação muito melhor (através do uso da classe vector da STL).

Classe BetterArray

Decidi criar uma classe que possibilita a adição (e delecção) de novos elementos num array, através do uso de apontadores e da memória dinâmica. Além disso, possui um contador, que também poderá facilitar na contagem dos elementos. Esta classe só funciona com variáveis do tipo int, mas poderíamos utilizar templates para se tornar numa classe genérica.

#include <iostream>
using namespace std;

class BetterArray
{
public:	
    void addValue(int value); //adiciona um valor no fim do array
    void delEndValue();      //elimina o valor que está no fim do array
    
    int getValue(int index); //retorna o valor que está na posição index do array
    int getCount();          //retorna o número de elementos do array
    
    BetterArray();           //construtor
    ~BetterArray();          //destrutor

private:
        
    int *array;              //o apontador para o array
    int count;               //o número de elementos do array
};

int main()
{
    BetterArray teste;       //cria um objecto de teste para a nossa classe
    teste.addValue(3);       //é adicionado o valor '3' ao final do array (primeiro valor)
    
    //esta é uma forma simples de apresentar os dados dentro do array...
    for (int x = 0; x < teste.getCount(); x++)
    {
        cout << "Posicao: " << x << ", Valor: " << teste.getValue(x) << ", Count: " << teste.getCount() << endl;
    }
    
    cin.get();
    
    teste.addValue(9);    
    teste.addValue(27);   //foram adicionados dois valores
    
    for (int x = 0; x < teste.getCount(); x++)
    {
        cout << "Posicao: " << x << ", Valor: " << teste.getValue(x) << ", Count: " << teste.getCount() << endl;
    }
    
    cin.get();
    
    teste.delEndValue();  //foi eliminado um valor do fim do array
    
    for (int x = 0; x < teste.getCount(); x++)
    {
        cout << "Posicao: " << x << ", Valor: " << teste.getValue(x) << ", Count: " << teste.getCount() << endl;
    }
    
    cin.get();
    return 0;
}


BetterArray::BetterArray()
{
    array = NULL;         //no início o apontador para o array não aponta para nada
    count = 0;            //numero de elementos é igual a 0
}

void BetterArray::addValue(int value)
{

    int *tempArray = new int [count+1]; //cria um array na memória dinâmica, com mais um elemento do que o antigo
    
    for (int x = 0; x < count; x++)
    {
        tempArray[x] = array[x];   //passa os conteúdos do array antigo para o novo
    }
    
    tempArray[count] = value; //o último elemento do array novo é alterado, com o novo valor
    count++;
    
    delete [] array;   //é eliminado o array antigo
    array = tempArray; //o apontador para o array passa a apontar para o novo array
    tempArray = NULL;  //já não temos uso para este array
        
}

void BetterArray::delEndValue()
{
    if (count > 1)  //se houver mais que um elemento...             
    {
        int *tempArray = new int [count-1]; //cria um novo array com menos um elemento do que o anterior
    
        for (int x = 0; x < count-1; x++)
        {
            tempArray[x] = array[x]; //passa todos os elementos (excepto o último) para o novo array
        }
        
        count--;

        delete [] array;
        array = tempArray;
        tempArray = NULL;
    }
    else if (count == 1) //se só houver um elemento, ele é eliminado...
    {
        delete [] array;
        array = NULL;
        count = 0;
    }
}

int BetterArray::getValue(int index)
{
    if (count > 0) //isto é para prevenir erros do programador
    {
        if (index < count)
        {
            return array[index];
        }
    }
}

int BetterArray::getCount()
{
    return count;
}

BetterArray::~BetterArray()
{
    if (array != NULL) //se o array ainda não tiver sido eliminado...
    {
        delete [] array;
        array = NULL;
    }
}

Esta classe necessita de conhecimentos razoáveis de como funcionam apontadores e a memória dinâmica. Aconselho-vos a reverem a aula 11 e a aula 14.

STL - Vector

A classe que desenvolvi apresenta bastantes problemas. Primeiro, porque só teve cerca de meia hora de desenvolvimento. Segundo, porque foi desenvolvida por um estudante "amador". Além destes problemas, o mais visível é a criação de um array temporário só para fazer a transição entre o array antigo e o novo, ou seja, durante uns instantes, iremos precisar do dobro da memória, já para não falar no tempo de processamento que precisamos para passar cada elemento para o novo array.

Felizmente, existe a classe vector, que faz parte da STL e que tem a função de introduzir uma nova estrutura de dados, semelhante ao array, mas muito mais dinâmica. Podemos declarar um vector através da expressão seguinte:

#include <vector>

vector <TIPO_DE_DADOS> identificador;

Como exemplo, vou aproveitar o main que fiz para a classe BetterArray:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector <int> teste;       //cria um vector de teste, com o tipo int
    teste.push_back(3);       //é adicionado o valor '3' ao final do array (primeiro valor)
	
    //notem as diferenças
	for (int x = 0; x < teste.size(); x++)
    {
        cout << "Posicao: " << x << ", Valor: " << teste[x] << ", Count: " << teste.size() << endl;
    }
    
    cin.get();
    
    teste.push_back(9);    
    teste.push_back(27);   //foram adicionados dois valores
	
    for (int x = 0; x < teste.size(); x++)
    {
        cout << "Posicao: " << x << ", Valor: " << teste[x] << ", Count: " << teste.size() << endl;
    }
        
    cin.get();
    
    teste.pop_back();  //foi eliminado um valor do fim do array
	
    for (int x = 0; x < teste.size(); x++)
    {
        cout << "Posicao: " << x << ", Valor: " << teste[x] << ", Count: " << teste.size() << endl;
    }
    
    cin.get();
    return 0;
}

Vou explicar cada método novo, um por um:

vector <int> teste;

Aqui estamos a declarar um vector. A classe vector faz valer o uso de templates para poder tratar qualquer tipo de variável. Quando colocamos <int> no meio da declaração, estamos a dizer à classe que pretendemos usar variáveis inteiras dentro do vector.

push_back(valor) e pop_back()

A classe vector utiliza o conceito de estrutura de dados do tipo "pilha" (stack). Isto basicamente quer dizer que poderemos adicionar novos elementos no fim da pilha e retirar elementos também do fim da pilha: os últimos a entrar são os primeiros a sair.

O push adiciona elementos e o pop retira os elementos. Podem ver esse conceito ilustrado na seguinte figura (retirada da wikipedia):

size()

A classe vector possui um contador, que nos diz o número de elementos do vector. Como podem ver, é bastante útil.

Outras situações com a classe vector

Ainda falta falar de mais características da classe vector, para que possam substituir os vossos arrays em favor desta estrutura de dados. Felizmente, são conceitos bastante fáceis de aprender.

No exemplo seguinte veremos que utilizar a classe vector e utilizar um array pode ser praticamente igual:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector <char> nome; //isto é algo estranho, porque uma string seria muito melhor
    
    nome.push_back('I');
    nome.push_back('V');
    nome.push_back('O');
    
    cout << nome[0] << nome[1] << nome[2] << endl;
    
    nome[0] = 'M';  //podemos alterar cada elemento como num array normal
    nome[1] = 'A';
    nome[2] = 'R';
    
    cout << nome[0] << nome[1] << nome[2] << endl;
    
    nome.resize(5); //podemos alterar a dimensão do array!

    //se não fizessemos resize(), isto daria erro...    
    nome[4] = 'A';  //estou a introduzir os caracteres ao contrário...
    nome[3] = 'I';
    
    for (int x = 0; x < nome.size(); x++)
    {
        cout << nome[x];
    }
    
    cout << endl;
    
    cin.get();    
    
    return 0;
}

Neste exemplo, é óbvia a vantagem do vector em relação ao array, mantendo a sua simplicidade de código.

Existe ainda outros métodos, que nos permitem inserir elementos no meio de cada vector (em vez de ser só no final). No entanto, devido à natureza dos vectores, estes métodos são muito ineficientes, ou seja, se for mesmo necessário vão ter que procurar outra alternativa.

Listas Ligadas

As listas ligadas apresentam uma vantagem enorme sobre os vectores: permitem a adição ou delecção de qualquer elemento da lista, sem perder em performance. Como nem tudo é perfeito, apresentam uma enorme desvantagem em relação aos vectores: não é possível aceder a um índice aleatório da lista, sem perder em performance. Iremos já ver porquê ao analisar a natureza de uma lista ligada.

Uma lista é constituída por vários nós. Cada nó contém:

• uma variável para o tipo de dados que pretendemos guardar (ex: int value)
• um apontador para o nó seguinte (ex: Node* proximo)

Nota:

Existem vários tipos de listas, nesta aula irei apresentar a mais simples, a lista simplesmente ligada, que apresenta apenas um apontador para o próximo elemento, sendo que o último elemento liga-se a um valor nulo.
Os outros tipos de listas incluem um apontador para o elemento anterior (listas duplamente ligadas) ou o último elemento liga-se ao primeiro, formando um ciclo (lista circularmente ligada)

Podem ver um esquema a ilustrar uma lista simplesmente ligada (novamente da wikipedia)

Para visualizarmos os conceitos que estão na base de uma lista ligada, antes de criar uma classe para a gestão da mesma, vou criar um exemplo de uma lista ligada "à mão".

#include <iostream>
using namespace std;

class Node	//cada nó da nossa lista
{
public: 
    int value;	//o valor que fica armazenado
    Node* proximo;	//um apontador para o próximo nó (que está ligado a este)

    Node () { value = 0; proximo = NULL; }	//um construtor para prevenir erros de inicialização
};

int main()
{
    Node *um = new Node();	//assim estamos a chamar o construtor de cada nó
    Node *dois = new Node();
    Node *tres = new Node();
    
    um->value = 1;	//agora atribuimos cada valor a cada nó
    dois->value = 2;
    tres->value = 3;
    
    um->proximo = dois;	//o nó "um" liga-se ao nó "dois"
    dois->proximo = tres; //o nó "dois" liga-se ao nó "três"
    tres->proximo = NULL; //o nó "três" não se liga a nenhum, porque é o último da lista
    
    Node* temp = um; //para podermos percorrer a lista, ligamos um nó temporário ao primeiro da lista
    
    while (temp != NULL)	//enquanto o valor temporário não for nulo (não chega ao fim da fila)
    {
        cout << temp->value << endl;	//mostra-nos o valor
        temp = temp->proximo;			//temp assumo o valor do próximo nó, percorrendo assim a lista
    }

    cin.get();	//esperamos um bocado...

    //agora vamos "eliminar" o segundo valor

    um->proximo = tres;	//vejam que simples! basta apontar o nó "um" para o "nó" três e já está!
    delete dois;		//agora tiramos o "dois" da memória porque já não precisamos dele 
    dois = NULL;		//isto é para prevenir erros
    
    temp = um;			//voltamos a fazer tudo de novo...

    while (temp != NULL)	//enquanto o valor temporário não for nulo (não chega ao fim da fila)
    {
        cout << temp->value << endl;	//mostra-nos o valor
        temp = temp->proximo;			//temp assumo o valor do próximo nó, percorrendo assim a lista
    }

    cin.get();

    delete um, tres;	//não se esqueçam de eliminar!

    return 0;
}

Novamente, vou tentar explicar o que é novo (se bem que nada daqui seja propriamente novo, a mecânica é que é nova).

Comecemos por analisar a classe Node. Cada "Node" representa um nó da lista, portanto uma lista é um conjunto de nós. Cada nó possui duas variáveis:

• int value - Esta variável serve para armazenar o valor de cada nó (é a variável "mais importante" para o utilizador)
• Node* próximo - Esta variável contém toda a mecânica para que uma lista ligada funciona. É um apontador para objectos da própria classe, ou seja, serve para apontar para outro Node. Assim, cada nó armazena uma variável que aponta para o elemento seguinte, permitindo o acesso a outros nós da lista.

Nota:

Notaram decerto na utlização da expressão NULL. Normalmente utiliza-se esta expressão para identificar apontadores que não apontam para nenhuma variável. De facto, o valor NULL faz exactamente o mesmo efeito que o valor 0(zero). Em vez de Node *proximo = NULL; poderíamos fazer Node* proximo = 0;.

Dica:

A classe nó apresenta ainda um construtor. Este construtor tem o papel de se certificar que as variáveis são inicializadas com valores nulos. Se não definirmos as variáveis, estas assumirão um valor aleatório, o que poderá originar conflitos mais tarde. Este construtor não é essencial neste exemplo, porque eu defino as variáveis antes de as utilizar, mas em projectos maiores esta pequena linha de código pode dar uma ajuda enorme.

Por exemplo, poderíamos usar o seguinte código:

                
if (node == NULL)
{
    cout << "Erro" << endl;
}
else
{
    cout << node->value << endl;
}

Depois de criada a classe, declaramos três apontadores (com os criativos nomes de "um", "dois" e "tres") e alojamos para cada um deles um objecto do tipo Node na memória dinâmica. Neste ponto aconselhava-vos a reverem a aula 14, para relembrarem como funciona a memória dinâmica.

Papel dos apontadores e da memória dinâmica numa lista

As listas ligadas têm o propósito de facilitar a inserção e eliminação de cada nó. Como tal, é bastante óbvio o papel da memória dinâmica e apontadores numa lista ligada. No exemplo acima, para inicializar a lista, segui os seguintes passos:

• Atribui os valores de cada nó(value)
• Liguei o nó "dois" ao nó "um". Isto é feito através da atribuição do objecto "dois" ao apontador "proximo", que está dentro do nó "um". Assim, podemos dizer que o nó que está a seguir ao nó "um" é o nó "dois".
• Liguei o nó "dois" ao nó "tres", pelo mesmo processo que acima
• Defini como NULL o apontador "proximo" do nó "tres". Isto significa que não existem mais elementos na lista, ou seja, "tres" é o último elemento da lista

Para compreendermos melhor a importância dos apontadores e memória dinâmica, demonstrei o caso específico da eliminação dos nós:

• Liguei o nó "um" ao nó "tres". Defini o apontador proximo do nó "um" para apontar para o nó "tres" (assim o nó "tres" passa a ser o nó seguinte ao nó "um")
• Eliminamos o nó "dois" da memória dinâmica, pois este não se torna necessário para o resto do programa (este passo não é necessário, pois o passo anterior já chega para eliminar o elemento da lista. No entanto é bastante aconselhável este passo, pois assim estaremos a libertar memória)

Podem ver a facilidade com que eliminamos um elemento numa lista ligada: basta alterar um apontador no nó anterior ao elemento que pretendemos eliminar. Os outros elementos continuam a apontar para os nós seguintes, independentemente da sua localização.

Percorrer a lista

É aqui que se apresenta a desvantagem de uma lista ligada. Num array, cada elemento está organizado na memória: o elemento seguinte está sempre na posição seguinte da memória. Numa lista ligada, cada elemento poderá estar disposto em qualquer lugar da memória, à dez mil lugares à frente ou a um lugar atrás do elemento seguinte. Poderão ver esse conceito ilustrado nas tabelas seguintes:

Array

Endereço	1200	1201	1202	1203	1204
Valor	1	2	3	4	5

Lista Ligada

Endereço	1200	1201	1202	1203	1204	1205	1206	1207	1208
Valor	4	---	2	---	5	3	---	---	1
Próximo (Aponta para)	1204	---	1205	---	NULL	1200	---	---	1202

Nota:

Os "buracos" (---) em alguns endereços na lista ligada significam endereços que são ocupados por outras variáveis e serve para ilustrar a "desordem" de uma lista. Num programa, esses "buracos" também existiriam num array (embora depois ou antes de todo o array e nunca entre cada elemento do array). Esta nota é só para não ficarem com a ideia que as listas ocupam mais memória de que um array (na verdade ocupam, pois possuem mais uma variável que um array: um apontador. No entanto este aumento é desprezável).

Como tal, é muito mais fácil (e eficiente) aceder a um elemento de um array do que um elemento de uma lista. Isto porque, se quisermos aceder à quarta posição de um array fazemos array[3] (ou array+3). Com esta instrução, vai ser procurado o 3º elemento à direita do primeiro. Para acedermos ao quarto elemento de uma lista teríamos que fazer: head->proximo->proximo->proximo, em que head é o primeiro elemento da lista. Até aqui não perdemos muito em eficiência, mas se quisermos consultar o x elemento de uma lista, o caso muda de figura. Enquanto isso num array seria tão simples como array[x], numa lista teríamos que recorrer a algo como:

int getValue(int x, Node* head)
{
    Node* temp = head;
    for (int i = 0; i < x; i++)
    {
        temp = temp->proximo;
    }
    
    return temp->value;
}

O simples uso do for faz com que isto fique muito mais ineficiente do que um simples array[3];

Classe Lista

Como esta aula já foi muito longa (e porque o código para uma Lista é um pouco grande), decidi colocar a classe lista junto com o código fonte desta aula, em vez de ocupar ainda mais espaço nesta página. Penso que seja fácil de entender, pelo menos se perceberam o código acima (e está muito comentado).

Mesmo cobrindo tantos aspectos destas simples estruturas de dados, isso ainda não chega. Na próxima aula irei introduzir o conceito de iterador e irei mostrar a classe List, da STL. Espero também poder introduzir a estrutura de dados "árvore binária", assim como alguns algoritmos simples de procura.