Я не уверен, что понимаю «много вставок, которые попадают в одни и те же записи». Вы имеете в виду, что есть только 100 значений, которые когда-либо были членами, но 500k в основном дублирующих операций, которые вставляют одно из этих 100 значений?
Если это так, то я бы предположил, что самым быстрым контейнером будет генерировать хеш без коллизий для этих 100 значений, а затем поддерживать массив (или вектор) флагов (целых или битовых) в зависимости от того, что работает быстрее всего. по вашей архитектуре).
Я оставляю создание хэша в качестве упражнения для читателя, поскольку, как я знаю, оно существует как техника, но я никогда сам не изучал ее. Суть в том, чтобы получить быстрый хеш в максимально возможном диапазоне, чтобы для каждого n, m в ваших 100 значениях хэш (n)! = Хэш (m).
Таким образом, вставка выглядит как array[hash(value)] = 1;, удаление выглядит как array[hash(value)] = 0; (хотя вам это не нужно), и для перечисления вы запускаете массив, и для каждого установленного значения в индексе n, inverse_hash (n) равен в вашей коллекции. Для небольшого диапазона вы можете легко поддерживать справочную таблицу для выполнения обратного хэша или вместо сканирования всего массива в поисках установленных флагов, вы можете запустить 100 возможных значений, проверяя каждое по очереди.
Извините, если я неправильно понял ситуацию, и это бесполезно для вас. И, честно говоря, это не намного быстрее, чем обычная хеш-таблица, поскольку реально для 100 значений вы можете легко измерить таблицу так, чтобы было мало или вообще не возникало коллизий, без использования такого большого количества памяти, чтобы уничтожить ваши кеши.