The STL: containers, iterators, algorithms

The STL is not just "some useful classes." It is a design pattern for generic C++: containers own or organize elements, iterators describe positions in sequences, and algorithms operate over ranges of iterators. That separation lets std::sort work on a std::vector, std::find_if work on many traversable structures, and std::span pass a non-owning contiguous view without losing the length. The mental model is: choose the data structure for ownership and layout, then use algorithms for the operation.

The reset: containers answer "where do elements live?", iterators answer "how do I walk them?", and algorithms answer "what operation is applied to that walk?"

How it really works

Containers come in families with different layout and complexity promises:

Family	Examples	Shape
Sequence	`std::vector`, `std::array`, `std::deque`, `std::list`	ordered elements, chosen layout
Associative	`std::map`, `std::set`	sorted tree-like lookup, stable ordering
Unordered associative	`std::unordered_map`, `std::unordered_set`	hash-table lookup, no sorted order
Adaptors	`std::stack`, `std::queue`, `std::priority_queue`	restricted interface over another container
Views	`std::span`, ranges views	non-owning or lazy view over elements

std::vector<T> is the default sequence container because it is contiguous, compact, and cache-friendly. It can reallocate, which invalidates pointers, references, and iterators into its storage. std::list<T> keeps node addresses stable across many operations, but pays per-node allocation and poor locality. std::map gives ordered keys and logarithmic lookup. std::unordered_map gives average constant-time lookup, but hashing, rehashing, and worst-case behavior matter.

Iterators are generalized pointers. Some can only move forward; some are bidirectional; some are random-access; contiguous iterators expose adjacent memory. Algorithms state their requirements through iterator categories or concepts. Sorting needs random access. Finding only needs input/forward traversal. This is why algorithm choice and container choice are coupled without every algorithm naming every container.

Algorithms usually take half-open ranges: [first, last). The first iterator points to the first element; the last iterator points one past the final element. That matches C pointer ranges and avoids a sentinel element. C++20 ranges add overloads that take range objects directly, but the same contract remains: the algorithm works over a valid range and assumes its preconditions are met.

Executable artifact: containers plus algorithms

The runnable demo lives in examples/modern-cpp/the-stl-containers-iterators-algorithms/. It stores records in a std::vector, sorts with an algorithm, finds with a predicate, transforms into another container, and demonstrates vector reallocation without dereferencing an invalid pointer.

cd examples/modern-cpp/the-stl-containers-iterators-algorithms
./run.sh

The algorithm layer reads like operations over ranges:

std::sort(samples.begin(), samples.end(), [](const Sample &left, const Sample &right) {
    return left.cycles < right.cycles;
});

auto first_slow = std::find_if(samples.begin(), samples.end(), [](const Sample &sample) {
    return sample.cycles >= 30;
});

std::transform(samples.begin(), samples.end(), std::back_inserter(cycles),
               [](const Sample &sample) {
                   return sample.cycles;
               });

The reallocation probe is careful:

std::vector<int> growth{1, 2, 3};
const int *before = growth.data();
std::size_t before_capacity = growth.capacity();
while (growth.capacity() == before_capacity) {
    growth.push_back((int)growth.size() + 1);
}
const int *after = growth.data();

std::cout << (before != after) << "\n";

It compares addresses after reallocation but never dereferences before. Dereferencing it would be a use-after-invalidation bug.

Failure modes & trade-offs

Iterator invalidation is real lifetime invalidation. After a vector reallocates, old pointers, references, and iterators into its storage are dead.
Algorithm preconditions are contracts. std::sort needs a valid range and a comparator that behaves like a strict weak ordering. Violating that is not "sort being weird"; it is your contract failing.
Container choice is a performance decision. std::list avoids relocation but usually loses locality. std::vector relocates but is often faster because memory is contiguous.
Views do not own. std::span and many ranges views are borrow-like. If the underlying storage dies, the view dangles.
end() is not an element. It is a sentinel/past-the-end iterator. Dereferencing it is invalid.
Debug iterators are not the language. Some standard-library debug modes catch invalid iterators. Release builds usually trust you.

In practice

Default to std::vector until a constraint says otherwise. It is simple, cache-friendly, and algorithm-compatible.
Use algorithms to state intent. std::find_if, std::count_if, std::sort, and std::transform are more searchable and less error-prone than custom loops for common operations.
Reserve when growth is known. vector.reserve() avoids repeated reallocations and preserves iterators until capacity is exceeded.
Keep iterator lifetimes short. Store indices or stable IDs if a container will mutate.
Reach for std::span at boundaries. It carries pointer plus length without taking ownership, a cleaner replacement for many T* plus count pairs.

Connects to: Templates and generic programming · References, const, and overloading · Move semantics and value categories · Data layout and cache-friendliness · Pointer arithmetic and stride · Arrays and array-to-pointer decay

Sources

cppreference - Containers library - container families, storage management, iterator invalidation table, and complexity context. https://en.cppreference.com/w/cpp/container
cppreference - Iterator library - iterator categories, iterator traits, sentinels, and C++20 iterator concepts. https://en.cppreference.com/w/cpp/iterator
cppreference - Algorithms library - standard algorithm families, range requirements, sorting, finding, transforming, and numeric operations. https://en.cppreference.com/w/cpp/algorithm
cppreference - Ranges library - C++20 range and view vocabulary over iterator/sentinel pairs. https://en.cppreference.com/w/cpp/ranges
C++ working draft - [containers.general] - standard summary of container requirements and families. https://eel.is/c++draft/containers.general
C++ working draft - [iterators] - standard wording for iterator requirements and concepts. https://eel.is/c++draft/iterators
C++ working draft - [algorithms] - standard wording for algorithm requirements and operation families. https://eel.is/c++draft/algorithms