Collections: arrays, lists, and slices

Collections store multiple related values. C++ offers fixed-size arrays, resizable vectors, and non-owning views. Choose based on whether the size is fixed, whether the collection owns its elements, and what operations your algorithm needs.

Fixed-size collections

#include <array>

std::array<int, 3> scores{8, 10, 9};
std::cout << scores[0] << '\n';
std::cout << scores.size() << '\n';

std::array has a size encoded in its type and owns its elements. Built-in arrays also have fixed extent, but they do not carry a size when passed as function parameters, so standard containers are usually easier to use correctly.

Resizable sequences with vector

#include <vector>

std::vector<int> values{4, 7};
values.push_back(11);
for (const int value : values) {
    std::cout << value << '\n';
}

std::vector owns a contiguous sequence that can grow. Its size() is the number of elements; its capacity() is the amount of storage currently reserved. Use push_back or emplace_back to add elements. Indexing with [] does not check bounds; at() checks and reports an out-of-range access.

Adding elements may reallocate storage. Reallocation invalidates pointers, references, and iterators into the vector. Do not keep such references across an operation that might grow the container.

Views and iteration

std::span (C++20) is a lightweight non-owning view over a contiguous sequence. It carries a length and works with arrays and vectors, but it does not own the elements. The underlying data must outlive the span.

#include <span>

int sum(std::span<const int> numbers)
{
    int total{};
    for (const int number : numbers) {
        total += number;
    }
    return total;
}

Use a range-based loop for straightforward traversal. Use iterators or indexes when an algorithm needs a position. A valid index is from zero through size() - 1; an empty container has no valid element index.

Capacity, growth, and invalidation

A vector's size tells you how many elements exist; its capacity tells you how many can fit before another allocation is needed. Calling reserve(n) may allocate enough storage for at least n elements without changing the vector's size. This can reduce reallocations when you know approximately how many elements will be added, but reserving an enormous amount without reason wastes memory.

When vector storage reallocates, its elements move to a new memory region. Pointers, references, and iterators into the old region become invalid. Even an insertion that does not reallocate can invalidate references and iterators at or after the insertion point. When you need to refer to an element later, consider storing its index and reacquiring the reference after changes, while remembering that erasure can change which element an index identifies.

Iterators describe ranges

Many standard algorithms receive two iterators: a beginning position and an end position one past the last element. The half-open range [begin, end) is useful because an empty range has equal begin and end, and the number of steps between random-access iterators equals the number of elements. Do not dereference the end iterator.

Algorithms may return iterators. Check whether a search reached end() before using its result. For example, std::find returns the first matching position or the end iterator if no element matches. This is a common, safe way to express “not found” without inventing a sentinel index.

Const access and container choice

Use a const reference in a range loop when you want to avoid copying an element and do not need to modify it: for (const auto& item : items). Use auto& to modify existing elements. A plain auto item creates a copy for each iteration, which may be appropriate for small values but expensive for large objects.

A vector is the default sequence container for many tasks because it is compact and works well with algorithms. A fixed-size array communicates a known extent. A span accepts a contiguous sequence without taking ownership. Do not choose a linked list just because insertion sounds fast: finding the insertion location and memory-locality costs can dominate. Choose a different container only when its operations or guarantees solve a specific need.

Bounds and empty containers

Reading container[index] outside its valid range is undefined behavior for standard vectors and arrays. During development, at(index) can turn an out-of-range access into a reported exception. Neither form removes the need to reason about valid indexes; checks and correct loop bounds are still essential.

Practice

1. Store five temperatures in a vector and compute their average.
2. Write a function accepting std::span<const int> so it can process either an array or a vector.
3. Explain why a reference to values[0] may become invalid after values.push_back(...).
4. Use std::find and check its result against end().
5. Reserve space for a known number of elements, then explain why the vector's size is still initially zero.
6. Write a range loop that updates each element, and another that prints without modifying values.

Key idea: containers own data; views describe data owned elsewhere. Prefer standard containers and make lifetimes and bounds explicit.

Contiguous storage and cache behavior

A vector stores elements contiguously, which usually gives good spatial locality: when the processor fetches one element, nearby elements are likely to arrive in the same cache line. A linked structure may provide stable nodes but requires pointer chasing and separate allocations, which can be slower even when its theoretical insertion complexity appears favorable. Real performance depends on access patterns, element size, allocator behavior, and hardware.

This is one reason the vector is a strong default for sequences. Its amortized constant-time append means individual appends can occasionally trigger a linear-time reallocation, while a long sequence of appends still has linear total work. Reserve capacity when a useful estimate is known, but do not assume reserve changes the number of constructed elements.

Iterator categories and algorithm requirements

Iterators expose capabilities such as reading a value, advancing, moving backward, or jumping by an offset. An input iterator may support only a single-pass traversal; a random-access iterator supports constant-time jumps. Standard algorithms state which capabilities they require. A binary search algorithm can perform logarithmically many comparisons, but using it with a non-random-access iterator can require more iterator increments than expected.

Ranges and iterator-sentinel pairs make these requirements more expressive. A sentinel need not be the same type as an iterator, and a range can communicate whether it is sized or borrowed. These abstractions are valuable for generic APIs, but they do not erase ownership rules: a view over a temporary owner may dangle unless the view type or API deliberately retains ownership.

Invalidation as part of the interface

Iterator invalidation is not an incidental footnote; it is a contract of the container operation. If a function returns an iterator into a container, its documentation should explain which later mutations invalidate it. If a caller needs long-term identity, an index or stable identifier may be more appropriate than a raw iterator, though indexes must also account for erasure and reordering.

When erasing while traversing, use the iterator returned by the erase operation where applicable, or use an algorithm whose contract explicitly removes matching elements. Do not increment an iterator after it has been invalidated. Test the logic with empty, one-element, and all-matching ranges because boundary cases often expose invalid iterator assumptions.

Advanced exercise

1. Compare vector and list traversal on a large data set, measuring allocation count and elapsed time as well as Big-O operations.
2. Write a generic function constrained to the iterator operations it actually needs, then test it with more than one standard container.
3. Design an API that returns a view into stored data and document precisely how long the returned view remains valid.