Your Game Has 500 Objects — How Do You Store Them Without Losing Your Mind (or Your Cache Lines)?

In a game engine, you might have hundreds of entities: agents, doors, walls, triggers, quantum nodes. Each entity can carry a different set of components — one has a Transform and an Agent, another has a Transform and a Wall, a third has a Transform, a PhysicsComponent, and an Inventory. The engine needs to add components to entities, look them up by entity ID, iterate over all components of a given type efficiently, and remove components without fragmenting memory.

The naive approach — a std::map<EntityID, std::map<std::string, void*>> — is slow, unsafe, and fragile. This tutorial walks through the Multiversal Consciousness engine’s actual solution: a type-erased Component Registry backed by contiguous arrays, with O(1) entity-to-component lookup, cache-friendly iteration, and a swap-and-pop deletion strategy that maintains array density. All without external ECS libraries.

What You Need: Templates, Type Erasure, and std::type_index

Knowledge prerequisites:

• Class templates and how template type parameters work
• Virtual functions and polymorphism (the concept of a base class pointer to a derived class)
• std::unordered_map for O(1) lookup
• Move semantics (std::move)
• std::type_index — a wrapper around typeid() that can be used as a hash map key

Environment:

• C++17 or later (for std::type_index, structured bindings, if constexpr)
• No external dependencies — this is pure standard library code

A Filing Cabinet with Self-Organizing Drawers

Imagine a filing cabinet where each drawer is labeled with a component type — one drawer for Transform, one for PhysicsComponent, one for Inventory. Inside each drawer, folders are arranged in a contiguous row. Each folder has two things: the entity ID on the tab, and the component data inside.

When a system needs to process all physics objects, it opens the PhysicsComponent drawer and reads straight through — no jumping between drawers, no scanning irrelevant entities. When an entity is destroyed, its folder is swapped with the last folder in the drawer and then the last slot is popped off — keeping the row contiguous without shifting everything.

graph TB
    subgraph ComponentRegistry
        direction LR
        CR["containers_<br/>map: type_index → IComponentContainer*"]
    end

    subgraph TransformDrawer["ComponentContainer&lt;Transform&gt;"]
        direction TB
        TM["entity_to_index_<br/>{E1→0, E3→1, E5→2}"]
        TC["components_<br/>[Transform₁, Transform₃, Transform₅]"]
        TE["entities_<br/>[E1, E3, E5]"]
    end

    subgraph PhysicsDrawer["ComponentContainer&lt;PhysicsComponent&gt;"]
        direction TB
        PM["entity_to_index_<br/>{E1→0, E5→1}"]
        PC["components_<br/>[Physics₁, Physics₅]"]
        PE["entities_<br/>[E1, E5]"]
    end

    CR -->|"typeid(Transform)"| TransformDrawer
    CR -->|"typeid(PhysicsComponent)"| PhysicsDrawer

From Raw Maps to Contiguous Arrays: Building the ECS Step by Step

Step 1: Define entity IDs and the entity manager

Entities are plain integers. The EntityManager hands out IDs and recycles them through a FIFO queue so destroyed IDs are not reused immediately, reducing the window for stale-reference bugs.

using EntityID = uint32_t;
constexpr EntityID INVALID_ENTITY = 0;

class EntityManager {
private:
    std::queue<EntityID> available_ids_;          // Recycled IDs
    std::unordered_set<EntityID> active_entities_; // Live entities
    EntityID next_id_ = 1;                        // 0 is reserved

public:
    EntityID create_entity() {
        EntityID id;
        if (!available_ids_.empty()) {
            id = available_ids_.front();  // Reuse a recycled ID
            available_ids_.pop();
        } else {
            id = next_id_++;              // Mint a fresh ID
            if (next_id_ == INVALID_ENTITY) next_id_ = 1;  // Skip 0 on overflow
        }
        active_entities_.insert(id);
        return id;
    }

    bool destroy_entity(EntityID entity) {
        if (entity == INVALID_ENTITY ||
            active_entities_.find(entity) == active_entities_.end())
            return false;

        active_entities_.erase(entity);
        available_ids_.push(entity);    // Recycle, don't discard
        return true;
    }

    bool is_valid(EntityID entity) const {
        return entity != INVALID_ENTITY &&
               active_entities_.count(entity) > 0;
    }
};

Step 2: Define the type-erased container interface

We need a non-templated base class so the registry can hold containers of different component types in a single map. This interface exposes only the operations that don’t need to know the concrete type: remove, check existence, clear, count.

class IComponentContainer {
public:
    virtual ~IComponentContainer() = default;
    virtual bool remove_component(EntityID entity) = 0;
    virtual bool has_component(EntityID entity) const = 0;
    virtual void clear() = 0;
    virtual size_t size() const = 0;
};

Step 3: Build the templated concrete container

This is where the real work happens. Three parallel data structures work together:

• entity_to_index_ — O(1) lookup from entity ID to array index
• components_ — contiguous array of component data (cache-friendly)
• entities_ — parallel array so we can iterate entities and components in lockstep

template<typename T>
class ComponentContainer : public IComponentContainer {
private:
    std::unordered_map<EntityID, size_t> entity_to_index_;
    std::vector<T> components_;
    std::vector<EntityID> entities_;

public:
    void add_component(EntityID entity, T&& component) {
        auto it = entity_to_index_.find(entity);
        if (it != entity_to_index_.end()) {
            components_[it->second] = std::move(component); // Update
        } else {
            size_t index = components_.size();
            entity_to_index_[entity] = index;               // Map
            components_.push_back(std::move(component));     // Store
            entities_.push_back(entity);                     // Track
        }
    }

