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

Почему сложность наихудшего случая std::unordered_multiset вставка линейная? Я понимаю, почему это так для std::unordered_set (Вы должны проверить, что вставленного значения нет в наборе), но для мультимножества я не получаю его. Я что-то упускаю из виду?

4

Решение

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

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]