One- and Multi-Dimensional Arrays

1Declaring and initializing

int scores[5];                       /* five ints, uninitialized */
int primes[5] = { 2, 3, 5, 7, 11 };  /* five ints, given values  */
int zeros[5]  = { 0 };               /* first is 0, rest are 0   */
int partial[5] = { 1, 2 };           /* 1, 2, 0, 0, 0            */
int sized[]   = { 4, 8, 15, 16 };    /* length 4, deduced        */

Two rules in that list are worth stating explicitly. If you supply any initializer, every element you did not mention is set to zero — so { 0 } is the idiomatic way to zero an entire array. And if you supply no initializer at all, the elements contain garbage, exactly as an uninitialized scalar does in week 5.

The size must be a constant expression in standard C89. C99 added variable-length arrays, where the size can be a run-time value; they are convenient and carry real hazards, which is why they are deferred to week 38.

Computing the length

size_t n = sizeof primes / sizeof primes[0];

The total size divided by the size of one element. Using primes[0] rather than int keeps the expression correct if the element type later changes.

Designated initializers

int sparse[10] = { [2] = 5, [7] = 9 };   /* C99: others are 0 */

Useful for lookup tables where most entries are zero, and far more readable than counting commas. Week 21 uses the same syntax on structures.

2Indexing, and why size_t

Elements are numbered from 0. An array of n elements has valid indices 0 through n-1 — the half-open range [0, n) from week 10, which is exactly why the canonical loop is written the way it is.

for (size_t i = 0; i < n; i++) {
    printf("%d ", values[i]);
}

Use size_t, not int, for indices. It is unsigned, so it cannot hold a meaningless negative index; it is guaranteed wide enough for any array the platform can hold; and it is the type sizeof yields, so comparing against a computed length does not mix signedness and trigger week 7's trap.

The cost is the countdown hazard from week 5. To iterate backwards:

for (size_t i = n; i-- > 0; ) {
    printf("%d ", values[i]);
}

This reads oddly and is worth decoding once. The condition tests i against 0 and then decrements it, so the body sees n-1 down to 0, and the loop exits when the test sees 0 — before the decrement could wrap. It handles n == 0 correctly with no special case.

3Out of range: what actually happens

C performs no bounds checking. None. values[10] on a five-element array computes an address and reads or writes it, exactly as if you had asked for something legitimate.

Indexing is defined as address arithmetic: values[i] means the object at address values + i × sizeof(element). If i is out of range, that address belongs to something else — another variable, saved register state, or the function's return address.

The first row is the worst outcome, not the best. A bug that reliably crashes is a bug you will fix today. A bug that silently corrupts a neighbouring variable is a bug you will chase for a week, and the crash will happen somewhere innocent.

This is the defect class behind a large share of security vulnerabilities, and the reason weeks 20, 35, and 36 all return to it. The practical defence is tooling:

gcc -std=c17 -Wall -Wextra -g -fsanitize=address -o prog prog.c
./prog

AddressSanitizer instruments every access and reports the exact line, the array, and the offset. It costs roughly a factor of two in speed, which is irrelevant during development. Use it from now on.

4Two-dimensional arrays

int grid[3][4];              /* 3 rows, 4 columns */
int table[2][3] = {
    { 1, 2, 3 },
    { 4, 5, 6 }
};
grid[1][2] = 7;              /* row 1, column 2 */

A two-dimensional array is an array of arrays, and it is stored in row-major order: the whole first row, then the whole second, contiguously in memory.

Row-major layout has a practical consequence that week 34 measures: iterate rows outermost, columns innermost. That walks memory in order, and the cache supplies the next elements for free. Reverse the loops and each step jumps a row's width, defeating the cache. On a large matrix the difference can be several times the runtime — same result, same operation count.

/* fast: sequential in memory */
for (size_t r = 0; r < ROWS; r++)
    for (size_t c = 0; c < COLS; c++)
        sum += m[r][c];

/* slow: strides across memory */
for (size_t c = 0; c < COLS; c++)
    for (size_t r = 0; r < ROWS; r++)
        sum += m[r][c];

Passing a 2D array to a function

All dimensions except the first must be specified, because the compiler needs the row width to compute offsets:

void print_grid(int g[][4], size_t rows);    /* column count required */
void print_grid(int (*g)[4], size_t rows);   /* the same declaration  */

This rigidity is one reason real code often uses a one-dimensional array with manual indexing, m[r * cols + c], which accepts any shape at run time. Week 19 builds the dynamically allocated version.

5Worked example: transpose, and a demonstration of corruption

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

#define ROWS 3
#define COLS 4

static void print_matrix(const char *label, size_t rows, size_t cols,
                         const int m[rows][cols])
{
    printf("%s (%zux%zu)\n", label, rows, cols);
    for (size_t r = 0; r < rows; r++) {
        printf("  ");
        for (size_t c = 0; c < cols; c++) {
            printf("%4d", m[r][c]);
        }
        putchar('\n');
    }
}

