Contato

  • Jean Paulo Martins (jeanmartins utfpr edu br)
  • Sala 105, Bloco S (UTFPR - Campus Pato Branco)

Conteúdo

Estrutura e implementação

Implementar as funcionalidades da classe vector. Para tal utilizar uma estrutura similar a:

typedef struct {
    int* data;
    int  size;
    int capacity; 
} vector;

Inicialização e Finalização

Todas a funcionalidades e acesso aos dados será feita por funções, as quais precisaremos definir. A primeira delas, é a função de alocação da memória inicial de um vetor.

vector* new_vector(int cap_inicial);

De forma análoga há a função para desalocar a memória do vetor e do ponteiro.

// Desaloca a memória de v->data e o próprio v
void free_vector(vector* v);

Acesso e manipulação: sem crescimento

Para acessar um item do vetor e alterar o valor de um item, por exemplo:

// Retorna um ponteiro para o item na posição i
int* vector_at(vector* v, int i);
// Retorna o valor na posição i
int vector_get(vector* v, int i);
// Altera o valor na posição i
void vector_set(vector* v, int i, int valor);

Acesso e manipulação

Inserção: com crescimento

As funções acima não alteram o tamanho do vetor, portanto $i$ deve ser um índice válido. Já a função a seguir, tenta inserir um item no final do vetor, caso ainda haja espaço, basta inserí-lo e atualizar size. Caso contrário, é preciso realocar o vetor.

void vector_push_back(vector* v, int value);
/* Exemplo:
 v = 4 5 7 19 2 1
 push_back 5
 v = 4 5 7 19 2 1 5
 */

Suponha agora que queiramos inserir um elemento no vetor em uma dada posição que não seja o fim. Chamaremos essa função:

void vector_insert(vector* v, int value, int i);
/* Exemplo:
 v = 4 5 7 19 2 1
 vector_insert 5 3
 v = 4 5 7 5 19 2 1
 */

Se vector_insert é chamada para inserir um valor em uma posição $i$ do vetor, todos os elementos em posições posteriores a $i$ precisam ser deslocados uma posição adiante.

Implementada a inserção, temos condições de facilmente implementar uma função para inserir no início do vetor. Esta função precisa apenas chamar vector_insert(v, value, 0).

void vector_push_front(vector* v, int valor);

Remoção: sem decrescimento

De forma análoga às funções de inserção, temos as funções para remoção de elementos do vetor. Essas, no entanto, não alteram a capacidade do vetor, apenas seu tamanho. O funcionamento dessas funções é semelhante às anteriores.

// Remove o elemento do fim do vetor, decrementando size.
int vector_pop_back(vector* v);
// Remove o elemento na posição i, e move os posteriores para trás
int vector_erase(vector* v, int i);
// Remove o elemento na posição zero do vetor e move os posteriores para trás
int vector_pop_front(vector* v);

Atualizando o tamanho do vetor: resize

Sempre que um elemento for inserido no vetor, uma alteração no tamanho atual (size) é necessária.

void vector_resize(vector* v);

Se não há espaço adicional (entre size e capacity) é preciso realocar o vetor utilizando a função realloc de “stdlib.h”. Assumiremos que a nova capacidade será o dobro da atual, portanto, capacity *= 2. Observe que se a capacidade for inicializada com zero, esta atualização não funcionará, visto que a multiplicação por 2 manterá a capacidade em zero, nesses casos, assumiremos que a capacidade será inicializada por padrão em 4.

Imprimindo o conteúdo do vetor

void vector_print(vector* v);

Esta função auxiliar deverá imprimir o conteúdo do vetor obedecendo o seguinte formato:

[size/capacity] data[0] data[1] data[2] ... data[size] \n

Exemplo:

[6/10] 0 1 8 2 3 9

Verificando a validade de argumentos

Grande parte das funções de acesso e manipulação dos dados no vetor recebem como argumento um inteiro como índice. Para o contexto de vector, todo acesso que não esteja no intervalo $0 \leq i < \mbox{size}$ é inválido, pois extrapola os índices do vetor.

Há diversas formas de se verificar esse tipo de situação. Podemos, por exemplo, definir um condicional que verifique os limites de $i$

if (i >= 0 && i < v->size) {
    // Faz algo
}

