Step 5 of 10

Growing with realloc

What if you don't know how many values are coming, not even at run time? The answer is a growable array: start with a small heap block, and when it fills up, make it bigger. realloc does the resizing.

realloc(ptr, new_size) returns a pointer to a block of the new size that holds the old contents. It may grow the block where it is, or it may allocate a new block elsewhere, copy everything over, and free the old one. So:

• Always use the pointer realloc returns. The old one may now be invalid.
• If it fails, it returns NULL and the old block is untouched. So store the result in a temporary first. Writing a = realloc(a, ...) directly would overwrite your only pointer with NULL on failure, leaking the old block.

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

int main(void) {
    int cap = 1, len = 0;
    char *text = malloc(cap);
    if (!text) return 1;
    const char *word = "growing";
    for (int i = 0; word[i] != '\0'; i++) {
        if (len + 1 >= cap) {
            char *bigger = realloc(text, cap * 2);
            if (!bigger) { free(text); return 1; }
            text = bigger;
            cap *= 2;
        }
        text[len++] = word[i];
    }
    text[len] = '\0';
    printf("%s, capacity %d\n", text, cap);
    free(text);
    return 0;
}

growing, capacity 8

Why double?

Growing by one element each time would copy the whole array on every push, which gets very slow for big arrays. Doubling the capacity means copies become rarer as the array grows, so on average each push is cheap (this is called amortized O(1)). C++'s std::vector and almost every dynamic array in other languages work this way, growing by a constant factor (usually 1.5 or 2) each time.

Keep two numbers: length (how many are used) and capacity (how many fit). Grow only when length reaches capacity.

Your turn: read integers until the end of input (you don't know how many!) into a heap array that starts with capacity 2 and doubles when full. Print how many you read, the capacity at the end, and the last number:

Input 5 6 7 8 9 prints count 5 cap 8 last 9.

Previous: calloc and strdup-style copies Next: Memory bugs to avoid