static void transpose(size_t rows, size_t cols,
                      const int src[rows][cols], int dst[cols][rows])
{
    for (size_t r = 0; r < rows; r++) {
        for (size_t c = 0; c < cols; c++) {
            dst[c][r] = src[r][c];
        }
    }
}

/* Bounds-checked access. Returns false instead of reading out of range. */
static bool at(const int values[], size_t n, size_t index, int *out)
{
    if (index >= n) {
        return false;
    }
    *out = values[index];
    return true;
}

static int sum(const int values[], size_t n)
{
    int total = 0;
    for (size_t i = 0; i < n; i++) {
        total += values[i];
    }
    return total;
}

static void reverse(int values[], size_t n)
{
    for (size_t i = 0; i < n / 2; i++) {
        int temp = values[i];
        values[i] = values[n - 1 - i];
        values[n - 1 - i] = temp;
    }
}

static size_t find(const int values[], size_t n, int target)
{
    for (size_t i = 0; i < n; i++) {
        if (values[i] == target) {
            return i;
        }
    }
    return n;                          /* n means "not found" */
}

int main(void)
{
    int m[ROWS][COLS] = {
        {  1,  2,  3,  4 },
        {  5,  6,  7,  8 },
        {  9, 10, 11, 12 }
    };
    int t[COLS][ROWS];

    print_matrix("original", ROWS, COLS, m);
    transpose(ROWS, COLS, m, t);
    print_matrix("transposed", COLS, ROWS, t);

    puts("\nrow-major layout: the same 12 ints, read linearly");
    const int *flat = &m[0][0];
    printf("  ");
    for (size_t i = 0; i < ROWS * COLS; i++) {
        printf("%4d", flat[i]);
    }
    puts("\n  note the rows appear one after another");

    int values[] = { 4, 8, 15, 16, 23, 42 };
    const size_t n = sizeof values / sizeof values[0];

    printf("\nsum      = %d\n", sum(values, n));
    printf("find 23  = index %zu\n", find(values, n, 23));
    printf("find 99  = %s\n", find(values, n, 99) == n ? "not found" : "found");

    reverse(values, n);
    printf("reversed = ");
    for (size_t i = 0; i < n; i++) {
        printf("%d ", values[i]);
    }
    putchar('\n');

    puts("\nbounds-checked access:");
    int got;
    printf("  index 2 -> %s", at(values, n, 2, &got) ? "" : "refused\n");
    if (at(values, n, 2, &got)) printf("%d\n", got);
    printf("  index 99 -> %s\n", at(values, n, 99, &got) ? "returned a value" : "refused");

    return EXIT_SUCCESS;
}

gcc -std=c17 -Wall -Wextra -g -o arrays arrays.c
./arrays

Now corrupt something on purpose

Add this function and call it. It demonstrates the table in section 3 rather than describing it.

static void demonstrate_corruption(void)
{
    int before = 111;
    int small[4] = { 1, 2, 3, 4 };
    int after  = 999;

    printf("\nbefore=%d  after=%d\n", before, after);
    printf("writing to small[4] and small[5], which do not exist...\n");

    small[4] = 0;                 /* one past the end */
    small[5] = 0;                 /* two past the end */

    printf("before=%d  after=%d   <-- one of these probably changed\n",
           before, after);
}

Compile without sanitizers first:

gcc -std=c17 -Wall -Wextra -g -o arrays arrays.c && ./arrays

Typically one of before or after becomes 0, depending on how the compiler arranged the stack. There is no error, no warning at run time, and no crash. The program has quietly destroyed a variable that the code you are looking at never mentions.

Now with the sanitizer:

gcc -std=c17 -Wall -Wextra -g -fsanitize=address -o arrays_asan arrays.c
./arrays_asan

==12345==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffd...
WRITE of size 4 at 0x7ffd... thread T0
    #0 0x... in demonstrate_corruption arrays.c:118
  Address is located in stack of thread T0 at offset 52 in frame
    'small' (line 112) <== Memory access at offset 52 overflows this variable

Exact file, exact line, the variable's name, and the offset. That is the difference between an afternoon and ten seconds, and it is available to you for one compiler flag.

The sizeof trap, made visible

Add this pair and compare the output:

static void show_sizeof(const int values[])
{
    printf("  inside a function: sizeof values   = %zu\n", sizeof values);
}

/* in main: */
printf("\nsizeof trap:\n");
printf("  where declared:    sizeof values   = %zu\n", sizeof values);
show_sizeof(values);

  where declared:    sizeof values   = 24
  inside a function: sizeof values   = 8

Twenty-four bytes for six ints where the array is declared; eight bytes — one pointer — inside the function. GCC even warns: 'sizeof' on array function parameter will return size of 'const int *'. Week 13 explains the decay that causes it.

6Common mistakes

8Where this leads

Two unexplained things are now outstanding: why sizeof changes inside a function, and why a function can modify an array's contents despite pass-by-value. Both have the same answer, and week 13 gives it. Pointers also repair the swap from week 11, explain the & that scanf has been demanding since week 8, and open the door to strings in week 14.