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

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

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

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

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

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

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