C Array que Cresce

Um array comum tem tamanho fixo: double precos[5]; guarda cinco preços, nem um a mais. Mas a lista de compras da Ana não tem tamanho fixo: num dia são três itens, no mês de festa são quarenta. Nesta aula você vai juntar o que aprendeu em malloc e free e calloc e realloc para montar um array que cresce sozinho conforme os itens chegam. É uma das peças mais usadas de todo programa em C (e é o que o list do Python e o vector do C++ fazem por baixo dos panos).

Todos os programas desta aula foram compilados com o gcc 15.2 na máquina fictícia da Ana (usuária ana, computador notebook), na pasta ~/c, com o comando padrão do guia: gcc -std=c23 -Wall -Wextra arquivo.c -o programa (veja Compilar com gcc). Você pode repetir cada um no editor do guia.

A ideia: o caderno que lota

A Ana anota as compras num caderno pequeno, de 4 linhas. Enquanto há linha livre, ela só escreve. Quando o caderno lota, ela compra um caderno maior, copia as anotações para ele e joga o pequeno fora. Daí em diante, continua escrevendo no novo.

Repare em dois números diferentes:

• quantas linhas estão escritas (o tamanho da lista);
• quantas linhas o caderno tem (a capacidade).

Enquanto o tamanho é menor que a capacidade, escrever é fácil. Quando os dois ficam iguais, é hora de trocar de caderno.

O realloc (de re-allocate, "reservar de novo") faz exatamente a troca de caderno: reserva um bloco maior, copia o conteúdo do antigo e libera o antigo. Às vezes ele consegue até "esticar" o bloco no mesmo lugar, sem copiar nada. Você não precisa saber qual dos dois aconteceu: só precisa usar o ponteiro que ele devolve.

1. A primeira versão: crescer de um em um

Comece com três variáveis: o ponteiro para a memória, o tamanho e a capacidade. No começo não existe memória nenhuma: o ponteiro vale NULL e os dois números valem zero. A cada item novo, se a lista estiver lotada, o programa pede espaço para mais um.

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

int main(void) {
    double *precos = NULL;
    size_t tamanho = 0;
    size_t capacidade = 0;

    double novos[] = {12.50, 4.99, 7.80, 3.25, 9.90};

    for (size_t i = 0; i < 5; i++) {
        if (tamanho == capacidade) {
            size_t nova = capacidade + 1;
            double *maior = realloc(precos, nova * sizeof(double));
            if (maior == NULL) {
                printf("Sem memória!\n");
                free(precos);
                return 1;
            }
            precos = maior;
            capacidade = nova;
            printf("Cresceu: agora cabem %zu\n", capacidade);
        }
        precos[tamanho] = novos[i];
        tamanho++;
    }

    for (size_t i = 0; i < tamanho; i++) {
        printf("Item %zu: R$ %.2f\n", i + 1, precos[i]);
    }

    free(precos);
    return 0;
}

double *precos = NULL;

O "caderno". Começa sem memória nenhuma. Iniciar com NULL é importante: o realloc aceita NULL e, nesse caso, funciona igual a um malloc.

size_t tamanho = 0; size_t capacidade = 0;

Quantos itens estão guardados e quantos cabem. As três variáveis andam sempre juntas: mexeu numa, confira as outras.

if (tamanho == capacidade)

A lista lotou (ou ainda nem existe, quando os dois valem 0). Só nesse caso é preciso crescer.

size_t nova = capacidade + 1;

A nova capacidade: um lugar a mais. (Daqui a pouco você vai trocar esta linha.)

double *maior = realloc(precos, nova * sizeof(double));

Pede um bloco com espaço para nova preços. O tamanho é em bytes, por isso o * sizeof(double). O resultado vai para uma variável nova, maior, e não direto para precos: a seção 4 explica por quê.

if (maior == NULL) { … }

O realloc devolve NULL quando não há memória. Nesse caso o bloco antigo continua intacto em precos, e o programa ainda pode liberá-lo antes de sair.

precos = maior; capacidade = nova;

