In my humble opinion, trying to allow an ECS to let clients use their own containers and allocators is overkill. An ECS doesn't have that many responsibilities to be experimenting with an endless variety of data structures and allocators. It boils down to simply associating components to an entity aggregate and querying available components and entities in the system. There should be data structures and allocation strategies available which cover the needs of a wide range of people very efficiently without the temptation to try other data structures or allocators. Personally I'd rather have an ECS library which uses minimal memory and is super fast for all my needs over one where I can explore endless combinations of data structures and allocation strategies. The latter doesn't necessarily lead to the former.
That said, I'll get to how to do this later but first I want to offer a different perspective to try to persuade you why it's not necessarily so fruitful to do this.
For me, I have an ECS where I can actually create a particle emitter which emits 2 million particles where every single little particle is implemented as a separate entity with a particle component attached while animating all 2 millions particle entities/components and visualizing them at over 30 FPS. Every single frame has the particle system querying the ECS for all entities which have a particle component attached. Now this is normally a very dumb thing to do -- to represent every single particle as a separate entity with a separate component, but it was a stress test to demonstrate the efficiency of the system. The memory overhead of an entity is 8 bytes while the memory overhead of a component is 16 bytes (24 bytes of unnecessary overhead per particle when representing each individual one as an entity with a component attached, but not bad).
In my case the data structures used are very simple and coded in C for ABI compatibility with a C API (though with C++ wrappers on top):
struct Entity
{
/// Stores an index to the first component contained in the entity.
int first_comp;
/// Stores an index to the first component's list.
unsigned short first_list;
};
struct Component
{
/// Stores an index to the entity which contains this component.
int entity;
/// Stores an index to the next component contained in the entity.
int next;
/// Stores an index to the component's list.
unsigned short list;
/// Stores an index to the next component's list.
unsigned short next_list;
/// Stores data for the component (variable-length struct).
char mem[1];
};
Then there's a big random-access sequence which is mostly contiguous (big blocks storing 64 elements each which get freed when a block becomes empty) storing all the components and entities above which are accessed by index. Accessing a component requires two indices: a 16-bit index to the component list (basically a component type index) and then a 32-bit index into that list. The components contained in an entity are stitched together through indices which basically form a singly-linked list (but without requiring any memory allocation for each individual list node since the list pointers are just indices into a giant contiguous structure).
I see no reason to use any other data structure or memory allocation pattern for the ECS. The memory overhead of it is already quite minimal at 8 bytes per entity and 16 bytes per component and the processing is already very cache-friendly and largely contiguous. Component and entity insertion and removal occurs in constant time with no room for improvements in terms of algorithmic complexity.
The system can fetch all the components of a particular type, like ParticleComponent, by just iterating through the list (mostly contiguous) of ParticleComponents. It's about as cheap as it conceptually gets with support for parallel processing like so:
// Invoke 'animate_particle' in parallel for up to 256 particles to process
// per thread.
ecs.pfor_each<ParticleComponent>(animate_particle, 256);
If we want to fetch all the entities that implement two or more components, like both ParticleComponent and MotionComponent, we simply iterate through the list of ParticleComponents and MotionComponents and gather up the entity indices associated with each. Then we sort the indices in parallel and linearly look for entity indices which occur in the two resulting lists. If we have:
{1,2,3,4,5,6} // entity indices gathered from list of `ParticleComponents`
{1,3,5,7,9} // entity indices gathered from list of `MotionComponents`
... then entity indices 1, 3, and 5 appear in both lists so that's the set intersection for entities which implement both ParticleComponent and MotionComponent. That's a fairly cheap query only requiring a linear traversal through two integer arrays, a couple of parallel sorts, and one more linear pass. The client can process the resulting entities like so:
// Do something to entities which contain both a motion and particle
// component in parallel, processing up to 256 entities at once per
// thread.
ecs.pfor_each<ParticleComponent, MotionComponent>(do_something, 256);
It's not something to do every single frame for millions of particles (though it's still reasonably fast in spite of doing this), but we can avoid that by simply allowing clients to memoize the entities that contain those two components and be notified when a ParticleComponent or MotionComponent has been removed from or added to the system, only updating the memoized entity list (a vector of ints, e.g.) then.
If you have a formal grouping concept for this, then the system can be responsible for memoizing the filtered list of entities that contain the group of components and only updating it as necessary. That doesn't require a more sophisticated data structure necessarily; a couple of linear passes and sorts (which can be done in linear time with, say, a radix sort because we're just sorting integers) should be good enough if you are only doing this in a lazy fashion when the client requests a list of entities that are filtered for a given component group and only when components matching the types in the group have been added or removed.
Even if you want something cheaper than a couple of linear passes and sorts of indices to fetch an updated list of entities which match the group filter, there should be a good enough data structure to fulfill the widest range of needs without the temptation to allow clients to specify what data structure to use for these purposes.
Policy-Based Design
With that aside, if you still feel like there's a strong compelling reason in your case to allow clients to specify data structures and allocators, then policy-based design might be the right fit for you. There you have classes which accept one or more template parameters indicating what policies to use (which could basically boil down to what data structures and allocators to use). Ex:
template <class SequencePolicy,
class AssociativePolicy,
class AllocationPolicy,
...>
class EntityManager
{
...
};
Modern C++ Design by Alexandrescu covers policy-based designs in detail.
However, I would move away from the standard library interfaces in that case because standard concepts like Sequence and Associative Container are likely too low-level for an ECS. I'd try to come up with the highest-level interface you can, especially for the data structures, that provide high-level methods suitable for an ECS system's needs. That could be considerably higher level than, say, push_back, insert, and erase and in a higher-level realm like query_components. Make it as high-level as you can, especially for non-sequence containers, to allow the maximum number of data structures to be used efficiently by the ECS.
Also unless you need to do dynamic allocations beyond these containers, I don't think you need to be able to specify allocators as policies to the ECS. Instead allocators can be policies for the data structure policies on how to allocate their data, and data structure policies are for the ECS.
There's also issues of how to reference a particular component or entity. That could vary based on the data structure. For example, I use 16-bit and 32-bit indices which is possible since I use random-access sequences to store component and entity data. However, I might have to use something different and more expensive like pointers if I used linked structures like a tree or a linked list where every node is allocated separately in ways that offer no guarantees about contiguity and don't provide random access. In that case, you might want Reference type(s) as template parameters which indicates what data type(s) you use to refer to specific entities or components in the system or something of this sort (perhaps this is a typedef the data structure policies specify). My brain hurts a bit trying to think of all the possibilities, but policy-based design tends to be the most flexible when you want to explore endless behavioral combinations without runtime abstraction costs.
That said, policy-based designs often fail to amass appeal for similar reasons I mentioned above. People have tried to come up with policy-based designs to allow you to customize a smart pointer's behavior to your heart's content only for people to just settle on unique_ptr and shared_ptr with their hard-coded behaviors. The idea of being able to explore endless combos of policies is generally more exciting conceptually than it is in practice. In practice, such flexibility tends to lead to a cumbersome solution which tends to get abandoned in favor of something with hard-coded behaviors but ones which are generally applicable enough and efficient enough for the widest range of people. Cumbersome solutions which allow exploring infinite possibilities will often be set aside from simple, featherweight solutions that only allow one very good and useful possibility. Hard-coding policies also carries the bonus that optimizations can be applied centrally in ways that can benefit everyone using the library without changing their own code.
