Arrays: Contiguous Storage of One Type

Part I · Module 6 · Chapter 6.1 · Arrays: Contiguous Storage of One Type

1. Why Fifty Variables Does Not Work

Suppose you have four sensor readings. With what you know so far:

    int reading_0 = 120;
    int reading_1 = 118;
    int reading_2 = 125;
    int reading_3 = 119;

Tedious, certainly. But tedium is not the real problem — if it were, arrays would be a convenience and not a necessity.

Here is the real problem. Write a loop that finds the largest.

You cannot. A loop needs to examine the i-th reading for a value of i that changes on every pass, and there is no way to turn a number into a variable name. reading_0 is a name the compiler resolved while compiling, exactly as Chapter 5.6 described. Nothing in C builds a name out of a value at run time.

With separate variables, you can only ever refer to an element you named when you wrote the code. Anything that depends on a computed position is impossible.

That is why four variables is awkward and fifty is unusable: not the declarations, but everything you cannot write afterwards.

2. One Object, Many Elements

#include <stdio.h>

int main(void)
{
    int readings[4];

    readings[0] = 120;
    readings[1] = 118;
    readings[2] = 125;
    readings[3] = 119;

    printf("first  %d\n", readings[0]);
    printf("fourth %d\n", readings[3]);

    return 0;
}

Output:

first  120
fourth 119

int readings[4]; declares an array: four objects of type int, stored one after another, collectively making up one larger object called readings.

Three parts of that sentence carry weight.

Four objects of type int. Each element is a real object in the sense Chapter 2.1 established — storage with a type, which you can assign to and read from. readings[0] = 120; is an ordinary assignment to an ordinary int object.

All the same type. An array holds elements of exactly one type. There is no mixing.

A fixed number. The 4 is part of the array's type, fixed when you write the declaration. An array does not grow, and nothing you do later changes how many elements it has.

The number in the brackets at the declaration is the element count. The number in the brackets elsewhere is the index, which selects one element — and §4 is about why it starts at 0.

3. The Exact Bytes

This is the picture the rest of the module is built on, so it is worth establishing it with evidence rather than assertion.

#include <stdio.h>

int main(void)
{
    int readings[4];

    printf("sizeof (int)        %zu bytes\n", sizeof (int));
    printf("sizeof readings[0]  %zu bytes\n", sizeof readings[0]);
    printf("sizeof readings     %zu bytes\n", sizeof readings);
    printf("4 * sizeof (int)    %zu bytes\n", 4u * sizeof (int));
    printf("elements            %zu\n", sizeof readings / sizeof readings[0]);

    return 0;
}

Output on an implementation where int is 4 bytes:

sizeof (int)        4 bytes
sizeof readings[0]  4 bytes
sizeof readings     16 bytes
4 * sizeof (int)    16 bytes
elements            4

Read the third and fourth lines together. The whole array occupies exactly four elements' worth of storage — not a byte more.

That is the proof of the word contiguous. If there were anything between the elements — a separator, a length, a marker of any kind — sizeof readings would be larger than 4 * sizeof (int). It is not. There is no room for anything else to be in there.

The rule is general, not a fact about int:

    char           small[4];
    unsigned short mid[4];
    double         wide[4];

char   [4]   4 bytes, element 1
ushort [4]   8 bytes, element 2
double [4]  32 bytes, element 8

Every one is exactly the element count times the element size.

Counting the elements

The last line of §3's program is an idiom worth knowing now:

    sizeof readings / sizeof readings[0]

The whole array's size divided by one element's size is the number of elements. It is better than writing 4 again, because it cannot disagree with the declaration — change int readings[4] to int readings[8] and the count follows automatically.

It works here because readings is a real array that the compiler can see. That will stop being true in a situation Chapter 7.7 explains, and the reason it stops is one of the most important facts in C. For now the idiom is safe in every place this module can put it.

4. Why an Index Starts at Zero

Zero-based indexing is often presented as a convention to get used to. It is not a convention; it follows from Figure 1.

An index is the distance from the start of the array, measured in elements.

readings[0] is the element zero elements along — the first one. readings[2] is the element two elements along. Reading it that way, starting anywhere else would be strange.

#include <stdio.h>

int main(void)
{
    int readings[4];
    readings[0] = 120;
    readings[1] = 118;
    readings[2] = 125;
    readings[3] = 119;

    for (int i = 0; i < 4; i++) {
        printf("readings[%d] = %d   (%d elements past the start)\n",
               i, readings[i], i);
    }

    return 0;
}

Output:

readings[0] = 120   (0 elements past the start)
readings[1] = 118   (1 elements past the start)
readings[2] = 125   (2 elements past the start)
readings[3] = 119   (3 elements past the start)

Two consequences follow immediately, and both matter later.

The last valid index is one less than the count. An array of 4 has valid indices 0, 1, 2, 3. There is no readings[4], and Chapter 6.4 is about what happens if you write one anyway.

Chapter 4.5's loop idiom was built for this. for (int i = 0; i < count; i++) produces exactly the valid indices, in order, with no arithmetic to get wrong. That is not a coincidence — the half-open bound and zero-based indexing fit together, and Chapter 6.3 uses the pairing constantly.

5. Now the Loop Is Possible

§1's problem was that no loop could visit the readings. With an array it is straightforward:

#include <stdio.h>

