Indexing and Traversing an Array

Part I · Module 6 · Chapter 6.3 · Indexing and Traversing an Array

1. The Shape to Use

    for (size_t i = 0; i < count; i++) {
        /* work with array[i] */
    }

That is the traversal. The rest of the chapter explains why each piece is what it is, and what goes wrong with the alternatives.

Two things you already have make it correct without checking anything.

Chapter 6.1 established that an index is a distance, so the valid indices for count elements are 0 through count - 1.

Chapter 4.5 established that i = 0; i < count produces exactly those values — count of them, visibly, with no arithmetic to perform in your head.

The two facts were built to fit together. The loop does not need to be checked against the array's size because the condition is the array's size.

2. Where the Count Comes From

A loop bound is only as good as the number in it. There are three places that number can come from, and they are not equally good.

    for (size_t i = 0; i < 6; i++)                                /* a literal */
    for (size_t i = 0; i < sample_count; i++)                     /* a named object */
    for (size_t i = 0; i < sizeof samples / sizeof samples[0]; i++) /* the idiom */

The literal is the worst of the three. It is correct exactly until somebody changes the declaration, and nothing connects the two lines.

The sizeof idiom from Chapter 6.1 is the one to prefer while the array is in scope, because it cannot disagree with the declaration. Change int samples[6] to int samples[10] and every loop written this way follows automatically.

In practice, compute it once and name it:

    size_t count = sizeof samples / sizeof samples[0];

That reads better than repeating the division, and it puts the count in one place.

3. Why the Index Is size_t

Here is a connection that most introductions leave out, and it has a visible consequence.

Chapter 2.12 established that sizeof produces a value of type size_t, which is unsigned. So the count in §2 is unsigned. Now compare it against an int index:

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

    for (int i = 0; i < sizeof a / sizeof a[0]; i++) {
        printf("%d ", a[i]);
    }

warning: comparison of integers of different signs: 'int' and 'unsigned long'
    [-Wsign-compare]

The loop works, and the warning is right to be there: Chapter 3.5 showed that comparing a signed value with an unsigned one applies the conversions from Chapter 3.12, and Chapter 3.12 showed that the result can surprise you.

Declare the index to match and the warning disappears, because there is no mixed comparison left:

#include <stdio.h>

int main(void)
{
    int a[5] = {1, 2, 3, 4, 5};
    size_t count = sizeof a / sizeof a[0];

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

    return 0;
}

Output:

1 2 3 4 5

The count comes from sizeof, sizeof yields size_t, so the index is size_t. Three facts that have to agree, and the compiler tells you when they do not.

This is also why size_t exists. Chapter 2.12 introduced it as the type C uses for sizes and counts; an array index is a count of elements from the start, so it is the same kind of quantity.

4. Watching a Traversal Run

    int samples[6] = {120, 118, 125, 119, 131, 117};
    size_t count = 6;

    int total = 0;
    for (size_t i = 0; i < count; i++) {
        total = total + samples[i];
    }

Trace it as state rather than as text:

before the loop      i -       total 0

test i < 6   0 < 6   true      total = 0   + samples[0] 120  ->  120
test i < 6   1 < 6   true      total = 120 + samples[1] 118  ->  238
test i < 6   2 < 6   true      total = 238 + samples[2] 125  ->  363
test i < 6   3 < 6   true      total = 363 + samples[3] 119  ->  482
test i < 6   4 < 6   true      total = 482 + samples[4] 131  ->  613
test i < 6   5 < 6   true      total = 613 + samples[5] 117  ->  730
test i < 6   6 < 6   FALSE     loop ends,  total 730

Seven tests, six passes — Chapter 4.5's counted result, with the extra test being the one that discovers the end. The highest index actually used is 5, which is count - 1, exactly as Chapter 6.1 said it should be. Index 6 is computed for the test and never used to reach an element.

That last sentence is worth holding on to. The loop's final act is to produce a value one past the end and then not use it. Chapter 6.4 is about what happens when a loop uses it.

5. The Bound That Looks Equivalent

Some people prefer to write the condition in terms of the last valid index:

    for (size_t i = 0; i <= count - 1; i++)       /* do not do this */

