Мне нужна структура данных похожая на Set. Она должна обладать следующими свойствами:
- В ней хранятся числа от 0 до 4095.
- В неё можно добавлять числа, при этом повторное добавление того же самого числа должно игнорироваться (то есть поддерживаться уникальность элементов). Удаление одиночных элементов не обязательно, нужна только операция полной очистки.
- После того как мы надобавляли туда числа, по этой структуре должна быть возможность быстро проитерироваться, чтобы посмотреть, что же мы туда добавили.
Эта структура должна работать быстро, потому что будет много-много раз в секунду цикл заполнение-итерирование-очистка, то есть вставка за O(1), итерирование по всем элементам за O(N), очистка желательно за O(1).
На первый взгляд приходят в голову битовые карты (ведь множество значений элементов небольшое), однако они, как мне кажется, не проходят по условию «быстрое итерирование и очистка». Есть ли какие-то ещё варианты? Подойдёт как алгоритм, так и готовая plain C библиотека. Или на таком количестве элементов все альтернативы будут иметь такую же производительность?
