карта, набор, мультикарта и мультимножество

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

Вставка: O (регистрируют n)
Поиск: O (регистрируют n)
Удаление: O (регистрируют n)

hash_map, hash_set, hash_multimap, и hash_multiset

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

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

при использовании надлежащей хеш-функции Вы никогда не будете почти видеть худшего поведения случая, но это - что-то, чтобы иметь в виду, что — видят Отказ в обслуживании через Алгоритмические Нападения Сложности Crosby и Wallach для примера этого.

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

В основном, и мультимножество и карты является отсортированными двоичными деревьями, так вставка/открытие 1 из записей N берет O (зарегистрируйте N). Посмотрите Отсортированные контейнеры Помощника в документации.

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

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