public sealed class SparseSet<T>A set of non-negative integer keys with a value attached to each: O(1) add, remove and lookup, and — the reason it exists — iteration over a dense, contiguous array of the values, in no particular order.
No guide page documents this yet — the page shows what the code says about itself.
Remarks
Two arrays do the work. A sparse array maps a key to its position in the dense array; the dense arrays hold the keys and values packed together. Removing swaps the last entry into the hole, so the dense side never has gaps and a query never touches a cache line it does not need.
The sparse array is indexed by key, so memory is proportional to the largest key ever added, not to the number of entries. That is the right trade for entity ids and component indices, which are dense and small by construction, and the wrong one for anything sparse and unbounded — use a dictionary there.
Removal reorders. Anything that depends on iteration order needs to sort, and anything holding a dense index across a removal is holding the wrong one.
Fields and properties (4)
public int CountHow many entries the set holds.
public int KeyCapacityThe largest key the sparse array currently has room for, plus one.
public ReadOnlySpan<int> KeysThe keys, densely packed, in the set's own order.
public Span<T> ValuesThe values, densely packed, in the same order as Keys. Writable so a system can sweep every component in one pass without going through the key lookup.
Methods (8)
public SparseSet(int keyCapacity = 64, int capacity = 16)Creates a set sized for a given key range and entry count.
public bool Contains(int key)Whether a key is in the set.
public void Set(int key, T value)Adds or replaces the value for a key.
public bool TryGetValue(int key, out T value)Looks up the value for a key.
public ref T GetReference(int key)A reference to the value for a key, for mutating a large struct in place.
public bool Remove(int key)Removes a key.
public void Clear()Empties the set, keeping the buffers.
public SparseSet<T>.Enumerator GetEnumerator()Enumerates the entries in dense order.
Used by (2)
- CollectionTestsVixen.Core.Collections.Tests
- EnumeratorVixen.Core.Collections