No caso de vector, um acesso fora dos limites do vetor levaria a uma falha de segmentação durante a execução do programa. Um acesso desse tipo, em geral, é resultado de erro de programação, visto que não é razoável que alguém tente, deliberadamente, acessar uma região de memória que não lhe pertence. Portanto, acessos desse tipo são anômalos, e devem ser noticiados imediatamente.

Uma forma de se fazer isso, é utilizando a função assert(bool v) (requer “#include "). Esta é uma função bem simples, a qual aborta a execução do programa caso o argumento que ela receba não seja verdadeiro. O condicional definido anteriormente poderia ser substituído por:

assert(i >= 0 && i < v->size);

Neste caso, a linha após assert somente será alcançada caso a expressão i >=0 && i < v->size seja verdadeira. Caso contrário o programa será interrompido imediatamente (abort), e uma mensagem de erro exibida em tela, indicando a linha em que a condição do assert não foi atendida.

Generalizando o tipo vector

Até então tratamos de uma implementação vector cuja estrutura interna é baseada em um vetor de inteiros.

typedef struct {
    int* data;     // vetor que armazenará os inteiro;
    int  size;     // tamanho atual do vetor
    int  capacity; // tamanho reservado em memória 
} vector;

Porém, em grande parte dos casos, as mesmas funcionalidades implementadas poderiam ser úteis para outros tipos de dados. Como poderíamos alterar essa estrutura para que fosse mais fácil utilizá-la em outras situações? Ex.: para armazenar float ou char, etc.

Podemos definir um tipo de dados, com typedef e utilizá-lo em lugar de int. Ou seja

typedef int Type;

typedef struct {
    Type* data;     // vetor que armazenará os inteiro;
    int  size;     // tamanho atual do vetor
    int  capacity; // tamanho reservado em memória 
} vector;

Toda a referência ao tipo inteiro em elementos do vetor, são agora substituídos por Type. Deste modo para que se utilize a estrutura com um tipo de dados diferente, basta alterar a definição de Type, não sendo necessário alterar todo o código cada vez que se deseje utilizar vector com um tipo de dados diferente.

typedef float Type;
// Funções de remoção de elementos
Type vector_pop_back(vector* v);
Type vector_pop_front(vector* v);
Type vector_erase(vector* v, int i);
// Funções de inserção de elementos
void vector_push_back(vector* v, Type value);
void vector_push_front(vector* v, Type value);
void vector_insert(vector* v, Type value, int i);
...

Casos de teste

Um caso de teste é um conjunto de dados de entrada com a respectiva saída esperada. Há diversos meios de se implementar casos de testes (wiki/Teste_de_unidade), no entanto, para o nosso propósito isso será feito por meio de um arquivo de entrada, e um arquivo de saída. Considera-se que o programa passou em um determinado caso de teste, se, dado um arquivo de entrada, ele produz um arquivo de saída idêntico ao esperado.

Suponhamos o seguinte arquivo de entrada, o qual especifica um caso de teste.

6
6
push_front 13
push_back 49
push_back 29
push_back 5
push_front 26
pop_back

Após cada um desses comandos o vetor é impresso, seguindo um formato especificado descrito a seguir:

[1/6] 13 
[2/6] 13 49 
[3/6] 13 49 29 
[4/6] 13 49 29 5 
[5/6] 26 13 49 29 5 
[4/6] 26 13 49 29

A primeira linha do arquivo de entrada sempre inicializará o vetor, neste exemplo, ela requisita a inicialização com capacidade 6. A pŕoxima linha indica quantos comandos virão a seguir, neste exemplo temos 6 comandos, portanto a segunda linha contém o número 6.

A seguir desta linha, virão então 6 comandos, que serão lidos um a um. A cada comando lido, a função de mesmo nome deverá ser chamada no seu código com os parâmetros vindos do arquivo. Exemplo, a linha de entrada

push_front 13

Deverá disparar em seu código uma chamada à função

vector_push_front(v, 13);

Note que cada linha nessa saída é resultado de um dos comandos de entrada. Por exemplo, após o primeiro push_front 13, o vetor passa a ter tamanho 1 e capacidade 6, portanto foi impresso em tela a linha

[1/6] 13

Após o segundo push_back 49, o vetor passa a ter tamanho 2 e capacidade ainda é 6, portanto foi impresso em tela a linha

[2/6] 13 49