Arrays (avançado)

Arrays (avançado)

Introducao

ola, sejam bem vindos à aula de arrays avançado. Nessa aula vamos discutir um pouco sobre arrays em memória, da forma que são implementados em lingiagens baixo nível como C. De quebra você ainda vai aprender um pouco sobre ponteiros.

Com esse conhecimento você será capaz de ter uma ideia de como array são implementados na sua linguagem de programação favorita.

A memória

Array: uma região contígua de memória

Arrays são uma regiao contigua na memoria.

Ao escrevermos o programa

int main(void) {
    int ages[3];

    return 0;
}

Compilamos e nosso código já sabe que vai precisar de uma região contígua de memória capaz de guardar três inteiros. Isso é útil quando se sabe previamente quantos itens precisaremos.

Mas nem sempre é assim. As vezes é preciso um nível de dinamicidade. É aí que o que conhecemos como Arrays dinamicos entram em cena.

Arrays Dinamicos

Suponha que estou coletando informações das turmas de uma escola para calcular a média de idade. Nem todas as turmas possuem a mesma quantidade de alunos. Então precisamos de algo mais flexível.

Devemos entao lembra que array é ma regiao contigua de memoria e para termos essa regiao contigua precisamos somente de:

• espaco (mas isso é garantido pelo SO);
• o primeiro endereco daquele array;
• quantos itens ele possui.

Assim, se o array está na posição 100, para pegar o primeiro item basta ler a quantidade de memória, o tamanho de cada item. Para pegar o segundo uso o tamanho ainda, só que agora com o shift de 1.

int main(void) {
    int *ages = malloc(sizeof(int) * 3);

    return 0;
}

Capacidade e tamanho

Para termos arrays que podem crescer dinamicamente de fato precisamos dos conceitos de capacidade e tamanho.

Nesse contexto, nosso array de inteiros passa agora a ter metadados. Por isso podemos criar uma struct.

A capacidade de um array determina o numero maximo de elementos que aquele array pode ter. O tamanho, é a quantidade de items que o array possui.

Assim, é possível ter um array de capacidade 3 com apenas 1 item. Em Go esses conceitos ficam mais explícitos com slices.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *items; // TODO: make this a void pointer to allow for any type
    int capacity;
    int length;
} my_array;

my_array* create_array(int capacity) {
    my_array *arr = malloc(sizeof(my_array));

    if (arr == NULL) exit(1);

    arr->length = 0;
    arr->capacity = capacity;
    arr->items = malloc(sizeof(int) * capacity);

    return arr;
}

void push_item(my_array *arr, int value) {
    if (arr->length + 1 > arr->capacity) {
        arr->items = realloc(arr->items, sizeof(int) * arr->capacity * 2);
        arr->capacity *= 2;
    }

    arr->items[arr->length] = value;
    arr->length += 1;
}

/*
    Após remover o elemento no indice 'x', é feito o shift. Por isso essa operação em um array dinâmico é O(n)
*/
int remove_at(my_array *arr, int index) {
    // TODO: assert this is a valid index
    int removed_elem = arr->items[index];

    for (int i = index; i < arr->length - 1; i++) {
        arr->items[i] = arr->items[i + 1];
    }

    putchar('\n');

    arr->items[arr->length] = -1;
    arr->length -= 1;

    return removed_elem;
}

void clean_array(my_array *arr) {
    free(arr->items);
    free(arr);
}

void print_arr(my_array *arr) {
    printf("Array has %d items\n"
            "Capacity of array %d\n"
            "Starts at %p\n----------\n", arr->length, arr->capacity, arr);

    for (int i = 0; i < arr->length; i++) {
        printf("arr[%d] has the value %d\n", i, arr->items[i]);
    }

    puts("\n\n");
}

int main(void) {
    my_array *arr = create_array(3);

    push_item(arr, 1);
    push_item(arr, 2);
    push_item(arr, 3);

    /* print_arr(arr); */

    push_item(arr, 4);

    print_arr(arr);

    remove_at(arr, 0);

    print_arr(arr);

    remove_at(arr, 1);

    print_arr(arr);

    return 0;
}

Arrays em ruby

Noss array, embora dinâmico, guarda apenas números ineiros. Na linguagem que estamos utilizando, podemos ter valores dinâmicos.

Em Ruby, o que temos é um VALUE que representa qualquer coisa. Pois é um endereço de memória para algum valor. Para fazer isso alguns metadados de suporte são necessários.

A ideia é parecida com o que fizemos.

Conclusao

É isso, espero que você tenha gostado. Nos vemos na próxima aula.

Excercicios

1. Implemente a funcao insert_at que insere um elemento em um array dinamico em uma determinada posição.
2. Implemente a funcao remove que remove um elemento de um array dinamico.

Ruby alocando objetos: https://github.com/ruby/ruby/blob/8ad5dd79980dbc16753839526190ea5633d31c72/string.c#L990