Programação Básica 06 - Ponteiros

Os ponteiros são um tipo de variável especial do C/C++. Eles possuem diversas aplicações, sendo a mais comum a implementação de estruturas dinâmicas.

O que é um ponteiro?

Antes de introduzir os ponteiros, é necessário definir algumas coisas.

• bit: Um bit é a menor unidade de informação que um computador armazena, ele representa apenas dois estados: $0$ e $1$.
• byte: Um byte é simplesmente um conjunto de $8$ bits, como cada bit pode representar $2$ valores e um byte é formado por $8$ bits nós podemos representar $2^8 = 256$ valores distintos com um byte. Normalmente representamos os números de $[0, 255]$.

Uma variável do tipo $int$ no C/C++ é formado por $4$ bytes $=$ $32$ bits, já o $long$ $long$ é formado por $8$ bytes $=$ $64$ bits.

Nós podemos imaginar a memória como sendo uma lista de bytes, toda vez que declaramos um $int$ o computador escolhe uma posição da memória e reserva $4$ bytes pra colocar o inteiro.

Utilizando o operador $\&$ é possível saber em que posição da memória a variável está localizada.

O ponteiro é uma váriavel que recebe uma posição na memória, por isso dizemos que ele “aponta” para uma variável. Utilizando o ponteiro podemos alterar o valor que está escrito na posição da memória que ele aponta, ou seja, podemos alterar uma variável usando um ponteiro.

Aplicação simples de ponteiro

Observe o seguinte código:

Mesmo chamando a função modifica para a variável $x$ o valor dela não é alterado, isso ocorre pois quando passamos uma variável para uma função é criada uma cópia dela, então a variável original não é modificada.

A solução para esse problema é usar ponteiros, pois será criada uma cópia do ponteiro ao invés de uma cópia da variável, e a cópia do ponteiro continua apontando para a mesma variável que o ponteiro inicial, logo é possível modificar a variável.

Caso você tenha o costume de usar scanf/printf você já deve ter visto o operador $\&$ sendo utilizado no scanf, isso ocorre justamente porquê é necessário modificar o valor da variável no scanf, então é passado um ponteiro como argumento da função.

Relação entre vetores e ponteiros

De forma simplificada, vetores são valores colocados em sequência na memória, a posição $1$ de um vetor está exatamente uma posição na frente na memória da posição $0$, assim como a $2$ está uma na frente da $1$.

É possível visualizar que as posições de um vetor são consecutivas na memória usando o seguinte código:

Uma coisa importante é que quando escrevemos $vet$ sem colocar nenhum colchete nós já temos um ponteiro pra primeira posição do vetor, ou seja, ao invés de escrever $\&vet[0]$ podemos colocar simplesmente $vet$. Embora isso pareça estranho você provavelmente já utilizou várias vezes sem perceber, um exemplo é na função sort.

A função sort recebe um ponteiro para a primeira posição do vetor e um ponteiro para a primeira posição que não está no vetor, ou seja, uma posição depois da última do vetor. Com esses ponteiros ele consegue saber qual intervalo você deseja ordenar.

Alocação dinâmica de ponteiros

Imagine que nós queremos criar um ponteiro sem precisar de uma variável ligada a ele (isso pode parecer sem sentido por enquanto mas será útil na pŕoxima seção), para isso nós podemos criar uma função que cria uma variável e retorna o endereço dela pro ponteiro.

O problema é que toda vez que uma função acaba, as variáveis dentro dela são destruídas da memória, então esse nosso ponteiro estará apontando para uma posição inválida e provavelmente fará o programa travar se tentarmos acessar ele.

A solução disso são os operadores new e delete do C++. Com eles é possível criar novas variáveis dinamicamente e que não são destruídas quando a função termina.

Quando o programa termina, a memória das variáveis criadas com o new são deletadas automaticamente, então nem sempre é um problema esquecer de liberar a memória. Mas, caso você crie várias variáveis usando o new e não use o delete é criado um lixo de memória. Em programas simples isso normalmente não é um problema, mas caso o lixo de memória fique muito grande ele pode ocupar toda a memória do programa e causar um Runtime Error.

Estruturas dinâmicas com ponteiros

Estruturas dinâmicas são a principal aplicação de ponteiro em programação competitiva, usando eles é possível criar estruturas de dados que mudam de tamanho utilizando as funções new e delete. Um exemplo disso são estruturas como o vector e o set fazem o uso de ponteiros para inserir e deletar elementos.

Nesta aula, iremos implementar uma pilha dinâmica. A pilha é uma estrutura de dados simples onde você insere e remove elementos no topo da pilha. Iremos implementar as seguintes funções:

• push: Insere um elemento no topo da pilha.
• pop: Remove o elemento no topo da pilha.
• top: Pega o valor do elemento no topo da pilha.

A nossa estrutura funcionará assim: O topo da pilha será o nó principal e ele terá um nó filho que aponta para o próximo elemento da pilha. As operações vão funcionar da seguinte maneira:

• push: Cria um novo nó e transforma ele no topo da pilha, o antigo
  topo da pilha vira filho do novo nó.
• pop: Apaga o nó no topo da pilha e faz o novo topo ser o filho dele,
  que é o próximo elemento da pilha.
• top: Pega o valor que está guardado no nó principal.

A animação a seguir mostra as operações funcionando na pilha:

Segue a implementação da pilha em C++ usando ponteiros:

É extremamente cansativo ter que utilizar $(^{*}T).val$ toda vez que quisermos acessar o elemento val contido no ponteiro, para evitar isso podemos utilizar o operador $(\rightarrow)$, que faz exatamente a mesma coisa e elimina a necessidade do uso do asterisco, podemos escrever da seguinte forma: $(^{*}T).val = T \rightarrow val$. Isso faz com que a implementação da pilha fique bem mais limpa.