January 10th, 2018

rune

ENTITY_LIST

Есть в ACIS такой контейнер, которого очень не хватает в STL. Это массив указателей с хэш-поиском. Можно представить его как гибрид std::vector и std::unordered_set. Внутри он представляет собой фактически "академическую" реализацию хэш-таблицы: первая часть массива хранит массив указателей, вторая часть массива хранит хэш-таблицу value -> index, с линейным пробированием и 20% запасом.

Преимущества:

-- Небольшой overhead по размеру памяти и количеству операций выделения-освобождения
-- Добавление (с проверкой на уникальность или без), удаление, поиск по значению -- за константное время
-- Итератор, фактически, представляет собой индекс, поэтому сохраняет валидность при любых операциях.
-- По значению двух элементов легко выяснить их взаимный порядок, найдя за константное время индексы и сравнив.
-- Предсказуемый порядок итерации -- всегда в порядке добавления элементов. Кроме прямой выгоды, это упрощает тестирование.
-- Можно одновременно итерироваться и добавлять/удалять элементы. Как следствие, удобная реализация хвостовой рекурсии, обход графа в ширину одним циклом.

Недостатки:

-- Удаление элементов оставляет "дырку" (значение ENTITY_LIST_DELETED = (ENTITY*)-1, хотя это мог бы быть и нулевой указатель). Частое удаление, чередуемое с добавлением новых элементов, портит эффективность по памяти. Итерация по сильно "дырявому" контейнеру портит производительность, так как нужно пропускать "дырки".
-- Портится асимптотика при наличии дубликатов. Впрочем, обычно контейнер используется именно для уникальных элементов.

Банальный обход графа средствами STL требует десяток строк, в то время как ENTITY_LIST позволяет во многих случаях уложиться в две.