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