I'm currently trying to wrap my head around Entity, Component and Systems and I'm having a few problems with my design so far.
Basically Entities is a class that contains an index-value and an unique id associated with said index. I feel the way I create, store, recycle and iterate through the entities in the manger is quite unefficient and the code is filled with cluttery. I'm currently using a number of vectors that is somewhat hard to keep synced ( index-wise ) with each other.

#ifndef ENTITYMANAGER_HPP
#define ENTITYMANAGER_HPP

#include <vector>
#include "Entity.hpp"
#include "Component.hpp"
#include "System.hpp"

class EntityManager {
private:
	unsigned int indexCount;

	std::vector< Entity* > activeEntities; 
	std::vector< Entity* > deadEntities;
	std::vector< std::vector<Component*> > components;
	std::vector< System* > systems;
public:
	EntityManager();
	~EntityManager();

	Entity createEntity();

	void killEntity(Entity entity);
	void registerComponent(Entity entity, Component* component);
	void removeComponent(Entity entity, CID cid);
	
	Component* getComponent(Entity entity, CID cid);
	
	bool isAlive(Entity entity);

	void invokeSystems();
};

#endif

#include "EntityManager.hpp"
#include "DummySystem.hpp"

EntityManager::EntityManager():indexCount(0) {
	 deadEntities.reserve(100);
	 activeEntities.reserve(100);
	 // This will initialize 100, like reserve but for 2D vectors.
	 components.reserve(100);
	 components.resize(100, std::vector<Component*>(CID::UNIQUE_COUNT, nullptr) );
	 systems.push_back(new DummySystem(this));
}

EntityManager::~EntityManager() {
	for(Entity* e : activeEntities) delete e;
	for(Entity* e : deadEntities) delete e;
	for(System* s : systems) delete s;
	for(auto& v : components)
		for(Component* c : v) delete c;
}

Entity EntityManager::createEntity() {
	// Try to recycle a dead entity
	if ( !deadEntities.empty() ) {
		Entity* entity = deadEntities.back();
		deadEntities.pop_back();
		// Give it a new unique id to make sure it is treated as a new entity
		entity->setUID(entity->getUID()+1);
		activeEntities[entity->getIndex()] = entity;
		return (*entity); 
	}
	
	Entity* entity = new Entity(indexCount++,0);
	activeEntities.push_back(entity);
	components.push_back( std::vector<Component*>(CID::UNIQUE_COUNT) );
	return (*entity);
}

void EntityManager::killEntity(Entity entity) {
	if (!isAlive(entity)) return;
	for(int i = 0; i < CID::UNIQUE_COUNT; i++) {
		delete components[entity.getIndex()][i];
		components[entity.getIndex()][i] = nullptr;
	}
	deadEntities.push_back(activeEntities[entity.getIndex()]);
	activeEntities[entity.getIndex()] = nullptr;
}

Component* EntityManager::getComponent(Entity entity, CID cid) {
	if (!isAlive(entity)) return nullptr;
	return components[entity.getIndex()][cid];
}

bool EntityManager::isAlive(Entity entity) {
	if ( activeEntities.empty() ) return false;
	if ( activeEntities[entity.getIndex()] == nullptr ) return false;
	if ( activeEntities[entity.getIndex()]->getUID() != entity.getUID()) return false;
	return true;
}

void EntityManager::registerComponent(Entity entity, Component* component) {
	if (!isAlive(entity)) return;
	if ( component == nullptr ) return;

	if ( components[entity.getIndex()][component->getCID()] != nullptr )
		delete components[entity.getIndex()][component->getCID()];
	components[entity.getIndex()][component->getCID()] = component;
}

void EntityManager::removeComponent(Entity entity, CID cid) {
	if (!isAlive(entity)) return;
	if ( components[entity.getIndex()][cid] != nullptr )
		delete components[entity.getIndex()][cid];
	components[entity.getIndex()][cid] = nullptr;
}

void EntityManager::invokeSystems() {
	for(Entity* e : activeEntities)
		if (e != nullptr)
			for(System* sys : systems) sys->process(e);
}

Should I rather use another container? Like std::set or std::map and just use a unsigned int id as a key?
Should the EntitySystem handle both entities, components and systems?

As you separated the components already from the entities, I think it would get simpler if you dont put all components belonging to one entity into one array, but put all components of a single component-type into an array and if you try to not put all that lowlevel array handling inside that single manager class.

I would also remove the index from the entity and just keep the entity-id. Then I would make a templated helper class that manages one array containing all components of one type and provides a means to iterate over all components of that single type and update them, but also contains methods to add a component, find a component belonging to an entity id and delete it. There you can either safe the entity-id inside each component and do a search in the rare case(try to make components not depend on other components of the same entity to reduce this) you need to do this (and either keep them sorted and do a binary search or unsorted and linear search depending on whats faster), or have a second index array or map to convert an entity-id to the array-index. That helper class can then be used by (and maybe contained inside) the systems that update all components of the corresponding type (for example health-system updates all health-components).

I would keep the entity-array, but remove the dead entity array and automatically assume a non-existing entity is dead. You just use it to generate an entity at a free id, check if an entity exists and to delete one entity (though you would need to tell all component arrays before or after that to remove the associated components). That functionality could also be extracted into a helper class.

As you separated the components already from the entities, I think it would get simpler if you dont put all components belonging to one entity into one array, but put all components of a single component-type into an array and if you try to not put all that lowlevel array handling inside that single manager class.

This is the approach I'm currently using and it's working fine at the moment, although I cannot comment on performance as the game I'm making is pretty simple. I've created a 'ComponentCollection' class which abstracts the syncing of the two vectors away from my higher level classes. Here are some of the method/function signatures included in the public interface:

	/**
	 * Associates the UID with the component.
	 * 
	 * The component can only be added if:
	 * 
	 * <ul>
	 * <li> The UID has not already been added </li>
	 * <li> If a UID with the same index is currently mapped to a component, then this
	 *      new UID will be mapped to the new component (overwriting the old mapping) only if
	 *      the salt in the new UID is greater than the salt in the currently mapped UID. </li> 
	 * </ul>
	 * 
	 * @throws NullPointerException if gameObjectID or component are null.
	 * 
	 * @param gameObjectID		UID of game object.
	 * @param component			component to be mapped to the UID. Cannot be null.
	 * 
	 * @return True if successfully added, false otherwise
	 */
	public boolean add(UID gameObjectID, ComponentType component);


	/**
	 * Gets the component mapped to the game object UID passed in.
	 * 
	 * @throws IllegalArgumentException if there is no component mapped to the UID (including if there is a
	 * 			component mapped, but the component's UID has a different salt.
	 * 
	 * @throws NullPointerException if gameObjectID is null.
	 * 
	 * @param gameObjectID		UID to lookup.
	 * 
	 * @return component mapped to UID
	 */
	public ComponentType get(UID gameObjectID);


	/**
	 * Removes the mapping of UID to component for the UID gameObjectID
	 * @param gameObjectID		UID for which the mapping is to be removed
	 * 
	 * @throws NullPointerException if gameObjectID is null.
	 * 
	 * @return	True if component mapping was removed, False otherwise.
	 */
	public boolean remove(UID gameObjectID);

UID is a wrapper class containing your 'CID' and 'index'.

I would also remove the index from the entity and just keep the entity-id. Then I would make a templated helper class that manages one array containing all components of one type and provides a means to iterate over all components of that single type and update them, but also contains methods to add a component, find a component belonging to an entity id and delete it. There you can either safe the entity-id inside each component and do a search in the rare case(try to make components not depend on other components of the same entity to reduce this) you need to do this (and either keep them sorted and do a binary search or unsorted and linear search depending on whats faster), or have a second index array or map to convert an entity-id to the array-index. That helper class can then be used by (and maybe contained inside) the systems that update all components of the corresponding type (for example health-system updates all health-components).

I would keep the entity-array, but remove the dead entity array and automatically assume a non-existing entity is dead. You just use it to generate an entity at a free id, check if an entity exists and to delete one entity (though you would need to tell all component arrays before or after that to remove the associated components). That functionality could also be extracted into a helper class.

If I remove the entity index and just keep the id how would I recycle old entities? As well as making sure that an old entity that should be dead is validated as alive seeing as it exists in the same index? I'm a tad confused. What do you mean just generate an entity at a free id? How do I keep track of which id's are free?

Also regarding the templated helper functions, how would that look like? Could you give me an example?

You remove the component index from the entity because there are different component arrays where it would need to be different. So you just keep an array that basically contains all entity-ids that are alive and these ids need to be unique(you can package each id into the entity class if you like). You can easily find a free id because you know the used ids then. If you keep a counter (a static in the Entity class for example) that starts at 1 when the game loads and increase it by 1 every time you create an entity you easily get unique id numbers. Just remember to check for overflow before the +1 for safety, and if you really need more than 2^32 entities you can use 64 bit, renumber all entities or read through the whole sorted array to find gaps.

For deleting an entity you can just remove it from the vector. You could just replace the id in a deleted entity by 0 to avoid moving everything on deletion, but then you always have to look for free places in the whole array and get an unsorted mess of id numbers and waste memory and need to resort and possibly compact the array later anyway. Then tell all systems that id so they can delete the associated components.

That template I told about was only a helper to contain the array with all components of one type (and maybe some kind of index-map to convert an entity id to the arrayindex where the corresponding component is stored, but that can also be replaced by a binary search) to handle the low level work. It should be a template just so that the exact type of the component can be used inside the array so you dont need shared pointers or up/down-casting.

// I just typed that in here as an incomplete example, may contain errors, other approaches may be useful
class Component {
  IDNumber entityID;
  // todo
};

class PositionComponent : public Component {
  // todo
};

