Arrays

Summary

Up to now each datum of the course has lived in its own variable, with its own name; but many data of the same type, such as the temperatures of a week, cannot be traversed with a loop if each one has a different name. This lesson presents the first data structure of the course, the indexed sequence: elements of the same type, in contiguous positions of memory, numbered from zero. In modern C++ it is written with std::array, whose size is fixed at compile time. We study its declaration, the type std::size_t of the indices and the two traversals, with an index and with the range-based for. We establish the rule that governs the whole unit: an index is valid if it lies between 0 and the size minus one, and at each access inside a loop that validity is justified with the invariant. We show what happens when it does not hold, which is undefined behavior, and compare [] with the checked access .at(). And we present C arrays, in order to read other people’s code.

Learning objectives

Declare, initialize and traverse a std::array with indices and with the range-based for.
Justify, by means of the loop invariant, that an index is within bounds at each access.
Distinguish access with [], which the standard does not check, from access with .at(), which is always checked, and explain when each one is appropriate.
Read code with C arrays and explain their disadvantages compared with std::array.

The indexed sequence

Many data, a single name

To compute the average of the temperatures of a week with what has been taught so far, seven variables would be needed, monday, tuesday and so on up to sunday, and a sum of seven terms. With those of a year there would be 365, and no loop could traverse them, because in the body of a loop the name of a variable is always the same. What is missing is a name for the whole and a number for each element, so that the number can be a variable that the loop moves forward.

An indexed sequence is exactly that: a set of $n$ elements of the same type, stored one after another in contiguous cells of memory, and designated by their position, called the index. Mathematics knows the object: a finite sequence $(a_0, a_1, \dots, a_{n-1})$ , in which $a_i$ designates the element in place $i$ , or a vector, like those of the course Algebra and Geometry I. In C++ one writes a[i], and the index can be any integer expression: 2, i, i + 1.

Why from zero

In C++, as in most current languages, the first element has index 0, and the last, index $n - 1$ . The reason is not a capricious convention, but the way an element is found: if the sequence begins at a certain memory address and each element occupies $s$ bytes, the element of index $i$ is at the initial address plus $i \cdot s$ . The index is, therefore, an offset: the number of elements that must be skipped from the first. The first is zero skips away from itself.

From this follows the definition that governs this whole unit: in a sequence of $n$ elements, an index $i$ is valid if and only if $0 \leq i < n$ . The inequality on the right is strict, and it is the source of the most frequent error with sequences, the off-by-one error: writing $i \leq n$ where $i < n$ should have been written, or starting at 1 where one should have started at 0. An index equal to $n$ does not designate the last element, but the cell that follows the sequence, which does not belong to it.