For a count of 6 it visits 0 through 5, exactly like i < count. The two look interchangeable.

They are not, and the case where they differ is the one that matters most:

#include <stdio.h>

int main(void)
{
    size_t count = 0;

    printf("count          %zu\n", count);
    printf("count - 1      %zu\n", count - 1);
    printf("0 <= count - 1 %d\n", (size_t)0 <= count - 1);

    return 0;
}

Output:

count          0
count - 1      18446744073709551615
0 <= count - 1 1

count is size_t, which is unsigned, and Chapter 2.6 established that unsigned arithmetic wraps rather than going negative. So count - 1 on an empty array is not −1 but the largest value a size_t can hold — and 0 <= that is true.

This is the same failure Chapter 4.7 catalogued as the unsigned countdown, arriving from a different direction. There, i >= 0 was always true; here, count - 1 wrapped. Both come from Chapter 2.6, and both are invisible until the empty case arrives.

6. Traversing Backward

Walking from the end has the same problem and a standard solution.

The form that works for a signed index does not work for size_t:

    for (size_t i = count - 1; i >= 0; i--)        /* never ends */

i >= 0 is true for every value a size_t can hold — Chapter 4.7 established exactly this — and count - 1 has already wrapped if the array is empty. Two faults in one line.

The idiomatic unsigned form keeps the loop variable one above the element it handles:

#include <stdio.h>

int main(void)
{
    int samples[4] = {10, 20, 30, 40};
    size_t count = sizeof samples / sizeof samples[0];

    printf("forward: ");
    for (size_t i = 0; i < count; i++) {
        printf("%d ", samples[i]);
    }
    printf("\n");

    printf("backward: ");
    for (size_t i = count; i > 0u; i--) {
        printf("%d ", samples[i - 1u]);
    }
    printf("\n");

    return 0;
}

Output:

forward: 10 20 30 40
backward: 40 30 20 10

Read the backward loop carefully. i runs 4, 3, 2, 1 and the element used is samples[i - 1], so the indices touched are 3, 2, 1, 0. The condition is i > 0, which is a plain comparison that becomes false normally, and no subtraction happens in the condition — so an empty array gives 0 > 0, false, and the body never runs.

It takes a moment to get used to. It is worth it, because it is the one backward shape that is correct for an unsigned index and an empty array at the same time.

7. The Traversal Shapes

Most array work is one of a handful of patterns. All of them use §1's loop.

#include <stdio.h>

int main(void)
{
    int samples[6] = {120, 118, 125, 119, 131, 117};
    size_t count = sizeof samples / sizeof samples[0];

    int total = 0;
    for (size_t i = 0; i < count; i++) {
        total = total + samples[i];
    }

    int highest = samples[0];
    size_t highest_at = 0;
    for (size_t i = 1; i < count; i++) {
        if (samples[i] > highest) {
            highest = samples[i];
            highest_at = i;
        }
    }

    int above_threshold = 0;
    for (size_t i = 0; i < count; i++) {
        if (samples[i] > 120) {
            above_threshold = above_threshold + 1;
        }
    }

    printf("count      %zu\n", count);
    printf("total      %d\n", total);
    printf("highest    %d at index %zu\n", highest, highest_at);
    printf("above 120  %d\n", above_threshold);

    return 0;
}

Output:

count      6
total      730
highest    131 at index 4
above 120  2

Accumulate starts from an identity value — 0 for a sum, 1 for a product — and visits every element.

Find the extreme starts from element 0 as the current answer and visits from index 1, because comparing element 0 with itself achieves nothing. It records where as well as what, which usually costs one object and often saves a second traversal. Note that this pattern needs at least one element to start from; on an empty array, samples[0] is the access §5 warned about, so a function doing this would have to handle a count of zero before it begins.

Count matching is an accumulate with a condition.

The fourth pattern modifies in place:

    for (size_t i = 0; i < count; i++) {
        samples[i] = samples[i] * 2;
    }

before: 3 7 2 9 4
after:  6 14 4 18 8

samples[i] is an ordinary object: it can appear on the left of an assignment, take a compound assignment (samples[i] *= 2), or be incremented (samples[i]++). Chapter 6.1's point that elements are real objects is what makes all of that work without new rules.

