PRG29003: Etapa 2: Projeto de estruturas de dados

Desde o início do semestre foi usada a biblioteca STL, que contém implementações das estruturas de dados estudadas. Na primeira etapa da disciplina se enfatizou conhecer e usar essas estruturas de dados. Na segunda etapa o foco está no projeto de uma estrutura de dados, e o resultado esperado é a criação de estruturas de dados pelas equipes. Podem ser criadas versões que reproduzam (possivelmente com um toque pessoal) as características das estruturas de dados estudadas, ou mesmo novas estruturas de dados, diferentes daquelas conhecidas.

As estruturas de dados que já conhecemos são:

• Lineares: filas, pilhas e listas
• Associativas: tabelas hash, conjuntos e árvores de pesquisa binária

Mais especificamente o objetivo de aprendizagem desta unidade é:

Desenvolver (criar) uma estrutura de dados que possa ser utilizada em programas, possuindo uma interface de programação bem definida, e incluindo os algoritmos específicos necessários para a eficiência de suas operações quanto ao uso de memória e tempo computacional.

Algumas das estruturas conhecidas são bastante simples, e não serviriam como objeto de estudo nesta etapa da disciplina (refiro-me especificamente a filas e pilhas). As demais têm complexidade adequada para serem desenvolvidas neste último mês de aula. Além delas, outras estruturas de dados podem ser escolhidas:

• Trie: uma trie é um tipo de árvore n-ária (que pode ter um número n de ramos por nodo), em que os dados estão armazenados nos ramos, e não nos nodos. Esse tipo de árvore armazena prefixos dos dados, então são adequadas para dados formados por cadeias de elementos (ex: strings, endereços IP, sequências de bits em geral, ...). Um uso conhecido para tries é como dicionário de termos para um sistema do tipo auto-completar. Uma variação de tries é radix tree.
• Array Deques: um array deque é um tipo de fila que usa um array dinâmico (i.e. que pode ser expandido ou contraído) para armazenar dados. Ela possibilita a inserção e remoção eficiente de dados de seus extremos, e o acesso a qualquer dado pode ser feito com tempo constante (i.e. o custo de tempo computacional dessa operação é O(1)).
• Hashed Array Tree: um hashed array tree (ou HAT) é parecido com um array deque, porém sua estrutura interna faz um melhor uso de memória. Apesar do nome, ela nada tem a ver com tabelas hash.
• Lista desenrolada: uma lista desenrolada é parecida com uma lista usual, porém ela possibilita armazenar múltiplos dados em cada nodo da lista. Isso traz algumas vantagens quanto ao uso de memória e localização dos dados.
• Filtros Bloom: um filtro Bloom serve para informar sobre a existência ou não de um dado, porém probabilisticamente. Ele pode resultar em falsos positivos, quando retorna verdadeiro para um dado inexistente ou desconhecido, mas nunca retorna falsos negativos. Assim, se um filtro informa que um dado é desconhecido ou inexistente, com certeza isso é verdade. Essa estrutura de dados possui várias aplicações importantes.
• ... e possivelmente outras !!!

Requisitos para escrever estruturas de dados

O projeto de uma estrutura de dados envolve alguns requisitos.

O mais evidente é ter clara a finalidade da estrutura de dados, o que significa entender e prever o tipo de uso que se pode fazer dela. Uma consequência desse requisito é identificar as operações que podem ser feitas sobre essa estrutura de dados. A finalidade da estrutura, e seu conjunto de operações, tem forte correlação com a forma com que os dados são armazenados em memória.

O requisito seguinte diz respeito à organização dos dados em memória nessa estrutura de dados. Existem diversas técnicas para armazenar e organizar os dados em memória, de forma que as operações definidas possam ser realizadas com a eficiência projetada. A alocação dinâmica de memória, e esquemas de endereçamento indireto, são comuns ao se projetar o uso de memória em uma estrutura de dados.

Um outro requisito envolve escolher ou projetar algoritmos eficientes para as operações da estrutura de dados. Esses algoritmos têm forte dependência da forma com que os dados são organizados em memória. A eficiência desses algoritmos tem relevância, implicando compromissos entre menores tempos computacionais e usos de memória.

Alocação de memória

Alocação de memória significa reservar uma certa quantidade de memória do computador para um uso específico pelo programa. A forma mais simples de alocar memória é criar variáveis. Quando se declara uma variável, implicitamente aloca-se a memória necessária para armazenar seu conteúdo. Essa alocação é definida pelo compilador ao se compilar o programa. Para ter uma ideia de como isso funciona, veja este exemplo.

#include <iostream>
#include <string>

using namespace std;

