Почему сложность наихудшего случая std::unordered_multiset
вставка линейная? Я понимаю, почему это так для std::unordered_set
(Вы должны проверить, что вставленного значения нет в наборе), но для мультимножества я не получаю его. Я что-то упускаю из виду?
Наихудший вариант сложности для std::unordered_multiset::insert()
является линейным, потому что:
Например, рассмотрим случай, когда 5
, 13
, а также 13
вставляются в unordered_multiset
который имеет 4
ведра и unordered_multiset::key_eq(5, 13)
возвращается false
, В этом случае, unordered_multiset::hash_function(5)
возвращает разные хэш-коды для обоих 5
а также 13
, Несмотря на наличие разных хеш-кодов, эти элементы могут быть вставлены в одно и то же ведро. Если хеш-функция для целого числа возвращает само целое число, а индекс сегмента является результатом модуля хеш-кода количества сегментов, то:
5
хешируется в 5
, и с 4
ведра, он помещается в ведро 1
,13
хешируется в 13
, и с 4
ведра, он помещается в ведро 1
также.В то время как unordered_set::insert()
проверяет, чтобы избежать дубликатов во время вставки, unordered_multiset::insert()
определяет, куда вставить элемент для группировки по эквивалентному ключу. В худшем случае ведро содержит [5, 13]
при вставке финала 13
и после перебора всех элементов, корзина содержит [5, 13, 13]
, Поскольку итерация по всем элементам происходит, сложность линейна в size()
,
Стоит отметить, что перефразировка может происходить во время unordered_multiset::insert()
, а также unordered_multiset::rehash()
указан как имеющий сложность со средним случаем, линейным в size()
и худший случай является квадратичным. Во время перефразирования все элементы в исходной хеш-таблице перебираются и вставляются в новую хеш-таблицу. Поскольку итерация имеет линейную сложность size()
и, как указано выше, каждая вставка имеет худший случай, линейный по size()
в результате наихудший случай O(size()*size())
,
Других решений пока нет …