Ответ 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) наихудший случай

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

Ответ 2

cppreference.com - это то, куда я обращаюсь к своим справочным вопросам на С++. Они очень хорошо описывают нотацию Big O для большинства функций, о которых вы просили выше.

Ответ 3

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

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

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

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