мультимножество, сложность карты и хеш-карты

Question

Хотелось бы узнать сложность обозначений Big O для классов мультимножеств STL, map и hash map, когда:

• вставка записей
• доступ к записям
• получение записей
• сравнение записей

Answer 1

map, set, multimap и multiset

Они реализованы с использованием красно-черного дерева , типа сбалансированного двоичного дерева поиска . Они имеют следующие асимптотические времена выполнения:

Вставка: O (log n)
Поиск: O (log n)
Удаление: O (log n)

hash_map, hash_set, hash_multimap и hash_multiset

Они реализованы с использованием хеш-таблиц . Они имеют следующие среды выполнения:

Вставка: O (1) ожидаемый, O (n) худший случай
Поиск: O (1) ожидается, O (n) худший случай
Удаление: O (1) ожидаемый, O (n) худший случай

Если вы используете правильную хэш-функцию, вы почти никогда не увидите наихудшего поведения, но об этом следует помнить - см. Отказ в обслуживании посредством атак алгоритмической сложности Кросби и Уоллака для пример тому.

Answer 2

Вы можете найти эту информацию в документации SGI STL: http://www.sgi.com/tech/stl/

По сути, и мультимножество, и карты являются отсортированными двоичными деревьями, поэтому вставка / поиск 1 из N записей занимает O (log N). Смотрите отсортированный доц. Контейнеры в документации.

Очевидно, что большим преимуществом Hashmap является O (1) для вставки и поиска записей.

Доступ к нему после найденного O (1) для всех структур. Сравнение, что вы подразумеваете под этим? Звучит как O (1) для меня, после того, как все были найдены.