Some confusing about Sparse Set

[ysysimon]

I recently discovered this library and read a series of blogs by the author, I learn a lot from it, This is invaluable to a programmer.

But I also had some confusing about Sparse Set.

As far as I understand, sparse set is used in entt by:

• Store registered entities in the registry, But this seems odd since this would seem to only be sufficient for sparse arrays? Is entt::storage<void> used in the registry to store entities?
• Storing components in a component pool, Are components stored directly in the dense array of the sparse set?

I also read that an entt::null entity is an entity whose identifier part is invalid, This is used in a sparse array of a component pool's sparse set to indicate that this entity does not have this component (avoid to test dense array ), But if the identifier part is occupied by entt::null, how to implement the implicit linked list for identifier recycling?

And entt::tombstone is a version part invalid that is used to ensure pointer stability in dense arrays of sparse sets of component pools, But if it is stored in the dense array, where are the components stored? If entt::tombstone is not stored in a dense array, but in a sparse array, then its identifier part originally indicates which entity is the tombstone, and now the position in the sparse array has already indicated this? And there is still no place left for the implicit linked list (the identifier part should store entt::null)? However, if stored in a sparse array, iterating over a dense array will not be able to distinguish and skip invalid tombstone components?

[skypjack]

I think this is better suited for a discussion. Converting it.

[ysysimon]

I just noticed that github has a feature called discussion... 🤣

[skypjack]

Is entt::storage used in the registry to store entities?

No, EnTT uses a specialization of the storage class for the entities. That is, when the entity type and the component type are the same. See here for further details.

Are components stored directly in the dense array of the sparse set?

Uhm 🤔 it depends of what you mean. The library derives from the plain sparse set and adds yet another packed array on top of it. See here and the storage.hpp file in general for all implementation details.

This is used in a sparse array of a component pool's sparse set to indicate that this entity does not have this component [...] But if the identifier part is occupied by entt::null, how to implement the implicit linked list for identifier recycling?

You're mixing apples and pears. Recycling an identifier is something that entity storage does. Component storage types aren't interested in recycling any identifiers. So, yeah, null is used to speed up component checks. As for entities, I recommend studying the above storage specialization instead. Identifiers are never deleted. Their list is partitioned instead.

And entt::tombstone is a version part invalid that is used to ensure pointer stability in dense arrays of sparse sets of component pools, But if it is stored in the dense array, where are the components stored?

Components: nowhere. If the i-th position contains a tombstone in the sparse set, then the memory chunk to store the component is empty in the storage class. Uninitialized memory, available for next reuse.
See here for example. We swap-and-pop by default. However, we just invoke destroy the object when pointer stability is enabled. Memory is retained and managed accordingly.

If entt::tombstone is not stored in a dense array, but in a sparse array [...] And there is still no place left for the implicit linked list (the identifier part should store entt::null)?

The tombstone is in the packed array. Again, you're confusing the entity storage with the component one.

[ysysimon]

That is to say, entt::null and entt::tombstone are only in the component storage because they are used to speed up the verification of whether an entity has a component and maintain pointer stability.
While entity storage does not have them. Instead, they are replaced by an implicit linked list in the sparse array to speed up identifier recycling.