Sparse set
Una struttura dati che abbina un array denso di valori a un array sparso di indici, con inserimento, rimozione e test di appartenenza in O(1) e iterazione favorevole alla cache.
Si regge su due array: uno denso (compatto) che contiene gli elementi in modo contiguo, e uno sparso, molto più grande, indicizzato dalla chiave, che memorizza dove si trova ciascun elemento in quello denso. L'appartenenza richiede una sola indirezione; la rimozione sposta l'ultimo elemento denso nel vuoto e corregge due indici, senza far scorrere nulla. Iterando l'array denso si toccano solo gli elementi vivi, in sequenza.
Per questo le librerie ECS archiviano ogni tipo di componente come sparse set indicizzato dall'ID dell'entità: l'iterazione è lineare e favorevole alla cache, nello stile del data-oriented design. Il prezzo è la memoria: l'array sparso è dimensionato sull'intervallo delle chiavi, non sul numero degli elementi. La tecnica fu descritta da Briggs e Torczon nel 1993.