kray_zemli (kray_zemli) wrote,
kray_zemli
kray_zemli

ENTITY_LIST

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

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

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

Недостатки:

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

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

  • Либеральная партия

    Конечно, либералы победят. Их победа давно запланирована, они ждут своего часа и лишь притворяются оппозицией, поскольку они — дети и…

  • Кто в молодости... нет сердца, кто в зрелости... нет мозгов.

    Написал в КПРФ и СР о своём желании быть выдвинутым в депутаты ГД (а почему бы и нет?). Пока что как-то непонятно всё. А тут ЕР продлила своё…

  • Две страны, одна система

    Перестройка и реформы 90-х — неудачная попытка повторить китайский путь. В Китае делали примерно всё то же самое. Одна страна — две системы:…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments