An introduction to algorithm analysis with a practical focus on how CPUs execute code and fetch data. Topics include growth rates, locality, and why memory layout matters

An introduction to data structures and algorithms from a practical, hardware-first perspective. Learn how the physical layout of your data in memory impacts performance.

Data Structures & Algorithms

Understand how our code interacts with physical hardware. Learn about virtual memory, the stack vs. heap, cache lines, and prefetching.

CPUs, Memory, and Locality

Learn how input size affects execution speed and the most common class of algorithms.

Polynomial Algorithms

Working with massive datasets using divide and conquer strategies, and the the required trade-offs.

Logarithmic and Linearithmic Algorithms

Learn why some problems are impossible to solve exactly and how we can use approximations like Monte Carlo simulations to cheat.

NP-Hard and Approximations

Practical Algorithm Analysis

Setting up a lightweight framework for measuring performance. Create benchmarks that produce reliable, meaningful results

Separate our core logic into libraries, configure CMake for multiple targets, and apply hardware-aware optimizations.

Configuring a CMake Project

Integrate the industry-standard Google Benchmark library into a CMake project to capture nanosecond-precision timings.

Integrating Google Benchmark

Fight the compiler's aggressive optimizations to ensure benchmarks measure reality.

Writing Effective Benchmarks

Learn to interpret CPU time, variance, and the trade-offs between insertion speed and read speed.

Analyzing Benchmark Data

Using Google Benchmark's Range and Complexity features to visualize Big O growth and identify the moment our data falls off the CPU cache cliff.

Mapping Complexity and Hardware Cliffs

Using benchmarks to calculate the 'break-even point' where investing in data preparation pays off.

Amortized Costs and Crossover Points

Google Benchmark for C++

Understand how C++20 ranges reshape the standard library. Learn to combine algorithms and views for clean, efficient code

The bridge between data layout and algorithms. Learn how iterators abstract memory traversal and the hierarchy of capabilities.

The Iterator Pattern

An introduction to the C++ Standard Library's algorithms, lambda expressions, and handling memory safely with insertion iterators.

Standard Library Algorithms

Learn how C++20 Ranges and Views allow us to compose safe, lazy-evaluated data pipelines without sacrificing performance.

C++20 Ranges

Learn how to build readable, lazy-evaluated data pipelines that execute in a single pass, and chain C++20 views together using the pipe operator `|`

View Composition and Pipes

Bridge the gap between iterators and views using `std::ranges::subrange` to turn any pair of iterators into a composable, safe C++20 View.

Subranges and Range Interoperability

Iterators, Ranges, and Views

Implement modern C++23 data processing with views and algorithms. Reduce boilerplate while improving correctness and performance

The Producer-Consumer model of C++20 Ranges and the hardware implications of eager vs lazy evaluation.

The Four Algorithm Families

Integrate sorting into C++20 pipelines, the difference between stable and unstable sorts, and how to use partial sorting.

Sorting and Materialization

Learn how C++20 Projections allow us to separate sorting logic from data layout, the mechanics of `std::invoke` and the hardware reality of sorting large objects.

Comparators and Projections

Learn why sorting large objects is slow, and how to optimize it using Proxy Sorting and Data-Oriented Design (SoA).

Proxy Sort and Structure of Arrays

Iterate multiple containers simultaneously with `zip`, handle indices with `enumerate`, and skip elements with `drop` and `stride`.

Composition, Zipping, and Indicies

Using Algorithms and Views

Modern processors are built for parallel execution, not sequential code. Learn how to use multithreading and vectorization in C++ to match that reality

Offload heavy work to other CPU cores. Learn how `std::async` and `std::future` enable concurrent execution.

Asynchronous Tasks with `std::async`

Combine the elegance of C++20 Ranges with the power of parallel execution policies.

Parallel Algorithms and Execution Policies

Learn how mutexes and atomics prevent race conditions, and why hardware contention can make multithreaded code slower than single-threaded code.

Locks and Atomics

Explore the performance cost of synchronization, how to mitigate it, and how to avoid it entirely with better algorithm design.

Cache Coherency and False Sharing

Learn how SIMD registers allow you to process multiple data points in a single instruction, unlocking the full power of each CPU core.

SIMD and Automatic Vectorization

Introduction to Parallelism

Learn how to design and implement a domain-specific container from scratch. The chapter focuses on cache efficiency, data-oriented design, and real-world performance trade-offs

Build a custom container that combines the performance of data-oriented design with the ergonomics of object-oriented programming.

Domain-Specific Containers

Implement proxy sorting, physical memory permutations, and multi-threaded reordering.

Sorting and Permuting Containers

Comparing the performance cost of deletion techniques, and implementing the Swap-and-Pop approach in a Structure of Arrays container.

The Swap-and-Pop Idiom

Solving the index invalidation problem and the trade-offs between memory density and reference stability.

Stable Addressing and Tombstones

Upgrade simple indices into Generational Handles, creating safe, persistent references that detect stale access.

Generational Indices

The hidden cost of `std::vector` growth, why it is dangerous for real-time systems, and how to mitigate it.

The Reallocation Spike

Implementing a Structure of Arrays

Learn advanced bit-centric techniques including fast filtering, bit packing, and compression to maximize efficiency

Learn to use bitwise operators to pack multiple states into a single byte, reducing memory bandwidth use.

Working with Bits

Replace slow logical operators with fast bitwise arithmetic. Learn how to filter data without branching, avoiding pipeline flushes and speeding up queries.

Fast Filtering and Branchless Logic

Trade CPU cycles for memory bandwidth by compressing data using bit packing, quantization, and delta encoding.

Quantization and Delta Encoding

Use bloom filters for fast rejection, hierarchical bitmasks for spatial skipping, and hardware intrinsics using C++20's `<bit>` library.

Advanced Bitwise Techniques

Implement the high-performance Entity-Component-System (ECS) design pattern, alongside an API that makes the architecture easy to use

Transitioning from monolithic data structures to the ECS architecture, splitting our data into dedicated component pools.

Entity-Component-System (ECS)

Connecting components to their entities using the sparse set pattern, achieving fast lookups while maintaining cache-friendly contiguous data.

Relational Data and Sparse Sets

Efficiently pulling data from multiple component pools simultaneously using the smallest set driver pattern, and optimizing it using bitmasks to minimize cache misses.

The Join Algorithm

Improving our API using templates and a centralized registry using `std::tuple`.

Templatizing Components

Updating our ECS to support composable, range-based views that handle the smallest-set algorithm automatically using C++20 ranges.

Creating Views

Entity-Component-System

Additional chapters are coming soon, covering non-contiguous data structures

Part 2

Learn data structures and algorithms by building real systems, measuring performance, and understanding how your code interacts with the physical hardware.

A hands-on course where you'll implement, benchmark, and optimize code, turning abstract concepts into practical skills you can immediately apply.

Implement real systems like ECS and custom containers from scratch, reinforcing concepts through hands-on work and gaining confidence by building complete, working solutions.

Learn by Building

Turn abstract concepts into efficient implementations, learning how theoretical ideas translate into real-world code you can understand, modify, and confidently apply.

From Theory to Code

Identify performance bottlenecks, measure improvements correctly, and apply practical optimization techniques without guesswork or misleading assumptions about what actually matters.

Debug and Optimize

Use C++20 and C++23 features to write cleaner, more expressive code while reducing boilerplate and improving both safety and performance in everyday development.

Modern C++ Techniques

Build a toolkit of reusable patterns and approaches that transfer across projects, helping you solve new problems faster without relying on memorized solutions.

Reusable Patterns

Learn how to balance performance, readability, and maintainability, making better engineering decisions based on real constraints rather than idealized or purely theoretical scenarios.

Real-World Tradeoffs

What You'll Learn

Become a software engineer with C++.  Starting from the basics, we guide you step by step along the way

Intro to C++ Programming

If you're completely new to programming, we recommend starting with our introductory course:

New to Programming?

Practical DSA

One of the most common ways of connecting storage systems in a performant way is the **sparse set** pattern.  These are designed for **optional one-to-one** relationships, where a record in one collection can be linked to **zero or one** record in another collection.


We cover one-to-many patterns later in the chapter, but for our use case, sparse sets are perfect.  They offer $O(1)$ lookup - that is, if we have a proximity component (an index in our `ProximityStorage`) we can quickly find the entity that "owns" the component (the index in the `EntityStorage`). 


This is the case in both directions - if we have the index in our `EntityStorage`, we can find if that entity has a related record in `ProximityStorage`, and retrieve that record if so.


Sparse sets also offer $O(1)$ insertion and deletion.  We can create and remove these links in constant time.


## The Architecture


A sparse set connects two storage systems together using two arrays:

1. **The Sparse Array**, whose size corresponds to how many entities we have.  That is, the number of records in our `EntityStorage`.
2. **The Dense Array,** whose size corresponds to how many components we have of a specific type.  For example, the number of records in a component pool such as `ProximityStorage`.

For example, if our world had eight entities (with IDs from `0` to `7`) and two proximity components (with IDs `0` and `1`), then the sizes of our dense and sparse arrays would be `8` and `2` respectively:


<Interactive id="dsa-sparse-set-1">


A visual representation of a Sparse Set.


On the left, a faded representation of the EntityStorage.


Immediately to its right, a "Sparse Array" (a tall vertical column) matching the height of the EntityStorage.  The EntityStorage has 8 rows, and the sparse array has 8 slots.


On the right, a faded representation of the ProximityStorage.  Immediately to its left, a "Dense Array" (a short vertical column) matching the height of the ProximityStorage.  The ProximityStorage has 2 rows, and the dense array has 2 slots.


</Interactive>


The relationship between an entity and a proximity component is established by the values in the array slots.


For example, if entity `5` owned the proximity component `0`, then `sparse[5]` would contain the value `0`, and `dense[0]` would contain `5`, effectively linking those two records together.


The sparse array gets its name from the fact that it typically contains a lot of empty space - gaps that are created every time an entity does **not** have a corresponding component.


If an entity does not have a proximity component, we place some sentinel value such as `-1` in that entity's slot within the sparse array:


<Interactive id="dsa-sparse-set-2">


A visual representation of a Sparse Set.


On the left, a faded representation of the EntityStorage.


Immediately to its right, a "Sparse Array" (a tall vertical column) indexed by entity slot. Most slots are empty/null.

- Index 2 contains the integer "0".
- Index 5 contains the integer "1".
- All other indexes contain the integer "-1" and are faded to represent the "null" value

On the right, a faded representation of the ProximityStorage.  Immediately to its left, a "Dense Array" (a short vertical column) with 2 slots

- Index 0 contains the integer 2.
- Index 1 contains the integer 5

Arrows visually connect the corresponding entries


</Interactive>


We then simply repeat this pattern for every other type of component.  Our audio component pool would have its own sparse set.  That would be a sparse array representing the same entities, whose values map to indicies of a dense array corresponding to components within `AudioStorage`, or `-1` if that entity does not have an audio component.


<Aside>


### Isn't the Sparse Array Wasting Memory?


Yes. If there are 1,000,000 rows in the `EntityStorage`, the `sparse` array must have 1,000,000 slots, even if only 5 entities have the component.


This is the trade-off. We trade memory to gain fast reading, writing, and deleting. If we use 4-byte indices like a typical `int`, a 1,000,000-entity collection only costs ~4MB of RAM.  This is generally a good tradeoff.


If we have a lot of entities and memory is a problem, there are variations like **paged sparse sets**, but a basic hash map like `std::unordered_map<int, int>` also works.  It has slightly slower operations but better memory efficiency.  If we need bidirectional lookups, we can use two of them.


</Aside>


## Implementing the Sparse Set


In our case, we're trying to model a situation where only some entities have proximity components.  So, the "sparse" array corresponds to rows in the `EntityStorage`, whilst the "dense" array will match the row count of the `ProximityStorage`.


We'll need multiple sparse sets as we add more systems and relationships between them, so we'll create a dedicated type for this.  We'll use basic `int` indices to keep things simple and memory efficient, but this could also be `size_t` or a template type if we need to support larger collections:


<CodeFile path="dsa_core/include/dsa/SparseSet.h" status="New">


```c++
#pragma once
#include <vector>

class SparseSet {
public:
  // Maps Entity -> Proximity Component
  std::vector<int> m_sparse;
  
  // Maps Proximity Component -> Entity
  std::vector<int> m_dense;
  
  // What value is the "sentinel" in the sparse array?
  static constexpr int null_id = -1;
  
  // If m_sparse[42] == null_id , then entity 42 does
  // not have a proximity component

  // Does a specific entity have a component?
  bool contains(int entity_id) const {
    if (entity_id >= m_sparse.size()) return false;
    return m_sparse[entity_id] != null_id;
  }
};
```


</CodeFile>


## Handling Insertion


To create a link between an entity and a proximity component, our sparse set needs to update its arrays.


The indices we're being asked to link may be outside the bounds of our arrays.  For example, if our sparse array currently has a size of `5` (entities `0`, `1`, `2`, `3`, and `4`) and a request is made to add a component to entity `7`, we need to resize it.


