Ponteiros e Arrays

No primeiro post desta série, falamos um pouco sobre Ponteiros. No segundo, falamos de Referências. Hoje abordaremos a relação íntima (ui!) entre ponteiros e arrays (ou matrizes).

Relembrando Arrays

Um array, ou matriz, ou ainda um arranjo, é uma abstração matemática utilizada para representar um conjunto de dados homogêneos, ou seja do mesmo tipo (int, float, etc). Essa abstração é organizada em formato de tabela, com linhas e colunas. Cada elemento na matriz possui coordenadas únicas (linha e coluna), de forma que um dado elemento E(i,j) representa o único elemento na posição "linha i", "coluna j".

A sintaxe de declaração de matrizes segue abaixo:

// Matrizes unidimensionais ou vetores
int     ivet[10];               // 10 elementos, do 0 ao 9
char    cvet[23];               // 23 elementos, do 0 ao 22

// Matrizes bidimensionais
int     imat[2][3];             // 2 linhas (0 a 1) e 3 colunas (0 a 2)
double  dmat[10][2];            // 10 linhas (0 a 9) e 2 colunas (0 a 1)

Cada elemento da matriz é independente dos demais e pode ser acessado conforme a sintaxe abaixo:

int ivet[10];
int imat[3][4];

// Alterando o quarto elemento do vetor ivet.
// Lembre-se que começa-se a contar a partir do elemento zero
ivet[3] = 13;

// Lendo o segundo elemento do vetor ivet
int num = ivet[1];

// Alterando o elemento da primeira linha, segunda coluna de imat
imat[0][1] = 42;

// Lendo o elemento na terceira linha, quarta coluna de imat
int foo = imat[2][3];

Neste post não vamos discutir a fundo matrizes, vamos apenas investigar a relação entre matrizes e ponteiros de uma forma bastante intuitiva.

Tamanhos de matrizes

Dado que uma matriz é uma abstração que comporta vários valores de um mesmo tipo, qual o tamanho dela? Quanto espaço ele ocupa na memória?

Considere o código abaixo:

int     ivet[10];
char    cvet[13];
double  dvet[20];

char    cmat[3][4];
int     imat[5][4];

cout << "sizeof(int)     = " << sizeof(int) << endl;
cout << "sizeof(char)    = " << sizeof(char) << endl;
cout << "sizeof(double)  = " << sizeof(double) << endl;

cout << "sizeof(ivet)    = " << sizeof(ivet) << endl;
cout << "sizeof(cvet)    = " << sizeof(cvet) << endl;
cout << "sizeof(dvet)    = " << sizeof(dvet) << endl;
cout << "sizeof(cmat)    = " << sizeof(cmat) << endl;
cout << "sizeof(imat)    = " << sizeof(imat) << endl;

O resultado é bastante razoável. O Espaço ocupado por uma matriz é igual ao número de elementos multiplicado pelo tamanho do tipo do elemento (linhas x colunas x sizeof(tipo)). Ora, se cada elemento é independente, supõe-se que cada um ocupe um lugar separado na memória, caso contrário um elemento sobrescreveria outro. Sendo assim, será que cada elemento possui seu próprio endereço de memória?

Matrizes e endereços de memória

Para facilitar, vamos então analisar os possíveis endereços de uma matriz de caracteres, cujo tamanho de um dado único é 1 byte:

const int max = 5;
char cvet[max] = {'A', 'B', 'C', 'D', 'E'};

// Mostrando o índices, valores e endereços dos dados.
printf("Índice\tValor\tEndereço do elemento\n");
for (int i = 0; i < max; i++) {
    printf("%d\t%c\t%p\n", i, cvet[i], &cvet[i]);
}

// Mostrando o endereço da própria matriz
printf("Endereço da matriz: %p\n", &cvet);

// Mostrando o endereço da própria matriz denovo
printf("Endereço da matriz: %p\n", cvet);

Os endereços dos elementos são sequenciais, ou seja, cada elemento é armazenado ao lado do anterior. Adicionalmente existem dois fatos ainda mais interessantes:

  1. O endereço do array (&cvet), mostrado na linha 25, é o mesmo do primeiro elemento do array;
  2. A própria variável cvet pode ser interpretada como um ponteiro, como é mostrado na linha 28;