int main(void)
{
    int readings[4];
    readings[0] = 120;
    readings[1] = 118;
    readings[2] = 125;
    readings[3] = 119;

    int highest = readings[0];
    int highest_at = 0;

    for (int i = 1; i < 4; i++) {
        if (readings[i] > highest) {
            highest = readings[i];
            highest_at = i;
        }
    }

    printf("highest reading %d, at index %d\n", highest, highest_at);

    return 0;
}

Output:

highest reading 125, at index 2

The expression readings[i] is the thing §1 could not express: an element selected by a value computed while the program runs. Everything else in that program is Module 4 and Module 5 material.

Two details are deliberate. The search starts at index 1, because index 0 was already used as the starting answer — comparing it with itself would be wasted work. And highest_at records where, which is usually at least as useful as the value and costs one more object.

6. What an Array Is Not

Two smaller corrections while the picture is fresh.

An array is not a variable holding many values. It is many objects. readings[1] = 118; modifies one of them and leaves the other three alone, exactly as limit = 118; would modify one int.

An array is not resizable. The count is part of the type, so readings is an array of four int for its whole existence. A program that needs a number of elements decided while it runs needs Module 9's dynamic allocation.

7. A Note on Functions

Module 5 spent nine chapters teaching you to move work into functions, and you have probably already thought of writing int highest(...) for §5's loop.

Not yet — and the reason is worth stating rather than leaving you to wonder why every example in this module stays inside main.

When an array is used as an argument, something specific and surprising happens to it, which interacts directly with Chapter 5.3's rule that arguments are copied. Chapter 5.3 warned about this in advance: it said arrays would appear to be an exception to pass-by-value and are not. Chapter 7.7 explains what actually happens, and it can only explain it after Module 7 has built the machinery. Asserting the rule here, four chapters early, would mean asking you to accept something rather than understand it.

So this module keeps array work where the array is declared. It is a temporary restriction, it makes the examples slightly longer than they need to be, and it buys a real explanation later instead of a rule to memorise now.

8. What You Should Be Able to Say Now

1. Separate variables fail because no name can be computed at run time, so no loop can visit them.
2. int readings[4]; declares four int objects stored one after another, forming one larger object.
3. Elements are all the same type, and the count is fixed and part of the array's type.
4. sizeof readings is exactly the count times the element size — proof there are no gaps and no hidden fields.
5. An index is a distance in elements from the start, which is why it begins at 0.
6. Valid indices for a count of n run 0 to n − 1.
7. Chapter 4.5's for (i = 0; i < count; i++) produces exactly those indices.
8. sizeof arr / sizeof arr[0] gives the element count, and works because the compiler can see the declaration.
9. An array does not store its own length. The compiler knows it from the type.
10. Arrays are not passed to functions in this module — Chapter 7.7 explains why.

9. Exercises

Exercise 1 — predict the sizes. Assume int is 4 bytes, double is 8, char is 1, and unsigned short is 2. Give sizeof for the whole array and for one element, and the element count from the idiom.

int      a[10];
double   b[3];
char     c[7];
unsigned short d[5];

Exercise 2 — argue the contiguity. sizeof b above is 24. Explain in two sentences why that number rules out the array storing its own length alongside the elements.

Exercise 3 — read the distances. For int values[6];, say which element each of these selects and how far along it is: values[0], values[3], values[5]. Then say why values[6] is not one of them.

Exercise 4 — explain the impossibility. A colleague has int reading_0, reading_1, reading_2; and asks how to write a loop that prints all three. Explain, in terms of when names are resolved, why there is no way to do it, and what the fix is.

Exercise 5 — predict the output. Do not compile yet.

int v[5];
for (int i = 0; i < 5; i++) {
    v[i] = i * i;
}
for (int i = 0; i < 5; i++) {
    printf("%d ", v[i]);
}
printf("\n");
printf("%zu %zu\n", sizeof v, sizeof v / sizeof v[0]);

Exercise 6 — find the off-by-one. This is meant to fill every element. Say which index it writes that it should not, and relate it to §4's rule about the last valid index. (Chapter 6.4 covers what actually happens; here, just identify the index.)

int samples[8];
for (int i = 0; i <= 8; i++) {
    samples[i] = 0;
}

Exercise 7 — rewrite the count. §5's loop uses the literal 4 twice. Rewrite it using the sizeof idiom, then say what breaks if the declaration changes to int readings[6] in the original version and what happens in yours.

Exercise 8 — classify four claims. For each, say whether it is true of C arrays, and give your reason in one sentence.

• an array stores its own element count
• every element of an array has the same type
• an array can grow when it runs out of room
• the index of the last element is one less than the count

10. Summary

• Separate variables cannot be selected by a computed value, which is the real reason arrays exist.
• int a[n]; is n objects of one type, stored end to end, forming one larger object.
• The count is part of the type and is fixed.
• sizeof the array equals exactly count × element size — proof of contiguity and proof there is no hidden length.
• An index is a distance in elements; hence zero-based, and hence a last valid index of n − 1.
• sizeof arr / sizeof arr[0] gives the count because the compiler sees the declaration.
• An array is many objects, not one variable holding many values, and it does not resize.
• Array work stays inside main in this module; Chapter 7.7 explains why.

Every array so far has been declared empty and then filled one assignment at a time, which worked for four elements and would be unreasonable for forty. C lets you supply the values in the declaration itself — and that feature has a detail that catches people out, because what happens to the elements you do not mention is a specific, defined rule rather than the unpredictable contents Chapter 2.3 warned about for ordinary variables.