Разреженное множество (sparse set)
Структура данных из плотного массива значений и разреженного массива индексов: вставка, удаление и проверка принадлежности за O(1) и кэш-дружелюбный обход.
Её держат два массива: плотный (упакованный), где элементы лежат подряд, и большой разреженный, индексируемый ключом и хранящий позицию элемента в плотном. Проверка принадлежности — одно косвенное обращение; при удалении последний элемент плотного массива переставляется на место дыры и правятся два индекса, ничего не сдвигается. Обход плотного массива затрагивает только живые элементы, по порядку.
Поэтому ECS-библиотеки хранят каждый тип компонента как разреженное множество с ключом по id сущности: обход линейный и кэш-дружелюбный, в духе data-oriented-подхода. Расплата — память: разреженный массив рассчитан на диапазон ключей, а не на число элементов. Технику описали Бриггс и Торчон в 1993 году.