Ещё с московских собеседований
Если ты такой умный, то почему не с физтеха? А, может, не такой уж и умный? Иначе как объяснить, что учился в каком-то Новосибирске?
January 10th, 2018
ENTITY_LIST
Есть в ACIS такой контейнер, которого очень не хватает в STL. Это массив указателей с хэш-поиском. Можно представить его как гибрид std::vector и std::unordered_set. Внутри он представляет собой фактически "академическую" реализацию хэш-таблицы: первая часть массива хранит массив указателей, вторая часть массива хранит хэш-таблицу value -> index, с линейным пробированием и 20% запасом.
Преимущества:
-- Небольшой overhead по размеру памяти и количеству операций выделения-освобождения
-- Добавление (с проверкой на уникальность или без), удаление, поиск по значению -- за константное время
-- Итератор, фактически, представляет собой индекс, поэтому сохраняет валидность при любых операциях.
-- По значению двух элементов легко выяснить их взаимный порядок, найдя за константное время индексы и сравнив.
-- Предсказуемый порядок итерации -- всегда в порядке добавления элементов. Кроме прямой выгоды, это упрощает тестирование.
-- Можно одновременно итерироваться и добавлять/удалять элементы. Как следствие, удобная реализация хвостовой рекурсии, обход графа в ширину одним циклом.
Недостатки:
-- Удаление элементов оставляет "дырку" (значение ENTITY_LIST_DELETED = (ENTITY*)-1, хотя это мог бы быть и нулевой указатель). Частое удаление, чередуемое с добавлением новых элементов, портит эффективность по памяти. Итерация по сильно "дырявому" контейнеру портит производительность, так как нужно пропускать "дырки".
-- Портится асимптотика при наличии дубликатов. Впрочем, обычно контейнер используется именно для уникальных элементов.
Банальный обход графа средствами STL требует десяток строк, в то время как ENTITY_LIST позволяет во многих случаях уложиться в две.
Преимущества:
-- Небольшой overhead по размеру памяти и количеству операций выделения-освобождения
-- Добавление (с проверкой на уникальность или без), удаление, поиск по значению -- за константное время
-- Итератор, фактически, представляет собой индекс, поэтому сохраняет валидность при любых операциях.
-- По значению двух элементов легко выяснить их взаимный порядок, найдя за константное время индексы и сравнив.
-- Предсказуемый порядок итерации -- всегда в порядке добавления элементов. Кроме прямой выгоды, это упрощает тестирование.
-- Можно одновременно итерироваться и добавлять/удалять элементы. Как следствие, удобная реализация хвостовой рекурсии, обход графа в ширину одним циклом.
Недостатки:
-- Удаление элементов оставляет "дырку" (значение ENTITY_LIST_DELETED = (ENTITY*)-1, хотя это мог бы быть и нулевой указатель). Частое удаление, чередуемое с добавлением новых элементов, портит эффективность по памяти. Итерация по сильно "дырявому" контейнеру портит производительность, так как нужно пропускать "дырки".
-- Портится асимптотика при наличии дубликатов. Впрочем, обычно контейнер используется именно для уникальных элементов.
Банальный обход графа средствами STL требует десяток строк, в то время как ENTITY_LIST позволяет во многих случаях уложиться в две.