Arrays: contiguous memory

Why this matters

So far every value has lived in its own named variable. Real programs handle many values of the same kind: the samples of an audio clip, the pixels of an image, the lines of a file, the scores of a class. An array stores many values of one type under one name, side by side in memory, and lets you pick any of them by number. Arrays are the most basic data structure there is, and in C they are also the closest to the hardware: an array is exactly a block of consecutive bytes. Understanding that layout is the foundation for strings (this module) and pointers (the next).

Declaring and indexing

int scores[5];

declares an array named scores holding 5 ints. The number in brackets is the length; it must be a positive integer constant here. Each element is reached by indexing with scores[i], where the index i runs from 0 to 4:

#include <stdio.h>

int main(void)
{
    int scores[5] = {90, 72, 85, 64, 99};
    int sum = 0;

    for (int i = 0; i < 5; i++) {
        sum += scores[i];
    }
    printf("first: %d, last: %d\n", scores[0], scores[4]);
    printf("sum: %d, average: %.1f\n", sum, sum / 5.0);
    printf("sizeof scores = %zu, sizeof scores[0] = %zu\n", sizeof scores, sizeof scores[0]);
    printf("element count = %zu\n", sizeof scores / sizeof scores[0]);
    return 0;
}

first: 90, last: 99
sum: 410, average: 82.0
sizeof scores = 20, sizeof scores[0] = 4
element count = 5

scores[i] behaves exactly like an int variable: you can read it, assign to it, increment it, and take its address with &scores[i] (which is why scanf("%d", &scores[i]) works).

The loop for (int i = 0; i < N; i++) is the standard way to visit every element. Note <, not <=: the last valid index is N - 1.

What it looks like in memory

The elements of an array are contiguous: they sit next to each other with no gaps. With 4-byte ints, scores occupies 20 consecutive bytes:

  address (example)   0x1000   0x1004   0x1008   0x100c   0x1010   0x1014
                     +--------+--------+--------+--------+--------+
  scores             |   90   |   72   |   85   |   64   |   99   |
                     +--------+--------+--------+--------+--------+
  index                  0        1        2        3        4

(Real addresses vary from run to run; these are made up to keep the arithmetic easy.)

This is why indexes start at 0. To find element i, the machine computes

  address of scores[i] = address of scores + i * sizeof(int)

scores[0] is zero steps from the start; scores[3] is at 0x1000 + 3 * 4 = 0x100c. One multiply and one add, no matter how big the array is. Reaching any element takes the same constant time, which is the defining strength of arrays.

sizeof reports the whole block: sizeof scores is 5 * 4 = 20 bytes. Dividing by the size of one element recovers the length. You will often see this as a macro:

#define COUNT(a) (sizeof (a) / sizeof (a)[0])

Initializing

An uninitialized local array contains whatever bytes happened to be in that memory, just like an uninitialized int. Initializers fix that:

#include <stdio.h>

int main(void)
{
    int a[6] = {1, 2};          /* the rest become 0 */
    int b[] = {7, 8, 9};        /* size taken from the initializer: 3 */
    int c[6] = {[4] = 40, [1] = 10};

    for (int i = 0; i < 6; i++) printf("%d ", a[i]);
    printf("\n");
    printf("b has %zu elements\n", sizeof b / sizeof b[0]);
    for (int i = 0; i < 6; i++) printf("%d ", c[i]);
    printf("\n");
    return 0;
}

1 2 0 0 0 0 
b has 3 elements
0 10 0 0 40 0 

Rules worth remembering:

• If you give any initializer, every element you did not mention becomes 0. So int counts[10] = {0}; is the idiomatic way to zero a whole array.
• With empty brackets, the compiler counts the initializers for you.
• Designated initializers ([4] = 40) set specific elements by index.
• Global arrays (declared outside any function) are zeroed automatically even without an initializer.

A worked example: counting with an array

Arrays indexed by a value make excellent counters. This program reads digits and counts how often each occurs, using the digit itself as the index:

#include <stdio.h>

int main(void)
{
    int counts[10] = {0};
    int digit;
    while (scanf("%d", &digit) == 1) {
        if (digit >= 0 && digit <= 9) {
            counts[digit]++;
        }
    }
    for (int d = 0; d < 10; d++) {
        if (counts[d] > 0) printf("%d: %d\n", d, counts[d]);
    }
    return 0;
}

$ echo 3 1 4 1 5 9 2 6 5 3 5 | ./prog
1: 2
2: 1
3: 2
4: 1
5: 3
6: 1
9: 1

The check digit >= 0 && digit <= 9 is not decoration. Without it, an input of 12 would increment counts[12], memory that does not belong to the array.

Arrays are not values you can assign

You cannot copy an array with = or compare two arrays with ==:

int a[3] = {1, 2, 3};
int b[3];
b = a;

main.c:7:7: error: assignment to expression with array type
    7 |     b = a;
      |       ^

To copy, loop over the elements (or use memcpy, which you will meet with strings). a == b compiles, but it does not compare contents; what it does compare will make sense in the pointers module.

No bounds checking

C does not check indexes. This program has an off-by-one error (<= instead of <):

#include <stdio.h>

int main(void)
{
    int nums[4] = {10, 20, 30, 40};
    for (int i = 0; i <= 4; i++) {
        printf("nums[%d] = %d\n", i, nums[i]);
    }
    return 0;
}

It compiles without a single warning, and in the sandbox it printed:

nums[0] = 10
nums[1] = 20
nums[2] = 30
nums[3] = 40
nums[4] = 0

nums[4] read the 4 bytes just past the array, which held some other data that happened to be 0. On another run, another compiler or another machine it could print anything, crash, or (when writing out of bounds) silently overwrite another variable. This is undefined behavior, and out-of-bounds writes are the root of the famous buffer overflow security bugs.

Tools can catch it at run time. Building with -fsanitize=address adds checks to every memory access:

$ gcc -g -fsanitize=address -o prog main.c && ./prog
nums[0] = 10
...
==34==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7f7586900030 ...
READ of size 4 at 0x7f7586900030 thread T0
    #0 0x5593afc95368 in main /work/main.c:7
...
    [32, 48) 'nums' (line 5) <== Memory access at offset 48 overflows this variable

It names the line and the array. Use it whenever an array program behaves strangely.

Common mistakes

• Off by one: i <= N in the loop condition, or using a[N] as "the last element". The last element is a[N - 1].
• Using an index you did not check: an array indexed by user input must check the range first.
• Forgetting to initialize: int counts[10]; inside a function starts with garbage. Write = {0}.
• Reading past what you filled: if you read 3 values into a 100-element array, only elements 0 to 2 are meaningful. Keep a separate count (n) and loop to n, not to 100.
• Variable-length arrays: int a[n]; with a runtime n is legal in C17 but optional, has no way to report failure if n is huge, and many style guides ban it. This track uses fixed sizes and, later, malloc.

Recap

• An array is N elements of one type stored contiguously; indexes run from 0 to N-1.
• a[i] is at the array's start plus i * sizeof a[0] bytes: constant-time access.
• sizeof a / sizeof a[0] gives the length where the array itself is in scope.
• An initializer zeroes every element it does not mention; = {0} zeroes the whole array.
• Arrays cannot be assigned or compared with = and ==.
• C never checks bounds. Out-of-bounds access is undefined behavior; -fsanitize=address finds it.

Going further: take the off-by-one example and change the loop to write nums[i] = 0 for i <= 4, with another int variable declared next to nums. Print that variable afterwards, then rebuild with -fsanitize=address and read the report.