// Esta função mostra informações sobre uma variável
// Ela é uma função template para funcionar com qualquer tipo de variável
// Parâmetros:
//  varname: nome da variável
//  val: uma referência à variável a ser mostrada
template <typename T> void mostra(const string & varname, T & val) {
  cout << "######################################################" << endl;

  // mostra o valor da variável
  cout << varname << " = " << val << endl;

  // mostra o endereço da variável
  T * ptr = &val;
  cout << "Endereço de " << varname << ": " << (void*)ptr << endl;

  // Mostra a quantidade de memória alocada à variável
  cout << "Memória alocada: " << sizeof(T) << " bytes" << endl;
}

int main() {
  // algumas variáveis
  // a memória para elas é alocada automaticamente
  int x = 35;
  float y = 3.1416;
  double h = 6.62607015e-34;
  char c = 'A';
  char v[8] = {'a','b','c','d','e','f','g',0};

  mostra("x", x);
  mostra("y", y);
  mostra("h", h);
  mostra("c", c);
  mostra("v", v);
}

Ao executá-lo, o resultado é este:

######################################################
x = 35
Endereço de x: 0x7ffd895a65e0
Memória alocada: 4 bytes
######################################################
y = 3.1416
Endereço de y: 0x7ffd895a65e4
Memória alocada: 4 bytes
######################################################
h = 6.62607e-34
Endereço de h: 0x7ffd895a65e8
Memória alocada: 8 bytes
######################################################
c = A
Endereço de c: 0x7ffd895a65de
Memória alocada: 1 bytes
######################################################
v = abcdefg
Endereço de v: 0x7ffd895a6610
Memória alocada: 8 bytes

Observe que cada variável possui um endereço de memória diferente (mostrado em hexadecimal). Dependendo do tipo de variável, a quantidade de memória alocada pode variar. O que determina quanta memória é necessária é o tipo da variável, não o dado que será armazenado. O compilador sabe quanta memória cada tipo de dados precisa, e por isso reserva a quantidade adequada para cada variável. Essa forma de usar memória é muito prática para o programador, que não precisa se preocupar com a alocação e liberação de memória para suas variáveis. Porém isso apresenta algumas limitações.

A primeira dificuldade aparece quando não se sabe exatamente quantos dados serão armazenados. Por exemplo, desejam-se armazenar números em um vetor, mas não se sabe exatamente quantos números serão fornecidos ao programa. Se forem usadas variáveis com alocação automática, o programador precisará criar um vetor cujo tamanho deve ser estimado pela quantidade de dados que provavelmente podem ser fornecidos no pior caso. Isso implica dois problemas:

1. Se a estimativa estiver incorreta, mais dados do que se pensou podem ser fornecidos e não haveria lugar no vetor para todos eles.
2. Se na maioria das vezes a quantidade de dados for bem menor do que o estimado, o vetor terá boa parte de sua capacidade ociosa. Isso significa que o programa estará reservando mais memória do que o necessário, e isso pode ter consequências negativas (lembre que memória é um recurso finito).

A segunda dificuldade é mais sutil. As variáveis existem apenas no escopo em que foram declaradas. Além de as variáveis de uma função não serem acessíveis em outra função, elas deixam de existir quando termina a função em que foram declaradas. Uma variável deixar de existir significa que a memória a ela alocada foi liberada, e pode ser usada para outros propósitos no programa. Portanto, se uma função armazena dados que devem estar disponíveis em outras funções, uma outra forma de alocar a memória deve ser usada. Esses dados devem ser armazenados em uma área de memória que não seja liberada automaticamente, quando terminar o escopo em que foi alocada.

Alocação dinâmica de memória

A alocação dinâmica de memória é uma técnica para reservar e liberar memória por demanda, e sob controle do programador. Ela funciona como se o programador criasse variáveis, porém tivesse que ordenar suas destruições. Assim, as variáveis não deixariam de existir automaticamente, quando a execução do programa saísse do escopo em que foram criadas.

A alocação dinâmica está diretamente relacionada com variáveis do tipo ponteiro. Ao se alocar memória dinamicamente, obtém-se o endereço inicial da área de memória obtida, e esse endereço deve ser armazenado em um ponteiro. O uso dessa área de memória, portanto, se faz por meio desse ponteiro.

A alocação dinâmica de memória na linguagem C++ se faz com o operador new. Esse operador aloca memória de acordo com o tipo de dados informado, e retorna um ponteiro para essa área de memória. Veja o exemplo a seguir, que mostra o uso do operador new em uma situação muito simplificada.

#include <iostream>
#include <string>

using namespace std;

template <typename T> void mostra(const string & varname, T * val) {
  cout << "######################################################" << endl;
  cout << "Dado apontado por " << varname << " = " << *val << endl;
  cout << "Endereço da área de memória usada por " << varname << ": " << (void*)val << endl;
  cout << "Memória alocada: " << sizeof(*val) << " bytes" << endl;
}