Deu certo: agora o caderno é o novo bloco, e a capacidade é a nova.

precos[tamanho] = novos[i]; tamanho++;

Guarda o item na primeira posição livre (a posição tamanho) e conta mais um. Depois de crescer, sempre existe essa posição livre.

free(precos);

Um único free no fim: o realloc já liberou cada bloco antigo quando trocou de caderno.

$ gcc -std=c23 -Wall -Wextra cresce1.c -o cresce1
$ ./cresce1
Cresceu: agora cabem 1
Cresceu: agora cabem 2
Cresceu: agora cabem 3
Cresceu: agora cabem 4
Cresceu: agora cabem 5
Item 1: R$ 12.50
Item 2: R$ 4.99
Item 3: R$ 7.80
Item 4: R$ 3.25
Item 5: R$ 9.90

Funciona. Mas repare: cinco itens, cinco trocas de caderno. É como comprar um caderno novo, com uma linha a mais, toda vez que você anota uma compra. Para cinco itens, tudo bem. Para mil, a conta fica feia.

2. Dobrar a capacidade

O truque usado em praticamente toda biblioteca é: quando lotar, dobre a capacidade. Começando com 4 lugares, o caderno vai para 8, depois 16, 32, 64… Cada troca dá espaço para muitos itens novos. Só uma linha muda:

            size_t nova = (capacidade == 0) ? 4 : capacidade * 2;

O operador ternário diz: "se a capacidade é zero (a lista ainda não existe), comece com 4; senão, dobre". Sem esse cuidado, 0 * 2 daria zero, e a lista nunca cresceria. Com dez preços:

$ gcc -std=c23 -Wall -Wextra dobra.c -o dobra
$ ./dobra
Cresceu: agora cabem 4
Cresceu: agora cabem 8
Cresceu: agora cabem 16
Item 1: R$ 12.50
Item 2: R$ 4.99
Item 3: R$ 7.80
Item 4: R$ 3.25
Item 5: R$ 9.90
Item 6: R$ 6.40
Item 7: R$ 2.15
Item 8: R$ 15.00
Item 9: R$ 8.75
Item 10: R$ 1.99

Dez itens, só três trocas. No fim sobram 6 lugares vazios (capacidade 16, tamanho 10): é o preço de crescer depressa, e é um preço pequeno.

A diferença com mil itens

Este programa guarda os números de 0 a 999 em duas listas, uma crescendo de um em um e outra dobrando, e conta quantas vezes cada uma chamou o realloc:

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

