Sparse Set

A sparse set can be thought of as a "weird stack". It's made of two components: a mapping between IDs and indices, and a contigous array of memory.

This seperation allows for fast retrieve of members in the set as well as fast iteration of the set. Adding and removing values from the set behaves like a "weird stack".

To add to the set, you push a new value to the end of the contigous array.

table.insert(set.items, thing)
set.indices[thing.id] = #self.items

To remove from the set, you swap-pop the item out of it.

set.indices[thing.id] = nil -- free the id
set.items[index] = set.items[#self.items] -- the swap
table.remove(self.items) -- the pop

These two operations can form the basis of a sparse set. Sparse sets make no garentee of order.

This data structure is the basis on which ECSes are built.

A Quick Lua Implementation

The below is a quick lua implementation of a sparse set. The sparse array simply uses a table. The set implement ID recyclying.