Conceptually, this means that entities `5` and `6` probably exist too - our sparse set just hasn't seen them before because those entities don't have the component type we're tracking.


This means that, in addition to increasing the size of `m_sparse` to support `m_sparse[7]`, we also must fill any intermediate slots that are created by that resizing with our sentinal value `-1`:  


<Interactive id="dsa-sparse-set-3">


Show this


</Interactive>


We may want to consider how we should respond if we receive a request that would create gaps in our supposedly "dense" array, too.  We could throw an exception or use a result type like `std::expected` but, to keep our examples focused on the key concepts, we'll just assume our inputs are always valid:


<CodeFile path="dsa_core/include/dsa/SparseSet.h" status="Updated">


```c++
#pragma once
#include <vector>

class SparseSet {
public:
  // ...

  // Create a link between the two storage systems
  void insert(int entity_id, int dense_index) {
    if (entity_id >= m_sparse.size()) {
      // Grow our array, and assign each new index to the sentinel
      m_sparse.resize(entity_id + 1, null_id);
    }
    m_sparse[entity_id] = dense_index;

    if (dense_index >= m_dense.size()) {
      // Grow our array
      m_dense.resize(dense_index + 1);
    }
    m_dense[dense_index] = entity_id;
  }
};
```


</CodeFile>


### Using the `SparseSet`


Let's use this to let our `ProximityStorage` keep track of which entities own each of the components.


We'll add a `SparseSet` for this, and we'll also update our `Add()` function to receive the entity ID that this new component is for:


<CodeViewer>


<CodeFile path="dsa_core/include/dsa/ProximityStorage.h" status="Updated" defaultOpen>


```c++
#pragma once
#include <vector>
#include <string>
#include "SparseSet.h" //<h>

class ProximityStorage {
public:
  // The Map
  SparseSet m_map; //<h>

  // The Data
  std::vector<float> m_distance;
  std::vector<float> m_angle;
  std::vector<float> m_occlusion;

  // We now require the entity id to add data
  int Add(int entity_id, float dist, float angle, float occ) { //<h>
    // 1. Push data to contiguous arrays
    m_distance.push_back(dist);
    m_angle.push_back(angle);
    m_occlusion.push_back(occ);

    // 2. Update the SparseSet
    // The new data is at the end of the vectors
    int new_index = int(m_distance.size() - 1);//<h>
    m_map.insert(entity_id, new_index); //<h>
    return new_index;
  }
};
```


</CodeFile>


<CodeFile path="benchmarks/main.cpp" status="Updated">


```c++
// ...

static void BM_ContiguousSoA(benchmark::State& state) {
  int n = state.range(0) / 10;
  ProximityStorage ps;

  for (int i = 0; i < n; ++i) {
    // Passing a dummy entity ID
    ps.Add(1, 2.0f, 3.0f, 4.0f);//<h>
  }

  // ...
}

// ...
```


</CodeFile>


</CodeViewer>


## Handling Deletions


This is the most error-prone and confusing part of the process, especially if we want to use the swap-and-pop idiom.  This requires a carefully coordinated set of steps:

1. We need to delete a record from the dense array using swap and pop
2. This invalidates **two** indices in the sparse array, so those need to be updated
3. We need to actually delete the component from our `ProximityStorage`, again using pop and swap.

Let's start with our dense array:


<CodeFile path="dsa_core/include/dsa/SparseSet.h" status="Updated">


```c++
// ...

class SparseSet {
public:
  // ...
  int remove(int entity_id) {
    // Which component needs to be "deleted"?
    int deleted_index = m_sparse[entity_id];
    // Which component will replace it? (the last one)
    int last_entity = m_dense[m_dense.size() - 1];
    // Swap
    m_dense[deleted_index] = last_entity;
    // Pop
    m_dense.pop_back();
    
    // ...more coming soon
    
    return deleted_index;
  }
};
```


</CodeFile>


Our sparse array is up next.  Whichever entity owned the last component needs to be aware that we just swapped it.  Also, the entity that initially requested their component be removed needs to be updated to confirm that this happened:


<CodeFile path="dsa_core/include/dsa/SparseSet.h" status="Updated">