int main(void) {
    int *a = NULL, *b = NULL;
    size_t cap_a = 0, cap_b = 0;
    int vezes_a = 0, vezes_b = 0;

    for (size_t n = 0; n < 1000; n++) {
        if (n == cap_a) {                    /* estratégia 1: +1 */
            cap_a = cap_a + 1;
            int *novo = realloc(a, cap_a * sizeof(int));
            if (novo == NULL) { free(a); free(b); return 1; }
            a = novo;
            vezes_a++;
        }
        a[n] = (int)n;

        if (n == cap_b) {                    /* estratégia 2: dobrar */
            cap_b = (cap_b == 0) ? 4 : cap_b * 2;
            int *novo = realloc(b, cap_b * sizeof(int));
            if (novo == NULL) { free(a); free(b); return 1; }
            b = novo;
            vezes_b++;
        }
        b[n] = (int)n;
    }

    printf("1000 itens com +1:     %d realocações (capacidade final %zu)\n", vezes_a, cap_a);
    printf("1000 itens dobrando:   %d realocações (capacidade final %zu)\n", vezes_b, cap_b);
    free(a);
    free(b);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra conta.c -o conta
$ ./conta
1000 itens com +1:     1000 realocações (capacidade final 1000)
1000 itens dobrando:   9 realocações (capacidade final 1024)

Mil contra nove. E cada realocação pode copiar a lista inteira: crescendo de um em um, no pior caso o computador copia 0 + 1 + 2 + … + 999 = 499.500 números; dobrando, copia no máximo 4 + 8 + 16 + … + 512 = 1.020. Com um milhão de itens, a primeira estratégia vira uma eternidade; a segunda continua instantânea.

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

int main(void) {
    double *precos = NULL;
    size_t tamanho = 0;
    size_t capacidade = 0;
    int realocacoes = 0;

    for (int i = 1; i <= 10; i++) {
        if (tamanho == capacidade) {
            size_t nova = capacidade + 1;   /* troque esta linha */
            double *maior = realloc(precos, nova * sizeof(double));
            if (maior == NULL) {
                free(precos);
                return 1;
            }
            precos = maior;
            capacidade = nova;
            realocacoes++;
        }
        precos[tamanho] = i * 1.5;
        tamanho++;
    }

    printf("Itens: %zu\n", tamanho);
    printf("Realocações: %d\n", realocacoes);
    printf("Capacidade final: %zu\n", capacidade);
    free(precos);
    return 0;
}

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

int main(void) {
    double *precos = NULL;
    size_t tamanho = 0;
    size_t capacidade = 0;
    int realocacoes = 0;

    for (int i = 1; i <= 10; i++) {
        if (tamanho == capacidade) {
            size_t nova = (capacidade == 0) ? 4 : capacidade * 2;
            double *maior = realloc(precos, nova * sizeof(double));
            if (maior == NULL) {
                free(precos);
                return 1;
            }
            precos = maior;
            capacidade = nova;
            realocacoes++;
        }
        precos[tamanho] = i * 1.5;
        tamanho++;
    }

    printf("Itens: %zu\n", tamanho);
    printf("Realocações: %d\n", realocacoes);
    printf("Capacidade final: %zu\n", capacidade);
    free(precos);
    return 0;
}

3. Guardar tudo em funções: adicionar e liberar

Copiar aquele bloco do if em todo lugar que acrescenta um item seria pedir para errar. O certo é escrever a lógica uma vez, numa função. O problema: a função precisa mudar as três variáveis do main (o ponteiro, o tamanho e a capacidade). Como você viu em Passar por Ponteiro, para uma função mudar uma variável de fora, ela recebe o endereço da variável. E o endereço de um ponteiro é um ponteiro para ponteiro: double **.

De quebra, este programa lê os preços do teclado (ou de um arquivo) até a entrada acabar. É a situação em que o array que cresce brilha: ninguém sabe de antemão quantos preços vão chegar.

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

bool adicionar(double **precos, size_t *tamanho, size_t *capacidade, double valor) {
    if (*tamanho == *capacidade) {
        size_t nova = (*capacidade == 0) ? 4 : *capacidade * 2;
        double *maior = realloc(*precos, nova * sizeof(double));
        if (maior == NULL) {
            return false;
        }
        *precos = maior;
        *capacidade = nova;
    }
    (*precos)[*tamanho] = valor;
    (*tamanho)++;
    return true;
}

void liberar(double **precos, size_t *tamanho, size_t *capacidade) {
    free(*precos);
    *precos = NULL;
    *tamanho = 0;
    *capacidade = 0;
}

int main(void) {
    double *precos = NULL;
    size_t tamanho = 0;
    size_t capacidade = 0;

    double preco;
    while (scanf("%lf", &preco) == 1) {
        if (!adicionar(&precos, &tamanho, &capacidade, preco)) {
            printf("Sem memória!\n");
            break;
        }
    }

    double total = 0.0;
    for (size_t i = 0; i < tamanho; i++) {
        total += precos[i];
    }
    printf("%zu itens (capacidade %zu)\n", tamanho, capacidade);
    printf("Total: R$ %.2f\n", total);

    liberar(&precos, &tamanho, &capacidade);
    return 0;
}

Para testar, a Ana passa seis preços pelo printf com um pipe e depois dez preços num arquivo:

$ gcc -std=c23 -Wall -Wextra -g carrinho.c -o carrinho
$ printf '12.50\n4.99\n7.80\n3.25\n9.90\n6.40\n' | ./carrinho
6 itens (capacidade 8)
Total: R$ 44.84
$ cat compras.txt
12.50 4.99 7.80
3.25 9.90
6.40 2.15 15.00 8.75 1.99
$ ./carrinho < compras.txt
10 itens (capacidade 16)
Total: R$ 72.73

O -g no comando guarda os números das linhas dentro do programa, para o valgrind (logo abaixo) dizer em qual linha está cada problema.

Conferindo com o valgrind

O valgrind roda o programa e vigia cada byte reservado (veja Valgrind). A opção --leak-check=full pede o relatório completo de vazamentos:

$ valgrind --leak-check=full ./carrinho < compras.txt
==29259== Memcheck, a memory error detector
==29259== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.
==29259== Using Valgrind-3.26.0 and LibVEX; rerun with -h for copyright info
==29259== Command: ./carrinho
==29259==
10 itens (capacidade 16)
Total: R$ 72.73
==29259==
==29259== HEAP SUMMARY:
==29259==     in use at exit: 0 bytes in 0 blocks
==29259==   total heap usage: 5 allocs, 5 frees, 8,416 bytes allocated
==29259==
==29259== All heap blocks were freed -- no leaks are possible        « nenhum vazamento
==29259==
==29259== For lists of detected and suppressed errors, rerun with: -s
==29259== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

All heap blocks were freed -- no leaks are possible = "todos os blocos do heap foram liberados; vazamento impossível". E 0 errors: nenhum acesso fora do lugar. Os 5 allocs são as 3 vezes que a lista cresceu (4, 8 e 16 lugares) mais 2 blocos que o próprio scanf/printf reservam para a entrada e a saída (e que eles mesmos liberam no fim).

Agora, sem a linha do liberar (arquivo vaza.c):

$ valgrind --leak-check=full ./vaza < compras.txt
«… cabeçalho igual …»
10 itens (capacidade 16)
Total: R$ 72.73
==29331==
==29331== HEAP SUMMARY:
==29331==     in use at exit: 128 bytes in 1 blocks
==29331==   total heap usage: 5 allocs, 4 frees, 8,416 bytes allocated
==29331==
==29331== 128 bytes in 1 blocks are definitely lost in loss record 1 of 1
==29331==    at 0x485807F: realloc (vg_replace_malloc.c:1804)
==29331==    by 0x400125A: adicionar (vaza.c:7)
==29331==    by 0x4001359: main (vaza.c:33)
==29331==
==29331== LEAK SUMMARY:
==29331==    definitely lost: 128 bytes in 1 blocks
«…»
==29331== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

128 bytes in 1 blocks are definitely lost = "128 bytes num bloco estão definitivamente perdidos". São os 16 lugares × 8 bytes de cada double: o último caderno, que ninguém jogou fora. As linhas de baixo dizem onde ele nasceu: no realloc da linha 7, dentro de adicionar, chamado pela linha 33 do main. Os cadernos menores não aparecem: o próprio realloc liberou cada um deles na troca. Mais sobre isso em Vazamentos de Memória.

4. O jeito seguro de chamar realloc

Muita gente escreve assim, numa linha só:

precos = realloc(precos, nova * sizeof(double));   /* NÃO faça assim */

Funciona enquanto há memória. Mas quando o realloc falha, ele devolve NULL e não libera o bloco antigo (isso é de propósito, para você não perder os dados). Só que a linha acima guarda esse NULL em precos, por cima do único endereço que existia do bloco antigo. A lista continua lá na memória, mas ninguém mais sabe onde: não dá para usar nem para liberar.

Para ver acontecer, este programa pede, de propósito, espaço para um trilhão de preços (8 terabytes). O número vem da linha de comando (argv) só para o gcc não perceber o absurdo na hora de compilar:

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

int main(int argc, char *argv[]) {
    size_t capacidade = 4;
    double *precos = malloc(capacidade * sizeof(double));
    if (precos == NULL) {
        return 1;
    }
    precos[0] = 12.50;

    /* um pedido grande demais, de propósito, para o realloc falhar */
    capacidade = (argc > 1) ? strtoull(argv[1], NULL, 10) : 8;

    precos = realloc(precos, capacidade * sizeof(double));
    if (precos == NULL) {
        printf("O realloc falhou. E a lista antiga?\n");
        return 1;
    }
    printf("Primeiro item: R$ %.2f\n", precos[0]);
    free(precos);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra -g perdeu.c -o perdeu
$ ./perdeu
Primeiro item: R$ 12.50
$ valgrind --leak-check=full ./perdeu 1000000000000
«… cabeçalho …»
O realloc falhou. E a lista antiga?
==31796==
==31796== HEAP SUMMARY:
==31796==     in use at exit: 32 bytes in 1 blocks
==31796==   total heap usage: 3 allocs, 2 frees, 8,000,000,004,128 bytes allocated
==31796==
==31796== 32 bytes in 1 blocks are definitely lost in loss record 1 of 1
==31796==    at 0x4850858: malloc (vg_replace_malloc.c:447)
==31796==    by 0x4001213: main (perdeu.c:6)
«…»

Os 32 bytes (4 preços de 8 bytes) do malloc da linha 6 ficaram perdidos: o NULL apagou o endereço deles. A forma segura usa uma variável a mais, como todos os exemplos desta aula:

double *maior = realloc(precos, nova * sizeof(double));
if (maior == NULL) {
    /* precos ainda aponta para a lista antiga, inteira:
       dá para avisar, salvar, liberar ou continuar sem o item novo */
    free(precos);
    return 1;
}
precos = maior;          /* só troca quando deu certo */
capacidade = nova;

Formas de crescer: qual usar

Qual usar: dobre. Se você já sabe quantos itens vêm (por exemplo, leu a quantidade antes), reserve tudo de uma vez com malloc e nem precisa crescer. E se a lista nunca passa de um tamanho pequeno e conhecido, um array comum (double precos[50];) continua sendo o mais simples.

Quando dá errado

        double *maior = realloc(*precos, nova);   /* faltou * sizeof(double) */

$ gcc -std=c23 -Wall -Wextra -g -fsanitize=address semsizeof.c -o semsizeof
$ ./semsizeof < compras.txt
=================================================================
==30440==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x73853f7e0010 at pc 0x5e54d7d4c47e bp 0x7ffe2eaa3ea0 sp 0x7ffe2eaa3e90
WRITE of size 8 at 0x73853f7e0010 thread T0
    #0 0x5e54d7d4c47d in adicionar /home/ana/c/semsizeof.c:14
    #1 0x5e54d7d4c6e8 in main /home/ana/c/semsizeof.c:33
«…»
0x73853f7e0014 is located 0 bytes after 4-byte region [0x73853f7e0010,0x73853f7e0014)
allocated by thread T0 here:
    #0 0x77654092a6cf in realloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:81
    #1 0x5e54d7d4c399 in adicionar /home/ana/c/semsizeof.c:7
«…»

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

int main(void) {
    size_t capacidade = 4;
    double *precos = malloc(capacidade * sizeof(double));
    if (precos == NULL) {
        return 1;
    }
    precos[0] = 12.50;

    double *primeiro = &precos[0];

    capacidade = capacidade * 2;
    double *maior = realloc(precos, capacidade * sizeof(double));
    if (maior == NULL) {
        free(precos);
        return 1;
    }
    precos = maior;

    printf("Primeiro item: R$ %.2f\n", *primeiro);
    free(precos);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra -g antigo.c -o antigo
antigo.c: In function ‘main’:
antigo.c:22:5: warning: pointer ‘primeiro’ may be used after ‘realloc’ [-Wuse-after-free]
   22 |     printf("Primeiro item: R$ %.2f\n", *primeiro);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antigo.c:15:21: note: call to ‘realloc’ here
   15 |     double *maior = realloc(precos, capacidade * sizeof(double));
      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
$ ./antigo
Primeiro item: R$ 12.50        « parece certo, mas foi sorte
$ valgrind ./antigo
«… cabeçalho …»
==29753== Invalid read of size 8
==29753==    at 0x4001243: main (antigo.c:22)
==29753==  Address 0x4aa6040 is 0 bytes inside a block of size 32 free'd
==29753==    at 0x485807F: realloc (vg_replace_malloc.c:1804)
==29753==    by 0x4001218: main (antigo.c:15)
==29753==  Block was alloc'd at
==29753==    at 0x4850858: malloc (vg_replace_malloc.c:447)
==29753==    by 0x40011CC: main (antigo.c:6)
==29753==
Primeiro item: R$ 12.50
«…»
==29753== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

    *precos[*tamanho] = valor;        /* deveria ser (*precos)[*tamanho] */

$ gcc -std=c23 -Wall -Wextra -g parenteses.c -o parenteses
$ ./parenteses < compras.txt
Falha de segmentação     (imagem do núcleo gravada) ./parenteses < compras.txt

Referência rápida

Exercícios

Missão final: o carrinho da Ana

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

bool adicionar(double **precos, size_t *tamanho, size_t *capacidade, double valor) {
    if (*tamanho == *capacidade) {
        /* lotou: faça a lista crescer aqui */
        return false;
    }
    (*precos)[*tamanho] = valor;
    (*tamanho)++;
    return true;
}

void liberar(double **precos, size_t *tamanho, size_t *capacidade) {
    free(*precos);
    *precos = NULL;
    *tamanho = 0;
    *capacidade = 0;
}

int main(void) {
    double *precos = NULL;
    size_t tamanho = 0;
    size_t capacidade = 0;

    double preco;
    while (scanf("%lf", &preco) == 1) {
        if (!adicionar(&precos, &tamanho, &capacidade, preco)) {
            printf("Não coube o item de R$ %.2f\n", preco);
        }
    }

    double total = 0.0;
    for (size_t i = 0; i < tamanho; i++) {
        total += precos[i];
    }
    printf("%zu itens (capacidade %zu)\n", tamanho, capacidade);
    printf("Total: R$ %.2f\n", total);

    liberar(&precos, &tamanho, &capacidade);
    return 0;
}

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

bool adicionar(double **precos, size_t *tamanho, size_t *capacidade, double valor) {
    if (*tamanho == *capacidade) {
        size_t nova = (*capacidade == 0) ? 4 : *capacidade * 2;
        double *maior = realloc(*precos, nova * sizeof(double));
        if (maior == NULL) {
            return false;
        }
        *precos = maior;
        *capacidade = nova;
    }
    (*precos)[*tamanho] = valor;
    (*tamanho)++;
    return true;
}

void liberar(double **precos, size_t *tamanho, size_t *capacidade) {
    free(*precos);
    *precos = NULL;
    *tamanho = 0;
    *capacidade = 0;
}

int main(void) {
    double *precos = NULL;
    size_t tamanho = 0;
    size_t capacidade = 0;

    double preco;
    while (scanf("%lf", &preco) == 1) {
        if (!adicionar(&precos, &tamanho, &capacidade, preco)) {
            printf("Não coube o item de R$ %.2f\n", preco);
        }
    }

    double total = 0.0;
    for (size_t i = 0; i < tamanho; i++) {
        total += precos[i];
    }
    printf("%zu itens (capacidade %zu)\n", tamanho, capacidade);
    printf("Total: R$ %.2f\n", total);

    liberar(&precos, &tamanho, &capacidade);
    return 0;
}

Resumo

• Um array que cresce precisa de três coisas: o ponteiro para a memória, o tamanho (itens guardados) e a capacidade (itens que cabem).
• Quando tamanho == capacidade, cresça com realloc, sempre em bytes: nova * sizeof(double).
• Dobre a capacidade (começando em 4, por exemplo): 1000 itens custam 9 realocações em vez de 1000.
• Guarde o resultado do realloc numa variável auxiliar e confira o NULL antes de trocar o ponteiro.
• Depois do realloc, endereços antigos de dentro da lista morrem; índices continuam valendo.
• Coloque a lógica em funções (adicionar, liberar) e termine sempre com free. Confira com valgrind --leak-check=full.
• Com structs, as três variáveis viram uma só, e o código fica bem mais limpo.