A Sparse Set is a specialized data structure for storing elements from a large amount of possible values (e.g. natural numbers) that are used very sparingly, optimized for iteration, addition and removal to the set.

Use cases are for example are components attached to an entity in an Entity-Component System (ECS), if you are dealing with arrays of indices, but it can also be used comparably to a binary search tree or hash map, ideally outperforming both of them.

The main advantages of a Sparse Set are its performance which can be
O(1) for it's primary actions (source spareset/lib.rs) and its low memory footprint.

Example Implementations:

• Swift - Fireblade ECS
• Swift - SwiftECS
• Rust - sparseset
• Go - sparse

Further Reading:

• https://www.codeproject.com/Articles/859324/Fast-Implementations-of-Sparse-Sets-in-Cplusplus
• https://www.geeksforgeeks.org/sparse-set/
• https://www.bartwolff.com/Blog/2012/03/14/a-simple-sparse-set-implementation-in-c
• http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html