Comments 11
Спасибо за интересный материал! =)
Что-то Sparse Set память не сильно экономит.
Например, используя 10-ти битные числа, нужно положить значения 1,10,100,1000
В обычном векторе: 4 числа и 3 указателя.
sdt::bitset: 1024 бита. (32 числа)
Sparse Set: 2049 чисел.
Там вопрос не столько в экономии памяти, сколько в том, что ты операции быстрее. Просто другой подход.
Да, спарссет скорее отъедает память чем экономит. Его плюс в быстрой итерации (в вашем примере у битсета придется обходить все значения, а вектор не обеспечит быстрого поиска и удаления).
Ну и да, в entt к примеру используется модификация sparseset, чтобы не выделять кучу пустых элементов. Бьём массив sparse на блоки скажем по 128 элементов, аллоцируем только блоки в которых есть элементы.
Замечательно! Подписался на ваш канал !
Разряженный список немного напоминает skip list. Там тоже создаются разряженные ссылки через много элементов, но используются они для реализации поиска в остортированном списке за O(log n). Фактически, это альтернатива балансированному бинарному дереву.
Для значений, которые в нашем сете не находятся, мы проверим мусорные ячейки (если ранее там ничего не лежало) и вряд ли наше условие пройдёт (там всё-таки мусор).
Чтение неинициализированной переменной это ub. Компилятор рано или поздно заметит что Contains либо возвращает true либо триггерт ub и просто заменит ее тело на return true
Разреженные структуры данных