17. The Array

Advanced perspective: a sequence is useful only while its boundary remains attached

Contiguous storage does not excuse an access whose bound cannot be proved

An array gives us a sequence of adjacent elements of one type. That layout can support efficient traversal and simple interoperability, but neither property answers the first correctness question: does this particular subscript designate an element of this particular sequence? For int values[3], the valid indices are 0, 1 and 2. The expression values[3] steps beyond the elements. A program that appears to survive the access has demonstrated only that one failure was not immediately visible.

The bound is not a suggestion for sensible input. It is part of the proof required before each indexed access. If count is the number of elements, a valid subscript satisfies 0 <= index && index < count. For an unsigned index the lower comparison is implicit in the type, but the upper comparison remains essential. A pointer may be formed one position past the final element for range reasoning; dereferencing that one-past value is still invalid.

Array-to-pointer conversion removes information from the interface

The type of a built-in array object includes its element count. While the expression still refers to that array, facilities such as std::size can obtain the bound. In many expression contexts, however, the array is converted to a pointer to its first element. A function parameter written with array-looking syntax is adjusted to a pointer parameter; writing a number inside those brackets does not make the function receive or enforce that number.

Once the interface contains only const int* data, the callee cannot recover how many integers the caller intended to make available. A separate count can restore the contract by convention, but pointer and count can disagree. Which sequence produced the pointer? Is the count measured in elements or bytes? Was it captured before the owner resized? Each question exists because the type no longer carries the complete relationship.

Keep ownership and extent visible at the call

#include <array>
#include <iostream>
#include <span>

int sum(std::span<const int> values) {
    int total{0};
    for (const int value : values) {
        total += value;
    }
    return total;
}

int main() {
    const std::array values{4, 7, 9};
    std::cout << sum(values) << '\n';
}

The std::array in main owns three integers as part of its value. The span passed to sum is a view of those elements. It does not copy them and it does not own them. Its const element type prevents this function from modifying the integers through the view; it does not extend their lifetime.

The range-based loop obtains the elements described by the span without making the function invent a second count or maintain a manual index. The trace is 0 plus 4, then 7, then 9, so the result is 20. That visible arithmetic is useful, but the interface is doing the more important work. Data and extent arrive together, while ownership remains visibly with the caller for the duration of this call.

A span makes the bound available; it does not turn every operation into a checked operation. If code uses an explicit index, the program must still establish its validity or choose an operation whose contract performs the required check. Better information makes a better interface possible. It does not abolish preconditions.

Select the representation from change, ownership and identity

"Arrays are fast" is not a container-selection rule. First decide whether the element count is fixed by the problem or known only at runtime. Then decide who owns the elements, whether the sequence must resize, and whether existing references must survive changes. A std::array is appropriate when the count is genuinely fixed and value semantics fit. A std::vector is appropriate when the program owns a contiguous sequence whose size changes at runtime. A span is appropriate when an operation borrows an already existing contiguous range.

Using a dynamic allocation merely because the count is large answers none of those questions. Nor does a built-in array become the correct choice merely because it has no separate size or capacity fields. Representation overhead matters only after the required behaviour is correct and the workload shows that the difference is material.

Growth changes more than the number reported by size()

A vector owns a sequence and normally retains capacity for some number of elements. When an insertion requires more storage than the current capacity, the vector obtains a new allocation, moves or copies its elements as required, and releases the old allocation. Pointers, references and iterators into the former allocation are then invalid. The vector object is still alive. Its old element addresses are not.

reserve can establish enough capacity for a known amount of growth. If it reallocates, references into the old storage are invalidated at that point. Successful later insertions that remain within capacity avoid reallocation, but this is a bounded statement about those operations, not a permanent licence to store addresses. The past call to reserve must be compared with the actual capacity and subsequent growth.

Contiguity permits a locality argument; it does not finish one

For int grid[2][3], the rightmost index varies across adjacent elements. Row-first traversal therefore follows the stored order, while column-first traversal uses a larger stride. On a sufficiently large and repeatedly processed row-major data set, that difference can affect cache behaviour. This is a mechanism worth testing, not a ritual for rearranging every nested loop.

Observed performance also depends on element size, working-set size, compiler optimisation, access frequency, hardware, surrounding work and whether a different data organisation reduces the useful computation. An array of objects may be contiguous in those objects while the data reached through members is allocated elsewhere. An array of std::string places the string objects together; it does not promise that all character buffers follow one another. Draw what is actually contiguous before predicting what the cache will see.

The same discipline applies to array-of-structures and structure-of-arrays designs. The correct choice depends on which fields are accessed together across which elements. A benchmark should represent that access pattern and preserve the program's required behaviour. Faster output from a test that quietly computes less is not a locality success.

Transfer task: preserve the slice, not merely its first address

Design a function that sums elements first through last of a caller-owned vector, with first included and last excluded. State what must be true when the slice is empty, when it covers the full vector, and when either endpoint is outside the vector. Decide whether the function should receive the vector and two indices, a span already restricted by the caller, or a different representation.

Now assume the caller saves that slice, appends elements to the vector and uses the slice again. Draw the owner, data allocation, extent and saved view before and after the append. Your answer must identify the condition under which reallocation occurs and what that does to the view. Do not repair the design by saying "call reserve" until you have stated the maximum growth that makes that promise sufficient.

#include <cstddef>
#include <cstdint>
#include <numeric>
#include <optional>
#include <span>
#include <vector>

std::optional<std::span<const int>> checked_slice(
    const std::vector<int>& values,
    std::size_t first,
    std::size_t last) noexcept
{
    if (first > last || last > values.size()) {
        return std::nullopt;
    }

    std::span<const int> all{values};
    return all.subspan(first, last - first);
}

std::optional<std::span<const int>> checked_slice(
    std::vector<int>&&,
    std::size_t,
    std::size_t) = delete;

std::optional<std::span<const int>> checked_slice(
    const std::vector<int>&&,
    std::size_t,
    std::size_t) = delete;

std::int64_t sum(std::span<const int> values)
{
    return std::accumulate(
        values.begin(), values.end(), std::int64_t{0});
}

A safe sequence interface keeps four facts connected: the storage owner, the first element, the number of permitted elements and the operations that can invalidate the relationship. Lose any one of them and the array may remain contiguous while the program's reasoning develops a hole.