Designs of an entity component system

I wonder how to implement the fastest version of an entity component system (ECS from now on) in C++.

First off, regarding terminology:

a Scene is a container for Entities (and Systems in some implementations)
a Component is a simple data storage (like position, collision box, image to render etc)
a System performs logic on Components fitting the System's requirements (this could be physics, player input, simple rendering etc.)
an Entity contains several Components to make up the final behavior

I listed all the designs we came up with below.

1. The "naive" way

The Scene contains all Entities unordered.
As the Systems update, every System has to loop through all Entities and check whether each Entity contains all required Components and then perform the update upon those Entities.

Obviously, this way is not too performant when having a lot of Systems and/or a lot of Entities.

2. Using "bitmask enums" and mapping

Each Component contains a type identifier in the form of a bitmask (e.g. 1u << 5 / binary [0...]100000). Each Entity can then compose all Component's type identifiers (assuming all typeIDs are unique inside the Entity), so it looks something like

1u << 5 | 1u << 3 | 1u << 1
binary [0...]101010

The Scene contains some kind of map where Systems can easily look up fitting Entities:

MovementSystem::update() {
    for (auto& kv : parent_scene_) { // kv is pair<TypeID_t, vector<Entity *>>
        if (kv.first & (POSITION | VELOCITY))
            update_entities(kv.second); // update the whole set of fitting entities
    }
}

Pros:

Faster than the naive way

Cons:

Systems have to look up appropriate Entities every single time they are updated.
A bitmask (enum) is limited to a number of bits (32 for uint32_t, at least 64 for unsigned long long) and in some cases you might need more Components than the bitmask allows.

3. Using no Systems

This method is described by Danvil in an answer below.

Pros:

Gets rid of the bitmask thing completely.
Likely to be faster than design #2.

Cons:

Relies on dynamic_cast for looking up a component whereas design #2 can directly look up a component and then safely static_cast it.

4. Using spare sets

This method has been described in by skypjack in an answer below. He explained his approach in great detail, so I'd suggest you read his answer.

Solution

I would say what you call a "System" is actually a component. An example for rendering: there is a component Pose (for 3D location rotation) and a component Mesh (holds vertex buffers). Now instead of having a function which checks if it can render that particular entity, add a component Renderer. This component connects to the Pose and Mesh components. The "System" rendering now only has to communicate with the component Renderer. And each entity is either renderable or it is now, there is not need for checking components each time and all work for rendering is collected as a component.

Code example:

struct Pose : public Component { float x,y; };

struct Mesh : public Component { std::vector<Vertex> vertices; };

struct Renderer : public Component {
   Entity* entity;
   void render() {
       if(!mesh|| entity->componentsChanged) {
           mesh = entity->getComponent<Mesh>();
           if(!mesh) throw error;
       }
       if(!entity->pose) throw error;
       glTranslate(entity->pose->x, entity->pose->y);
       ...
   }
private:
   Mesh* mesh;
};

struct Entity {
    std::vector<Component*> components;
    bool componentsChanged;
    template<typename C> C* getComponent() const {
        for(Component* c : components) {
            C* cc = dynamic_cast<C>(c);
            if(cc) return cc;
        }
        return NULL;
    }
    // "fast links" to important components
    Pose* pose;
    Renderer* renderer;
    PhysicsStuff* physics;
};

struct Rendering
{
private:
    void render(const std::vector<Entity*>& entities) {
        for(Entity* e : entities) {
            if(!e->renderer) continue;
            e->renderer->render();
        }
    }
};