9 ms·
Sparse sets. They're often used in Entity Component System architectures since you have O(1) add/remove/find, & O(n) iteration. Iterations are also packed, whi
by kaylynb 4y ago
Sparse sets.
They're often used in Entity Component System architectures since you have O(1) add/remove/find, & O(n) iteration. Iterations are also packed, which is a bonus for cache efficiency.
Can be difficult to implement well, but the concept is simple and a neat example of a useful specialty data structure. Take a look at https://github.com/skypjack/entt https://github.com/skypjack/entt
- hgs3 4y agoYou can apply the same idea to hash tables: Store hashes and dense-array indices in your sparse array, during lookup use robin hood hashing to cache efficiently probe the sparse array for a matching hash value, and if a match is found use the dense-array indice to lookup the data in the packed/dense array. This approach is both cache efficient and space efficient as the dense array can grow independently of the sparse array.