Sparse set
A data structure pairing a dense value array with a sparse index array, giving O(1) insert, remove and membership test plus cache-friendly iteration.
Two arrays back it: a dense (packed) array holding the elements contiguously, and a large sparse array indexed by the key that stores where each element lives in the dense one. Membership is a single indirection; removal swaps the last dense element into the hole and patches two indices — nothing shifts. Iterating the dense array touches only live elements, in order.
That is why ECS libraries store each component type as a sparse set keyed on entity id: the iteration is linear and cache-friendly in the data-oriented style. The cost is memory — the sparse array is sized to the key range, not the element count. Briggs and Torczon described the technique in 1993.