Контейнер с O (1) вставкой (амортизируется) и O (n) итерацией

Question

Я ищу класс контейнера, подобный множеству, который имеет следующие основные свойства:

1. имеет амортизированное O (1) время вставки, дублирующие вставки игнорируются
2. имеет O(n) время итерации (в частности, O (емкость) недопустимо)
3. повторно использует память / выделяет только при превышении текущей емкости

Вариант использованияв том, что у меня есть большой контейнер объектов.Во время каждого цикла я добавляю подмножество этих объектов в этот новый контейнер.Это подмножество может содержать от 1-5 объектов или до 10% от всего набора.Затем я перебираю объекты в этом новом наборе.Каждый цикл объект будет очищен, и обработка будет начата снова.

Мой оригинальный подход использовал инвазивное логическое значение для объектов, указывающее, принадлежало ли оно этому новому набору.Таким образом, вставка была истинным постоянным временем, и она не использовала новую память.Однако итерация была неоптимальной.

Я попробовал boost::unordered_set и получил худшую производительность, чем мой первоначальный подход.Предположительно, поскольку, как хэш-карта, она не соответствует точке № 2.

Точка № 3 актуальна, поскольку я кодирую на уровне задержки, когда стоимость выделения памяти очень значительна.Таким образом, крайне маловероятно, что контейнер с непрерывным распределением будет работать хорошо.

Answer 1

Используйте ваш первый подход, чтобы определить, находится ли элемент уже в наборе (хэш-карта). И поместите его также в список для повторения ..

Answer 2

Вы можете использовать связанный хэш-набор. LinkedHashSet в Java. Я не знаю, существует ли библиотека в c ++, которая реализует ее, но идея проста: имейте хэш-набор записей, и пусть записи также образуют связанный список .

Итерация в связанном списке, а вставки сделаны из хеш-набора. Обратите внимание, что этот подход допускает вставки в список только с обратной стороны.

Answer 3

Попробуйте Эмде Боас дерево . Это может соответствовать вашим целям:

1. Вставка O (log (log (n))),
2. Итерация O (log (log (n))),
3. Память ... Ну, просто прочитайте предоставленную ссылку ...

Answer 4

Вы можете улучшить свой метод, добавив связанный список.

Там будет связанный список указателей (или любого другого подходящего идентификатора) для вставленных объектов.Кроме того, оставьте логическую переменную внутри каждого вашего объекта, чтобы узнать, вставлен ли он уже в список.