    T* get_component(EntityID entity) {
        auto it = entity_to_index_.find(entity);
        return (it != entity_to_index_.end()) ? &components_[it->second] : nullptr;
    }

Step 4: Implement swap-and-pop deletion

This is the critical optimization. Erasing from the middle of a std::vector is O(n) because every element after the deletion point must shift left. Swap-and-pop is O(1): move the last element into the gap, then pop the back.

    bool remove_component(EntityID entity) override {
        auto it = entity_to_index_.find(entity);
        if (it == entity_to_index_.end()) return false;

        size_t removed_index = it->second;
        size_t last_index = components_.size() - 1;

        if (removed_index != last_index) {
            // Swap the removed slot with the last element
            components_[removed_index] = std::move(components_[last_index]);
            entities_[removed_index] = entities_[last_index];

            // Fix the moved entity's index in the map
            entity_to_index_[entities_[removed_index]] = removed_index;
        }

        // Pop the (now-duplicated) last slot
        components_.pop_back();
        entities_.pop_back();
        entity_to_index_.erase(entity);
        return true;
    }

Step 5: Wire it all together in the ComponentRegistry

The registry maps std::type_index to IComponentContainer pointers. When you call add_component<Transform>(entity, t), the registry creates the container on first use, then delegates to the concrete ComponentContainer<Transform>.

class ComponentRegistry {
private:
    std::unordered_map<std::type_index,
                       std::unique_ptr<IComponentContainer>> containers_;

    template<typename T>
    ComponentContainer<T>& get_container() {
        auto type_id = std::type_index(typeid(T));
        auto it = containers_.find(type_id);
        if (it == containers_.end()) {
            auto container = std::make_unique<ComponentContainer<T>>();
            auto* ptr = container.get();
            containers_[type_id] = std::move(container);
            return *ptr;
        }
        return static_cast<ComponentContainer<T>&>(*it->second);
    }

public:
    template<typename T>
    void add_component(EntityID entity, T&& component) {
        get_container<T>().add_component(entity, std::forward<T>(component));
    }

    template<typename T>
    T* get_component(EntityID entity) {
        return get_container<T>().get_component(entity);
    }

    template<typename T>
    const ComponentContainer<T>* get_all_components() const {
        // Systems use this to iterate all components of a type
        return get_container<T>();
    }

    void remove_all_components(EntityID entity) {
        for (auto& [type_id, container] : containers_) {
            container->remove_component(entity);
        }
    }
};

Cache Lines, Contiguity, and Why Parallel Arrays Beat Maps

On modern CPUs, a cache line is typically 64 bytes. When the physics system iterates over every PhysicsComponent, contiguous storage in a std::vector means the CPU prefetcher can load the next component before the current one is finished processing. If components were scattered across individual heap allocations (as in std::map<EntityID, PhysicsComponent*>), each access would likely be a cache miss — potentially 100x slower for tight loops.

Complexity breakdown for ComponentContainer<T>:

Compare this to the naive std::map<EntityID, Component> approach: insertion is O(log n), lookup is O(log n), deletion is O(log n), and iteration involves chasing pointers through a red-black tree with no spatial locality.

The static_cast from IComponentContainer* to ComponentContainer<T>* is safe because get_container<T>() always stores the container under typeid(T), and only retrieves it with the same type parameter. The type is guaranteed to match by construction, not by runtime checking. This avoids the cost of dynamic_cast while maintaining correctness.

The Traps in the Type Erasure: What Can Go Wrong

The static_cast in get_container() is safe only because the registry enforces the invariant that each type_index maps to the correct ComponentContainer<T>. If a bug caused a typeid(Transform) entry to store a ComponentContainer<Agent>, the cast would silently reinterpret memory — no exception, no crash, just corrupted data. This is why the private get_container() method is the only path to the underlying storage. Never expose the raw containers_ map.

Component types must be move-constructible. The engine enforces this with a static_assert at the add_component call site. If you define a component with a deleted move constructor, compilation fails with a clear message rather than a cryptic template error deep in std::vector.

Stale entity references. If a system caches a T* pointer from get_component() and then another system removes a different entity’s component (triggering a swap-and-pop), the cached pointer may now point to a different entity’s data. The engine mitigates this by designing systems to query components fresh each frame rather than caching pointers across updates.

Thread safety. The ComponentRegistry is not thread-safe. If two systems run concurrently and both call add_component, the underlying vectors may reallocate and invalidate each other’s pointers. The engine avoids this by running all systems sequentially on the main thread — a deliberate architectural constraint that trades parallelism for simplicity.

Thread Safety, Pointer Invalidation, and the Limits of This Design

The ComponentRegistry is not thread-safe. If two systems run concurrently and both call add_component, the underlying vectors may reallocate and invalidate each other’s pointers. The engine avoids this by running all systems sequentially on the main thread — a deliberate constraint that trades parallelism for simplicity.

The other thing to watch: if a system caches a T* pointer from get_component() and then another system removes a different entity’s component (triggering a swap-and-pop on the same container), that cached pointer may now point to a different entity’s data. The engine mitigates this by querying components fresh each frame rather than storing raw pointers across updates.

The pattern you’ve built here — type-erased heterogeneous storage with O(1) access and O(1) deletion — shows up well beyond game engines. Plugin architectures, serialization frameworks, event buses all use the same idea: a non-templated base interface for the container, templated concrete implementations behind it, and a type-keyed registry to tie them together.