Em C++, um array comum é um bloco contíguo de memória cujo nome pode ser interpretado (cast) como um ponteiro que aponta para o seu primeiro elemento. Adicionalmente é válido fazer um ponteiro apontar para um array desde que o ponteiro destino seja para o mesmo tipo que o tipo dos elementos do array. Durante a atrubuição de um array a um ponteiro, o compilador faz uma conversão implícita de tipos. O ponteiro destino passa a ser interpretado como um ponteiro para a área de memória ocupada pelo array.

Uma das consequências não tão óbvias é que durante o cast implícito, é perdida a informação de que aquela área de memória era um array. Portanto é perdida a informação do tamanho do array. Do ponto de vista do ponteiro, ele está apontando para o começo de um bloco arbitrário de memória, de um tamanho também arbitrário. Sair de um array e ir para um ponteiro significa ir de uma abstração mais restritiva e mais alto nível, para um abstração menos restritiva e mais baixo nível.

Por outro lado tentar atribuir um ponteiro a um array gera um erro de compilação por tipos incompatíveis. Um array é um bloco de memória de n dados (bytes), já um ponteiro possui apenas um dado, um endereço. O compilador não tem como saber de antemão se um ponteiro aponta para uma área de 1, 2 ou 200 bytes.

const int max = 300;
char cvet[max];
char* pc = 0;

printf("\nAntes da atribuição\n");
printf("cvet = %p\n", cvet);
printf("pc   = %p\n", pc);
printf("sizeof(cvet) = %lu\n", sizeof(cvet));
printf("sizeof(pc)   = %lu\n", sizeof(pc));

pc = cvet;

printf("\nDepois da atribuição\n");
printf("cvet = %p\n", cvet);
printf("pc   = %p\n", pc);
printf("sizeof(cvet) = %lu\n", sizeof(cvet));
printf("sizeof(pc)   = %lu\n", sizeof(pc));

Note que antes da atribuição (linha 25) o ponteiro pc. está nulo, pois foi inicializado assim. Já os tamanhos indicam que o array possui 300 bytes e o ponteiro apenas 8 (minha máquina é um amd 64). Após a atribuição ambos passam a "apontar" para a mesma área de memória, porém os tamanhos não mudam. Houve um cast implicito de char[300] para char*, e nessa brincadeira o ponteiro pc não tem como saber o tamanho da área de memória para o qual ele aponta. Já o array cvet continua sabendo direitinho o que ele é, sem nenhuma crise existencial.

Aritmética de ponteiros - Vulgo, e daí?

Ora, mas se eu sei que os dados numa matriz estão dispostos lado a lado, eu posso utilizar um ponteiro que vai pulando para o endereço ao lado e acessando o elemento seguinte. O nome disso é aritimética de ponteiros.

const int max = 6; 
char cvet[max] = {'B','L','A','B','O','S'};

char* pc = cvet;

for (int i = 0; i < max; i++) {
    printf("%c", *(pc + i));
}
printf("\n");

for (int i = 0; i < max; i++) {
    printf("%c", *pc++);
}
printf("\n");


// Agora com inteiros
int ivet[max] = {1, 2, 3, 4, 5, 6};
int* pi = ivet;

for (int i = 0; i < max; i++) {
    printf("%p = %d\n", pi, *pi++);
}
printf("\n");

// Em duas dimensões
char cmat[2][3] = {{'B','L','A'},{'B','O','S'}};
char* ppc;

ppc = (char*)cmat;

for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 3; j++) {
        printf("%c", *(ppc + 3*i+j));
    }
    printf("\n");
}
printf("\n");

Na linha 18 o ponteiro pc passa a pontar para o array cvet, e consequentemente para o seu primeiro elemento, o caracter 'B'. Na linha 21 o conteúdo de pc, que é o endereço onde foi armazenado o caracter 'B', é incrementado de i e em seguida de-referenciado. Na primeira passada o valor de i é zero, portanto é dereferenciado para o valor 'B'. Nos passos seguintes, o endereço seguinte vai sendo de-referenciado para os outros caracteres armazenados no array original. É mais ou menos isso que internamente o compilador faz quando você utiliza a sintaxe cvet[i]. A abstração de array te dá uma forma mais amigável de tratar áreas contíguas de memória do que *(pc + i).

