Сложность вставки std :: unordered_multiset

Наихудший вариант сложности для 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()),