Что делает unorder_map и unorder_set быстрее, чем map и set?

Question

Итак, вчера у меня была лекция об ассоциативных контейнерах STL (unordered_map, unordered_set, map и set). Лектор сказал нам, что обычно unordered_map и unordered_set равны 0 (1), а map и set равны 0 (log (N)). У меня вопрос, что делает их быстрее? Они не отсортированы в конце концов.

Answer 1

Базовая структура данных, используемая для представления этих контейнеров, - это то, что делает один эффективнее другого.

• unordered_map и неупорядоченный набор используют карту ha sh table
• и набор используют самобалансирующееся BST (дерево двоичного поиска)

Ha sh таблицы обычно имеют O (1) вставку, время поиска. Ха sh таблицы достигают этого, потому что они используют индексированный подход для доступа и хранения данных.

Где в качестве BST используются O (log (n)) в основном из-за обхода, связанного с поиском или вставкой в ​​дерево , Они не используют индексированный подход. Для любой операции вы начинаете с узла root и затем перемещаетесь.