```c++
// ...

class SparseSet {
public:
  // ...
  int remove(int entity_id) {
    // Swap and pop the dense array (proximity components)
    int deleted_index = m_sparse[entity_id];
    int last_entity = m_dense[m_dense.size() - 1];
    m_dense[deleted_index] = last_entity;
    m_dense.pop_back();
    
    // Update the sparse array (entities)
    m_sparse[last_entity] = deleted_index;//<h>
    m_sparse[entity_id] = null_id;//<h>
    
    // ...more coming soon
  }
};
```


</CodeFile>


These `SparseSet` updates have just removed the relationship - we still need to remove the component in our `ProximityStorage`.  To help with this, our `SparseSet` can return the index that it just swapped and popped:


<CodeFile path="dsa_core/include/dsa/SparseSet.h" status="Updated">


```c++
// ...

class SparseSet {
public:
  // ...
  int remove(int entity_id) {
    // Swap and pop the dense array (proximity components)
    int deleted_index = m_sparse[entity_id];
    int last_entity = m_dense[m_dense.size() - 1];
    m_dense[deleted_index] = last_entity;
    m_dense.pop_back();
    
    // Update the sparse array (entities)
    m_sparse[last_entity] = deleted_index;
    m_sparse[entity_id] = null_id;

    return deleted_index; //<h>
  }
};
```


</CodeFile>


Over in our `ProximityStorage`, we can finally integrate everything.  We ask the `SparseSet` to erase the relationship, and we use its return value to swap and pop the corresponding component:


<CodeFile path="dsa_core/include/dsa/ProximityStorage.h" status="Updated">


```c++
// ...

class ProximityStorage {
public:
  // ...
  void Remove(int entity_id) {
    if (!m_map.contains(entity_id)) return;

    // Update the map and get the index of the gap we need to fill
    int index = m_map.remove(entity_id); //<h>

    // Perform the Swap-and-Pop on the data
    // We swap the back element into the 'index' slot...
    std::swap(m_distance[index], m_distance.back());
    // ...and then pop the back element
    m_distance.pop_back();
    
    // Repeat for all columns
    std::swap(m_angle[index], m_angle.back());
    m_angle.pop_back();
    
    std::swap(m_occlusion[index], m_occlusion.back());
    m_occlusion.pop_back();
  }
};
```


</CodeFile>


## Bringing It All Together


We now have two storage systems, with some basic bookkeeping that links them together behind the scenes:


<CodeFile path="dsa_app/main.cpp" status="New">


```c++
#include <dsa/EntityStorage.h>
#include <dsa/ProximityStorage.h>

int main() {
  EntityStorage entities;
  ProximityStorage proximity;
  
  // Create a player
  int alice = entities.Add("Alice");
  
  // Player is close
  proximity.Add(alice, 1.0f, 2.0, 3.0f);
  
  // Not any more
  proximity.Remove(alice);
}
```


</CodeFile>


In the next lesson, we'll strengthen these capabilities further, letting us get the data we need in a cohesive and joined-up way, regardless of what underlying storage system it's coming from.


## Complete Code


A complete version of the example code is below:


<CodeViewer>


<CodeFile path="dsa_app/main.cpp">


```c++
#include <dsa/EntityStorage.h>
#include <dsa/ProximityStorage.h>

int main() {
  EntityStorage entities;
  ProximityStorage proximity;
  
  // Create a player
  int alice = entities.Add("Alice");
  
  // Player is close
  proximity.Add(alice, 1.0f, 2.0f, 3.0f);
  
  // Not any more
  proximity.Remove(alice);
}
```


</CodeFile>


<CodeFile path="dsa_core/include/dsa/ProximityStorage.h">


```c++
#pragma once
#include <vector>
#include <string>
#include "SparseSet.h"

class ProximityStorage {
public:
  SparseSet m_map;
  std::vector<float> m_distance;
  std::vector<float> m_angle;
  std::vector<float> m_occlusion;

  int Add(int entity_id, float dist, float angle, float occ) {
    m_distance.push_back(dist);
    m_angle.push_back(angle);
    m_occlusion.push_back(occ);

    int new_index = int(m_distance.size() - 1);
    m_map.insert(entity_id, new_index);
    return new_index;
  }

  void Remove(int entity_id) {
    if (!m_map.contains(entity_id)) return;

    int index = m_map.remove(entity_id);
    std::swap(m_distance[index], m_distance.back());
    m_distance.pop_back();

    std::swap(m_angle[index], m_angle.back());
    m_angle.pop_back();

    std::swap(m_occlusion[index], m_occlusion.back());
    m_occlusion.pop_back();
  }
};
```


