Why doubling makes a dynamic array O(1) (and the realloc bug almost everyone writes)

#c #programming #beginners #datastructures

If you have used std::vector or Python lists, you have used a dynamic array. In C you have to build it yourself, and two details decide whether it is fast and correct: how much you grow, and how you call realloc.

The idea

A dynamic array stores three things: a pointer to the data, the number of elements (size) and the space available (capacity).

typedef struct {
    int    *data;
    size_t  size;
    size_t  capacity;
} Vec;

When size == capacity and you want to push another element, you need more room.

Growing by +1 is slow

If every push on a full array grows capacity by one, each push may copy the whole array. Pushing n elements costs about 1 + 2 + ... + n, which is O(n²). Ten thousand pushes means roughly fifty million element copies.

Doubling is amortized O(1)

If you double the capacity when it is full, copies happen rarely. Starting at capacity 1, you copy at sizes 1, 2, 4, 8, ... up to n. Total copies are 1 + 2 + 4 + ... + n/2, which is less than n.

So n pushes cost O(n) in total, and each push costs O(1) on average. Most pushes are cheap and an occasional push is expensive. That is what "amortized" means.

The realloc bug

This is the version many people write first:

v->data = realloc(v->data, new_cap * sizeof *v->data);   // BUG

If realloc fails it returns NULL and does not free the old block. You have just overwritten your only pointer to it. The old memory leaks, and v->data is now NULL, so the next access crashes.

The fix is to use a temporary:

int *tmp = realloc(v->data, new_cap * sizeof *tmp);
if (tmp == NULL) {
    return -1;            // v->data is still valid, nothing is lost
}
v->data = tmp;
v->capacity = new_cap;

Also check for overflow before you multiply: if capacity is already very large, capacity * 2 can wrap around.

A complete push

int vec_push(Vec *v, int value) {
    if (v->size == v->capacity) {
        size_t new_cap = v->capacity ? v->capacity * 2 : 4;
        int *tmp = realloc(v->data, new_cap * sizeof *tmp);
        if (tmp == NULL) return -1;
        v->data = tmp;
        v->capacity = new_cap;
    }
    v->data[v->size++] = value;
    return 0;
}

Test it

Push 100,000 integers, then check every value and size. Run it under a leak checker and make sure that a failed allocation leaves the vector usable.

Code

A commented, tested version of this (with a linked list and a stack) is on GitHub under the MIT license: https://github.com/abbomokhnoor/c-data-structures-lite

Disclosure: I also sell a larger paid version of this kit (trees, heaps, hash tables, graphs, sorting, 114 tests and a study guide): https://payhip.com/b/djq5l

DEV Community