Modern C++ containers provide safe, expressive abstractions for storing and managing data. This chapter compares vector, array, deque, list, and associative containers, showing how memory layout, access patterns, ordering, iterator stability, and allocation requirements inform sound container selection.

Iterators provide a common interface between containers and STL algorithms. Their categories define the operations they support, while range-based loops, standard algorithms, and lambdas enable concise traversal, searching, sorting, transformation, removal, accumulation, and customized behavior.

Used effectively, these tools replace error-prone manual memory management and hand-written loops with reusable, predictable operations. Practical engine applications include vertex and component storage, registries, lookup tables, caches, and fixed-size buffers, with particular attention to the erase–remove idiom, cache-efficient design, and the avoidance of unsuitable containers and raw allocation.

Containers, iterators, and algorithms are foundational to modern C++. They replace manual memory management, raw arrays, hand-written loops, and fragile data handling with abstractions that are safer, clearer, and more efficient. Mastery of these tools is essential to writing clean, production-quality C++.

Rather than treating the STL (Standard Library) as a loose collection of utilities, this chapter presents it as a cohesive system founded on value semantics, zero-cost abstractions, and predictable behavior.

Containers address three fundamental requirements:

1. Memory management. Containers allocate, resize, and release memory automatically.
2. Safety. They reduce the risk of buffer overruns, dangling pointers, and manual errors.
3. Expressiveness. They make code more concise, readable, and maintainable.

In modern C++, standard containers should replace raw arrays in nearly every practical scenario.

The STL provides several container types, each designed for a distinct set of use cases.

std::vector<T> — Dynamic Array

• Enables fast random access
• Stores elements in contiguous memory
• Serves as the default choice for most general-purpose workloads
• Is well suited to engine data such as vertices, transforms, and entities

Example:

std::vector<Vec3> points;
points.push_back({1,2,3});

std::array<T, N> — Fixed Size Array

• Has a size determined at compile time
• Stores elements in contiguous memory
• Introduces no additional runtime overhead
• Is well suited to mathematical types and small, fixed-size buffers

Example:

std::array<float, 3> color = {1.0f, 0.5f, 0.2f};

std::deque<T> — Double Ended Queue

• Supports efficient insertion and removal at both ends
• Uses noncontiguous storage
• Is well suited to queues and history buffers

std::list<T> — Linked List

• Is rarely the optimal choice in modern C++
• Offers poor cache locality
• Should generally be replaced by vector unless stable iterators are essential

Associative Containers

• std::map<K, V> — stores ordered key-value pairs
• std::unordered_map<K, V> — stores hashed key-value pairs
• std::set<T> — stores ordered unique values
• std::unordered_set<T> — stores hashed unique values

Game engines commonly use hash maps (unordered_map) for registries, rapid lookups, and resource tables.

Modern C++ requires deliberate, workload-driven container selection.

Use std::vector when:

• Fast iteration matters
• Contiguous storage is required
• Cache efficiency is important
• Many elements must be stored
• Predictable behavior is desired

Use std::unordered_map when:

• Keys must be found quickly
• Element order does not matter
• Average constant-time access is preferred

Use std::array when:

• The size is fixed at compile time
• Zero additional overhead is required
• Stack allocation is preferred

Avoid std::list unless:

• Stable iterators are required
• Frequent insertion or removal in the middle is unavoidable

Container selection is therefore an architectural decision, not merely an implementation detail.

Iterators are generalized pointer-like abstractions.

They enable the same algorithms to operate consistently across different container types.

Example:

std::vector<int> v = {1,2,3};

for (auto it = v.begin(); it != v.end(); ++it)
{
    std::cout << *it;
}

For straightforward traversal, modern C++ generally favors range-based loops:

for (int x : v)
{
    std::cout << x;
}

Nevertheless, a strong understanding of iterators remains essential when working with algorithms.

A container’s capabilities determine the category of iterator it provides:

Input Iterator
Reads values in sequence.

Output Iterator
Writes values in sequence.

Forward Iterator
Moves only forward and supports repeated passes.

Bidirectional Iterator
Moves both forward and backward.

Random Access Iterator
Supports direct movement to any position, as provided by vector and array.

Random-access iterators support the STL’s most powerful algorithms.

The <algorithm> library provides hundreds of functions that operate over iterator ranges.

Examples:

Searching

auto it = std::find(v.begin(), v.end(), 42);

Sorting

std::sort(v.begin(), v.end());

Transforming

std::transform(v.begin(), v.end(), v.begin(),
               [](int x){ return x * 2; });

Removing

v.erase(std::remove(v.begin(), v.end(), 0), v.end());

Accumulating

int sum = std::accumulate(v.begin(), v.end(), 0);

Algorithms replace repetitive manual loops with concise, reusable, and intention-revealing operations.

The erase–remove idiom is one of the STL’s most important patterns:

v.erase(std::remove(v.begin(), v.end(), value), v.end());

Why?

• remove reorders the range and shifts retained elements forward
• erase shortens the container by removing the trailing elements
• Together, they safely remove every matching value

This idiom is fundamental to clear and correct container manipulation.

Lambdas make algorithmic code both concise and expressive:

std::sort(v.begin(), v.end(),
          [](const Item& a, const Item& b)
          {
              return a.score < b.score;
          });

They provide customized behavior without the overhead of separate function objects or boilerplate code.

Containers are integral to virtually every production engine system:

Vectors

• Vertex buffers
• Transform arrays
• Component storage
• Event queues
• Frame history

Unordered maps

• Resource registries
• Entity lookup tables
• Shader parameter maps
• Asset caches

Arrays

• Math types
• Fixed buffers
• Small lookup tables

A thorough understanding of containers is essential to designing modular, efficient, and maintainable systems.

These are some common mistakes which we should try to avoid in our code.

• Choosing std::list for presumed performance benefits
• Using std::vector without accounting for its specialized behavior
• Failing to call reserve() for large vectors when capacity is predictable
• Choosing maps when an array or vector would be simpler and more efficient
• Using raw arrays when std::array provides a safer alternative
• Using new[] when std::vector offers safer ownership and resizing

Modern C++ avoids these pitfalls through deliberate, context-aware container selection.

This chapter covered:

• Why standard containers are fundamental to modern C++
• How to select the appropriate container for a given workload
• How iterators provide a unified model for container access
• How standard algorithms replace repetitive manual loops
• How lambdas express custom algorithmic behavior concisely
• How containers support practical engine architecture
• How to recognize and avoid common container-related mistakes

Together, these concepts establish a strong foundation for the next chapter on error handling, exceptions, and contracts.