Mas se a abstração de array é mais simples, pra que utilizar aritmética de ponteiros?

Uma das respostas está a linha 26. Ela faz a mesma coisa que a linha 21, porém um pouco mais rápido. Na sintaxe da linha 21, ou de forma semelhante, na sintaxe de array, o acesso a um dado qualquer pode ser resumido de forma bem grosseira nos comandos:

  1. Tome o endereço base do array;
  2. Adicione ao endereço o valor do índice;
  3. De-referencie este novo endereço;

Já com aritmética de ponteiro ficaria assim:

  1. De-referencie este endereço;

O comando incremento (ou a conta feita com endereços) não vou contar porque é parte do loop, embora i++; seja mais rápido que a = b + c;. Agora imagine esse pequeno ganho de 66% aplicado em uma área de dados de 1 MB. Serão mais de 2 milhões de comandos a menos!

A técnica de utilizar um ponteiro para manipular uma área arbitrária de memória é utilizada geralmente em programação de baixo nível (mais próximo da máquina), manipulação de buffers e strings, entre outros truques sujos. Nas entranhas dos computadores, operações que varrem extensas áreas de memória, frequentemente são realizadas com aritimética de ponteiros. Nesse nível, Darwin reina supremo e só os mais preparados sobrevivem. A partir daqui a linguagem começa a dar um poder que só os puros de coração conseguem compreender.

Uma observação importante é que entre as linhas 31 e 38 a experiência é repetida com inteiros. Note que como os inteiros possuem 4 bytes, os incrementos são automaticamente feitos de 4 em 4 bytes, e não de 1 em 1, ou seja o incremento é automaticamente calculado para sizeof(tipo). Incrementar um ponteiro significa acessar a próxima área de memória semelhante ao dado atual, e não apenas o próximo endereço. Como o tamanho de um char é um byte, quando incremetamos um ponteiro para char, avançamos apenas 1 byte. Se incrementarmos um ponteiro para double, avançaremos 8 bytes, e assim por diante.

Outra observação é que uma matriz bidimensional pode ser "linearizada" conforme é mostrado nas linhas 40 a 52. Isso é útil, quando aplicável, para aproveitar melhor o cache do processador, por exemplo.

void*, o Pansexual dos ponteiros

Anteriormente eu disse que só era possível atribuir um array a um ponteiro que fosse para o mesmo tipo que os dados do array. Eu menti descaramente! O motivo, é que para alguém que desistiu do post antes deste tópico, é mais seguro acreditar que não pode :) !

Existem duas exceções à regra. A primeira é quando há uma conversão explícita de tipos e o ponteiro destino "acha" que está apontando para o tipo certo. Um exemplo está na linha 44 do código anterior.

A segunda é o caso dos ponteiros para void. Um ponteiro para void é um ponteiro que não faz exigências quanto ao tipo de dados que está na área de memória para o qual ele aponta. Ele é um ponteiro pra uma área genérica de memória, algo bem baixo nível.

Para utilizar um dado apontado por um ponteiro para void, antes de de-referenciá-lo, é preciso fazer um cast explícito para algum tipo válido, pois se um int* é de-referenciado para int e um char* é de-referenciado para char, adivinhe para que é de-referenciado um void*?

const int max = 6; 
char cvet[max] = {'B','L','A','B','O','S'};

void* pv = cvet;

// Erro de compilação.
//*pv
// Quanto vale sizeof(void)?

for (int i = 0; i < max; i++) {
    printf("%c", *(((char*)pv) + i));
}
printf("\n");

Ponteiro para void são utilizados quando precisa-se apontar para uma área genérica de memória sem ter controle/conhecimento do tipo de dados que essa área contém, ou em funções que não podem fazer suposições sobre os tipos de seus parâmetros, como é o caso da API da lib pthreads (link arbitrário).

Encerrando

Quanto mais nos aprofundamos nos tópicos sobre ponteiros, mais próximos da máquina ficamos. Boa parte do poder das linguagens C e C++ provém daí, e boa parte dos problemas também. A complexidade vai aumentando e os riscos também. Para muitos é aí que mora a diversão!

Links