</CodeFile>


<CodeFile path="dsa_core/include/dsa/EntityStorage.h" defaultOpen>


```c++
#pragma once
#include <vector>
#include <string>
#include <ranges>
#include <memory>

struct AudioComponent {
  float volume;
  float pitch;
  float pan;
};

class EntityStorage {
public:
  std::vector<std::string> m_names;
  std::vector<std::unique_ptr<AudioComponent>> m_audio;

  int Add(std::string name) {
    m_names.push_back(std::move(name));
    m_audio.push_back(nullptr);
    return int(m_names.size() - 1);
  }

  void AddAudioToEntity(int index) {
    m_audio[index] = std::make_unique<AudioComponent>();
  }
};
```


</CodeFile>


<CodeFile path="dsa_core/include/dsa/SparseSet.h">


```c++
#pragma once
#include <vector>

class SparseSet {
public:
  std::vector<int> m_sparse;
  std::vector<int> m_dense;
  static constexpr int null_id = -1;

  bool contains(int entity_id) const {
    if (entity_id >= m_sparse.size()) return false;
    return m_sparse[entity_id] != null_id;
  }

  void insert(int entity_id, int dense_index) {
    if (entity_id >= m_sparse.size()) {
      m_sparse.resize(entity_id + 1, null_id);
    }
    m_sparse[entity_id] = dense_index;

    if (dense_index >= m_dense.size()) {
      m_dense.resize(dense_index + 1);
    }
    m_dense[dense_index] = entity_id;
  }

  int remove(int entity_id) {
    int deleted_index = m_sparse[entity_id];
    int last_entity = m_dense[m_dense.size() - 1];
    m_dense[deleted_index] = last_entity;
    m_dense.pop_back();
    
    m_sparse[last_entity] = deleted_index;
    m_sparse[entity_id] = null_id;

    return deleted_index;
  }
};
```


</CodeFile>


<CodeFile path="benchmarks/main.cpp">


```c++
#include <benchmark/benchmark.h>
#include <random>
#include <dsa/EntityStorage.h>
#include <dsa/ProximityStorage.h>

static void BM_PointerChasing(benchmark::State& state) {
  int n = state.range(0);
  EntityStorage es;

  std::mt19937 rng(42);
  std::uniform_int_distribution<int> dist(0, 9);
  for (int i = 0; i < n; ++i) {
    es.Add("Player");
    if (dist(rng) == 0) {
      es.AddAudioToEntity(i);
    }
  }

  for (auto _ : state) {
    float total_volume = 0.0f;
    for (const auto& audio_ptr : es.m_audio) {
      if (audio_ptr) {
        total_volume += audio_ptr->volume;
      }
    }
    benchmark::DoNotOptimize(total_volume);
  }
}

static void BM_ContiguousSoA(benchmark::State& state) {
  int n = state.range(0) / 10;
  ProximityStorage ps;

  for (int i = 0; i < n; ++i) {
    ps.Add(1, 1.0f, 2.0f, 3.0f);
  }

  for (auto _ : state) {
    float total_distance = 0.0f;
    for (float dist : ps.m_distance) {
      total_distance += dist;
    }
    benchmark::DoNotOptimize(total_distance);
  }
}

#define BENCHMARK_CONFIG(name) \
  BENCHMARK(name) \
    ->RangeMultiplier(10) \
    ->Range(100'000, 10'000'000) \
    ->Unit(benchmark::kMillisecond)

BENCHMARK_CONFIG(BM_PointerChasing);
BENCHMARK_CONFIG(BM_ContiguousSoA);
```


</CodeFile>


</CodeViewer>


## Summary


We have successfully transitioned from a single monolithic storage system to a flexible composition of systems.

- **SoA** provides the fastest possible iteration speed but lacks flexibility for optional data.
- **Memory Indirection** using techniques like `vector<unique_ptr>` handles optional data but destroys performance via cache misses and branch mispredictions.
- **Sparse Sets** bridge the gap. They allow us to keep data packed in contiguous arrays while providing a mapping between storage systems.

O(1) Deletions (Swap-and-Pop)

ECS back and forth - Part 2

Discover how to link entities to their components using Sparse Sets in C++. Master O(1) lookups, insertions, and swap-and-pop deletions for high-performance Entity Component Systems.

Relational Data and Sparse Sets

Understanding the Basics

Practical Applications

Common Mistakes

Next Steps

Additional Resources

Assessment Preparation

Practical DSA