8. What You Should Be Able to Say Now

1. The traversal is for (size_t i = 0; i < count; i++), and it is correct by construction.
2. It is correct because an index is a distance (6.1) and i < count yields exactly count values (4.5).
3. Prefer the sizeof idiom for the count over a literal; compute it once and name it.
4. sizeof yields size_t, so the index should be size_t — otherwise -Wsign-compare fires, and it is right to.
5. The loop's final test produces an index one past the end and never uses it.
6. i <= count - 1 is not equivalent. For an unsigned count of 0 it wraps and reads element 0 of an empty array.
7. That is Chapter 2.6's wrapping and Chapter 4.7's countdown arriving in a new place.
8. Backward with an unsigned index is for (size_t i = count; i > 0u; i--) using array[i - 1u].
9. The common shapes are accumulate, find the extreme, count matching and modify in place.
10. Finding an extreme needs at least one element; a count of zero must be handled before the loop starts.

9. Exercises

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

int v[4] = {2, 4, 6, 8};
size_t n = sizeof v / sizeof v[0];

int sum = 0;
for (size_t i = 0; i < n; i++) {
    sum = sum + v[i];
}
printf("%d %zu\n", sum, n);

Exercise 2 — trace it. Write the state table, in §4's style, for this loop with v as in Exercise 1. Give the value of product after each pass and say how many times the condition was evaluated.

int product = 1;
for (size_t i = 0; i < n; i++) {
    product = product * v[i];
}

Exercise 3 — count the visits. For an array of 7 elements, give the indices each loop visits, and say which are valid.

for (size_t i = 0; i < 7; i++)
for (size_t i = 1; i < 7; i++)
for (size_t i = 0; i <= 7; i++)
for (size_t i = 7; i > 0u; i--)

Exercise 4 — explain the warning. Say why for (int i = 0; i < sizeof a / sizeof a[0]; i++) warns, name the two types involved, and give two different repairs. Say which you would use and why.

Exercise 5 — the empty case. For size_t count = 0, state what each condition evaluates to on the first test, and which of the two loops runs its body.

for (size_t i = 0; i < count; i++)
for (size_t i = 0; i <= count - 1; i++)

Then explain, in terms of Chapter 2.6, why the second behaves as it does.

Exercise 6 — repair the backward loop. This never terminates. Say why, using Chapter 4.7, then rewrite it in the form from §6 and give the indices it touches for a count of 3.

for (size_t i = count - 1; i >= 0; i--) {
    printf("%d ", v[i]);
}

Exercise 7 — find the bug. This is meant to report the smallest element. Say what it does for {5, 3, 9}, what it does for an array whose elements are all greater than 0, and what it does for an empty array. Then repair it.

int smallest = 0;
for (size_t i = 0; i < count; i++) {
    if (v[i] < smallest) {
        smallest = v[i];
    }
}

Exercise 8 — write two traversals. Given int codes[10] and its count, write a loop that counts how many elements equal zero, and a loop that replaces every negative element with zero. State, before compiling, how many times each loop's condition is evaluated.

10. Summary

• The traversal is for (size_t i = 0; i < count; i++) — correct by construction, not by checking.
• It works because an index is a distance and i < count produces exactly the valid ones.
• Take the count from the sizeof idiom, computed once and named.
• sizeof yields size_t, so the index is size_t; a mismatch is reported by -Wsign-compare.
• i <= count - 1 is a different loop. On an empty unsigned count it wraps to a huge value and reads a non-existent element.
• Backward is for (size_t i = count; i > 0u; i--) with array[i - 1u], which also handles the empty case.
• The shapes are accumulate, find the extreme, count matching, modify in place.
• Finding an extreme requires at least one element.

Every loop in this chapter was built so that it could not produce an index outside the array, and §4 noted that the final test produces exactly such an index and then declines to use it. That raises the question the whole discipline exists to avoid: what if it did? C's answer is not what a beginner expects — there is no check, no error and often no immediate symptom — and understanding exactly what an out-of-range access does to a running program is what makes the habits in this chapter feel necessary rather than fussy.