6 Arrays and Collections

The array model

A built-in array stores a fixed number of values of one type in contiguous memory. For an array with $N$ elements, valid positions range from $0$ through $N-1$. The size cannot change after the declaration.

The declaration pattern is type name[size]. For example, an integer array declared with a bound of $4$ has four elements: positions $0$, $1$, $2$, and $3$. The subscript expression a[i] is defined through pointer arithmetic as $\ast(a+i)$, which explains why subscripting works with both arrays and pointers.

C++ does not automatically perform bounds checking. Using an index outside the valid range can therefore produce undefined behavior. A loop should normally use a condition such as $i < N$, not $i \leq N$.

Takeaway: The size and element type are fixed, indexing begins at $0$, and the last valid index is always one less than the number of elements.

Declaring and initializing arrays

Brace initialization assigns values from left to right, beginning at index $0$. If fewer initializers are supplied than the array contains, the remaining elements are value-initialized. For an integer array, this means the omitted elements become zero.

An empty initializer such as int counts[5]{} initializes every element to zero. When an initializer is present, the bound can be omitted because C++ deduces the size from the number of initializers. A character array initialized from a string literal includes a terminating null character when there is room for it.

Before reading an automatic-storage array, initialize it explicitly. Declaring an array without an initializer does not guarantee that its elements contain useful values.

Example: An array initialized with two integer values but declared to hold five elements contains those two values followed by three value-initialized elements.

Takeaway: Initialization determines the starting contents and can also allow C++ to infer the array's bound.

Traversing and modifying elements

Traversal visits each element, commonly with an index-based for loop or a range-based for loop. An index-based loop is useful when the position matters, such as when an algorithm must report or update a particular index. When the array is available in the same scope, its element count can be computed from its total size and the size of one element.

A range-based for loop is often clearer when only the values matter. Iterate by reference when each element must be modified; iterate by const reference when the elements should be read without copying and must not be changed.

For example, multiplying each element by a constant requires a non-const reference. Printing each element can use a value or a const reference, depending on whether copying is acceptable.

Takeaway: Choose index-based traversal when positions matter and range-based traversal when direct element access is enough.

Multidimensional arrays

A multidimensional array is an array whose elements are themselves arrays. A two-dimensional declaration such as int matrix[2][3] represents two rows and three columns. The first subscript selects a row, and the second selects a column.

The elements use row-major order: the complete first row is stored before the complete second row. This layout follows directly from the fact that a two-dimensional array is an array of one-dimensional arrays.

Nested loops are the usual way to visit every element. The outer loop controls rows, and the inner loop controls columns. Higher-dimensional arrays follow the same nesting pattern. When a multidimensional array is initialized, only the first bound may be omitted; the remaining bounds are needed to determine the shape of each nested element.

Takeaway: Keep row and column bounds explicit, and use one loop per dimension to avoid confusing the two indexes.

Searching and aggregating

A linear search checks elements from the beginning toward the end until it finds the target or exhausts the array. If the search stops when it finds a match, it returns the first matching position. To report every match, continue the traversal instead of stopping at the first one.

The worst-case running time of a linear search is $O(n)$, because it may inspect all $n$ elements. A sorted array can support a faster binary search, but the ordering must be maintained and the algorithm requires more structure than the introductory sequential approach.

Aggregation uses a traversal to combine values. A sum starts at zero and adds each element. An average divides the sum by the element count, but the division should be performed in a floating-point type when a fractional result is needed. For a minimum or maximum, initialize the candidate from the first element rather than from an assumed bound; this works correctly for negative and positive values alike.

Takeaway: Searching selects values or positions, while aggregation combines values into a summary.

Passing arrays to functions

When a built-in array is passed to a function, its parameter is adjusted to a pointer parameter. The function therefore receives access to the first element but does not automatically receive the original element count. Pass the count separately, and use const when the function must not modify the elements.

For a two-dimensional array, every bound except the first must be specified in the parameter type. The column bound is required so the compiler can calculate the address of an element in a selected row.

A reference parameter can preserve the complete array type, including its size. With a template parameter for the bound, the compiler can deduce the size from the array supplied by the caller, avoiding a separate count argument.

Takeaway: Function interfaces must make array size available explicitly, either through a count, a preserved reference type, or a standard container.

Choosing a collection and avoiding errors

A built-in array is simple and efficient, but it does not provide member functions such as .size() and cannot be copied or assigned as an ordinary object. For a fixed-size collection, std::array<T, N> provides a container interface while retaining contiguous storage and a compile-time size.

Use std::array when the number of elements is fixed but convenient operations and standard-container behavior are useful. Use a dynamically sized container such as std::vector when the number of elements must change during execution.

Common mistakes include using a loop condition that reaches one past the last index, applying sizeof to an array parameter and expecting the original array size, reading uninitialized elements, and reversing the row and column limits of a matrix.

Takeaway: Match the collection type to the required size behavior, and make bounds and initialization deliberate.

• built-in array parameter