Почему unordered_multiset плохо работает для многих равных ключей
У меня есть этот кусок кода:
unordered_multiset<int> t;
for (int i = 0; i < 1000000; i++) {
if (i % 10000 == 0)
cout << i << endl;
t.insert(10);
}
Так что это просто помещает много равных элементов в unordered_multiset, Но я узнал, что чем больше элементов в хэше, тем медленнее это работает? И я не могу понять причину. По моему мнению, после применения хеш-функции и нахождения сегмента равных элементов (поскольку все равные элементы сгруппированы вместе), stl просто помещает их в конец сегмента.
Так что здесь не так?
Udp:
Я нашел описание функции unordered_multiset :: insert
Вставки отдельных элементов:
Средний случай: постоянный.
В худшем случае: линейный по размеру контейнера.
Таким образом, вопрос теперь можно перефразировать так: «Почему наихудший случай является линейным»
Решение
Все идет в одном ведре. Чтобы положить что-то в конец ведра, вы должны найти конец ведра, и чем больше вещей в ведре, тем дольше это занимает.
Другие решения
Контейнер пытается сбалансировать себя путем реорганизации хранилища таким образом, чтобы средний размер корзины был ниже коэффициент нагрузки. Это достигается путем добавления большего количества сегментов в надежде, что данные будут распределены более равномерно.
Когда вы сохраняете одинаковое значение во всех элементах, они все равно окажутся в одном и том же сегменте. Наихудшее условие для хеш-таблицы!