Arrays: Contiguous Elements and Indexing

Start with the problem

A variable holds one value. To keep a thousand test scores you would need a thousand variables with a thousand names, and no loop could visit them. What you want is one name for a whole collection, with positions, so that a loop can walk through it. That is an array: a fixed number of elements of the same type, stored one after another in memory.

int scores[5] = {90, 85, 70, 60, 100};
int total = 0;
for (int i = 0; i < 5; ++i) {
    total = total + scores[i];
}

The interesting questions are all about memory. Where do the five numbers live, and how does scores[i] find the right one?

How the idea works

Declaring. The form is type name[count], and the count must be known at compile time. Elements share one type. An initializer list fills the first elements, and any elements left over are set to zero. Without an initializer, a local array holds leftover bytes, as lesson 3 warned for single variables:

int a[5] = {1, 2};   // 1, 2, 0, 0, 0
int b[5] = {};       // all zero
int c[5];            // garbage: uninitialized

Layout. The elements are contiguous: they sit directly one after another, with no gaps or bookkeeping between them. Element i begins i * sizeof(element) bytes after the first one. The trace shows three int values taking exactly 12 bytes. The sizeof operator on the whole array gives the byte count, and the number of elements is sizeof(a) / sizeof(a[0]), or std::size(a) since C++17.

Indexing. The expression v[i] means the element i steps away from the start, so the first element is at index 0, as step 2 shows with v[2] landing on offset 8. The compiler turns it into address arithmetic: the start address plus i times the element size. On x86-64, that is one instruction, because the CPU can add a scaled index while loading. Reading and writing use the same formula (steps 2 and 3).

No checks. Look at step 4. The formula works for any number you give it, including 3 for an array with indexes 0 to 2. The program contains no array name and no size, so nothing can notice that the address leaves the array.

Looping. The usual pattern is a half-open loop from 0 to the count, as in lesson 4. The range-based form for (int s : scores) visits every element with no index at all.

Two dimensions. An array of arrays such as int grid[3][4] is stored row by row, so grid[r][c] is at offset (r * 4 + c) elements.

Arrays are not values. You cannot assign one array to another with =, and you cannot pass an array by value. When you pass an array to a function, it turns into a pointer to its first element and the size is lost, as the last check showed. Lesson 7 explains why.

Why it is correct

Contiguity plus equal element sizes is what makes the formula work: the address of any element can be computed directly from its index, so accessing element 5 and element 5,000,000 costs the same. That is constant-time random access. It also explains zero-based indexing. The index is an offset, the number of elements to skip, so the first element is zero steps from the start and needs no arithmetic.

Because the size is part of the type and known at compile time, the compiler can place the array at a fixed offset in a stack frame, as in lesson 6, and the array needs no length field or bookkeeping of any kind. The price is the one step 4 revealed: nothing stores the length, so nothing can check it.

What it costs

Access. Reading an element is one load, with the address arithmetic folded into it.

Cache. The CPU fetches memory in lines of 64 bytes, so reading one int brings in its 15 neighbors for free. Walking through an array in order is the best case for the cache, and the hardware even prefetches ahead. Adding up 10 million integers, which is 40 MB, typically takes a few milliseconds. Walking in the wrong order costs a lot: in a 2D array stored by rows, visiting it column by column jumps by a whole row on every step, and can easily run several times slower.

Space. An array of n elements takes exactly n * sizeof(element) bytes, with no overhead. A million int values take 4 MB. But a large local array lives on the stack, and as lesson 6 explained, a local int big[3000000] of 12 MB overflows an 8 MB stack.

Fixed size. An array cannot grow. Sizing it for the worst case wastes memory, and sizing it too small invites overflow, which is why the next lessons introduce std::vector.

Pitfalls and variations

Off-by-one. For an array of size 5 the valid indexes are 0 to 4. The loop i <= 5 reads index 5, one past the end, which is lesson 4's error with much worse consequences. The next lesson covers them.

Sizes in parameters. sizeof on an array parameter reports the size of a pointer. Pass the count as a second parameter, or use a type that knows its size.

Comparing arrays. a == b compiles, but it compares the addresses of the first elements, not the contents. Newer GCC versions warn about it with -Warray-compare.

Signed and unsigned. Sizes are unsigned numbers of type std::size_t. Mixing them with signed loop counters triggers the comparison trap from lesson 4.

Variations. std::array wraps a fixed-size array in a proper type that can be copied and knows its size, and std::vector can grow, both in the next lesson. C++20 adds std::span, a view of a run of elements. Arrays whose size is set at run time, such as int a[n], are accepted by GCC as an extension but are not standard C++, so avoid them.

Where it is used

Pixel buffers, audio samples, lookup tables, matrices and video frames are all arrays of numbers, because contiguous layout is what hardware, from CPU caches to GPUs, handles best. The standard containers std::array and std::vector are built on exactly the layout in this lesson.

The next lesson, "Out-of-Bounds Access and Undefined Behavior", looks at what happens when an index leaves the array, and why the result is worse than a crash.