template<class C> class ComponentTable {
  std::vector<C> components;
public:
  std::vector<C>::iterator begin();
  std::vector<C>::iterator end();
  C& findComponent(IDNumber entityid);
  void deleteComponent(IDNumber entityid);
  void addComponent(C&& component);
};

class PositionSystem {
  ComponentTable<PositionComponent> components;
  // todo
};

You remove the component index from the entity because there are different component arrays where it would need to be different. So you just keep an array that basically contains all entity-ids that are alive and these ids need to be unique(you can package each id into the entity class if you like). You can easily find a free id because you know the used ids then. If you keep a counter (a static in the Entity class for example) that starts at 1 when the game loads and increase it by 1 every time you create an entity you easily get unique id numbers. Just remember to check for overflow before the +1 for safety, and if you really need more than 2^32 entities you can use 64 bit, renumber all entities or read through the whole sorted array to find gaps.

For deleting an entity you can just remove it from the vector. You could just replace the id in a deleted entity by 0 to avoid moving everything on deletion, but then you always have to look for free places in the whole array and get an unsorted mess of id numbers and waste memory and need to resort and possibly compact the array later anyway. Then tell all systems that id so they can delete the associated components.

That template I told about was only a helper to contain the array with all components of one type (and maybe some kind of index-map to convert an entity id to the arrayindex where the corresponding component is stored, but that can also be replaced by a binary search) to handle the low level work. It should be a template just so that the exact type of the component can be used inside the array so you dont need shared pointers or up/down-casting.

// I just typed that in here as an incomplete example, may contain errors, other approaches may be useful
class Component {
  IDNumber entityID;
  // todo
};

class PositionComponent : public Component {
  // todo
};

template<class C> class ComponentTable {
  std::vector<C> components;
public:
  std::vector<C>::iterator begin();
  std::vector<C>::iterator end();
  C& findComponent(IDNumber entityid);
  void deleteComponent(IDNumber entityid);
  void addComponent(C&& component);
};

class PositionSystem {
  ComponentTable<PositionComponent> components;
  // todo
};

Well I guess that makes sense ... somewhat. When we want to check if an entity is alive or if an entity has X-component wouldn't we need to iterate the ( possibly ) WHOLE vector to find a match? The same when "deleting" an object and it's associated components. We basically need to iterate through all vectors the entity was relevant in?

You are right that these could be problems sometimes. The idea is that things like updating a whole array of a component type are done every frame, but deleting an entity (the slowest operation) is done much less often.

Checking every entity for some condition is a thing one shouldn't do and the goal is avoiding it by design. If you only had a single entity array you would need to loop over all entities and check each (and get branch mispredictions+cache trashing) and then maybe do some operation on it; but having many specialized shorter arrays that also contain smaller objects makes it mostly only a matter of choosing one of the arrays and then doing the operation on the whole component array.

The good thing is the whole problem is isolated (in the example inside the ComponentTable class). You can easily profile later on and adapt the data structure and how it is used. There are many ways to implement it:

- unsorted array: new component is an easy append with O(1), deleting is just find and one move, find is O(N)

- sorted array: new is still append if its a new entity with a higher id number, O(N) insert if its a new component for an old entity, finding O(log2(N)), deleting O(N), for the rare case you need to have a component that is related to another (which should be avoided), you gain the possibility to iterate over a secondary component array at the same time and occasionally skip a few (instead of many searches in unsorted case)

- set: faster insert, find is O(log(N))

- hash set: even faster find, but may need rehashing on inserts

- sorted/unsorted array for data and a short sorted array as index (if you adapt the creation of entity id numbers to fill gaps to keep the index array small)

- sorted/unsorted array for data and map as index

- sorted/unsorted array for data and hash map as index

In some cases you can also choose if you want to remove the entity id from the components to reduce their size and instead put it into the indices.

The reason I ask is because: What if you have a homing missile targeting an entity. The homing missile would need to know whether or not the target is still valid. Running a isValid(Entity e) every frame might be quite expensive considering there is a lot of entities. But I guess the object could subscribe to an "onDeletion" event for that or something similar.

Thanks a lot! I will try to implement this ASAP. I feel that ECS plays so nicely along with OOP.

I guess you wont have thousands of those missiles flying at all time. A missile looking up a single position component of its target and then stearing in that direction should be fast enough to do every frame.

The reason I ask is because: What if you have a homing missile targeting an entity. The homing missile would need to know whether or not the target is still valid. Running a isValid(Entity e) every frame might be quite expensive considering there is a lot of entities. But I guess the object could subscribe to an "onDeletion" event for that or something similar.

I would open a temporary container for entities that are targeted by the homing missile triggered by the entity who throws out the homing missile, therefore the homing missiles only look up that container instead of the whole entity list. I simply need a weapon component that has this container and store temporary data of (pointing to) targeted entities to it, and start firing to that temporary list of entities until the missile entities are destroyed. There you only iterate the homing missiles to the targeted positions of your alive entities. I won't iterate everything just to check all entities whether they are targeted or not.