int main() {
  // algumas variáveis
  // a memória para elas é alocada automaticamente
  int * x;
  double  * h;

  // aloca dinamicamente memória para um valor do tipo int
  x = new int;

  // aloca dinamicamente memória para um valor do tipo double
  h = new double;

  // armazena valores nas áreas de memória alocadas, usando-se
  // os ponteiros
  *x = 35;
  *h = 6.6260715e-34;

  mostra("x", x); 
  mostra("h", h); 

  // libera as áreas de memória
  delete x;
  delete h;
}

Ao executá-lo, obtém-se isto:

######################################################
Dado apontado por x = 35
Endereço da área de memória usada por x: 0x561931d5de70
Memória alocada: 4 bytes
######################################################
Dado apontado por h = 6.62607e-34
Endereço da área de memória usada por h: 0x561931d5de90
Memória alocada: 8 bytes

Uma forma alternativa (e importante, como se poderá observar mais pra frente) de usar o operador new possibilita inicializar a área de memória assim que for alocada. O interessante dessa inicialização é que ela depende do tipo de dados para que foi alocada a memória. Para tipos de dados primitivos, como int, float, double e char, essa inicialização se limita a copiar um valor inicial. Veja como ficaria a alocação de memória do exemplo anterior com esse uso do operador new:

  // aloca dinamicamente memória para um valor do tipo int e depois para um double
  // e armazena valores nas áreas de memória alocadas
  x = new int(35);

  // aloca dinamicamente memória para um valor do tipo double
  h = new double(6.6260715e-34);

  mostra("x", x); 
  mostra("h", h);

No caso de um tipos de dados que possui um construtor, que é uma função-membro executada automaticamente quando se cria um valor desse tipo, o operador new o executa logo após alocar memória.

#include <iostream>
#include <string>

using namespace std;

struct Nome {
  string nome, sobrenome;

  // construtor: separa um nome completo, 
  // armazenando nome e sobrenome nos respectivos atributos
  Nome(const string & nome_completo) {
    int pos = nome_completo.find(' ');
    nome = nome_completo.substr(0, pos);
    int pos2 = nome_completo.find_first_not_of(" ", pos);
    sobrenome = nome_completo.substr(pos2);
  }
};

int main() {
  auto alguem = new Nome("Dona Bilica da Silva");

  cout << "Nome: " << alguem->nome << endl;
  cout << "Sobrenome: " << alguem->sobrenome << endl;

  delete alguem;
}

Por último, o exemplo a seguir mostra a persistência da área alocada de memória fora do escopo em que ela foi criada:

#include <iostream>
#include <string>

using namespace std;

// cria um vetor de inteiros com tamanho "size" e preenche
// todas suas posições com "valor_inicial"
int * cria_vetor(int size, int valor_inicial) {
  if (size <= 0) return nullptr;

  // cria um vetor com o tamanho dado por "size"
  auto v = new int[size];

  // preenche o vetor com o valor inicial
  for (int i=0; i < size; i++) v[i] = valor_inicial;
  return  v;
}

int main() {
  int size;

  cout << "Qual o tamanho do vetor: ";
  cin >> size;

  // v é um ponteiro para int
  auto v = cria_vetor(size, 99);

  cout << "Endereço do vetor: " << (void*)v << endl;
  cout << "Conteúdo do vetor: ";
  for (int x=0; x < size; x++) cout << v[x] << ',';
  cout << endl;

  // libera a memória do vetor
  delete[] v;
}

Um exemplo de execução é mostrado a seguir:

Qual o tamanho do vetor: 5
Endereço do vetor: 0x561a4d6a4690
Conteúdo do vetor: 99,99,99,99,99,

O uso do operador new nesse exemplo foi um pouco diferente. Como se pode notar, para criar um vetor indicou-se sua capacidade entre colchetes, logo após o tipo de dados. Isso pede que se aloque memória suficiente para conter aquela quantidade de valores do tipo informado:

// aloca memória suficiente oara guardar "size" valores do tipo int
auto v = new int[size];

Além disso, a função cria_vetor retorna como resultado o vetor que foi alocado. Isso mostra que a área de memória reservada para o vetor sobrevive ao final da função cria_vetor. Essa área de memória continuará alocada até que o operador delete a libere (o que se faz ao final da função main) ... ou até que o programa termine.

Resumo:

• O operador new aloca uma área de memória com capacidade suficiente para um tipo de dados indicado, e retorna um pointeiro para essa área de memória
• Após alocar a memória, o operador new a inicializa ao executar o construtor para o tipo de dados
• Toda área de memória alocada deve ser liberada usando o operador delete, quando não forma necessária