Для контейнеров STL С++, таких как vector и list, сложность поиска элементов и их вставки или удаления не требует пояснений. Однако для контейнера map, хотя из моего чтения я знаю, что сложность/производительность доступа и вставки - O (log (n)), я не могу понять, почему. Я явно не понимаю карты столько, сколько мне нужно, поэтому некоторое просвещение по этой теме было бы очень оценено.
Почему сложность контейнера карты С++ STL O (log (n))?
Ответ 1
Элементы карты или множества содержатся в древовидной структуре; каждый раз, когда вы просматриваете node дерева, вы определяете, находится ли элемент, который вы пытаетесь найти/вставить, меньше или больше, чем node. Количество раз, когда вам нужно это сделать (для правильно сбалансированного дерева), является log2 (N), потому что каждое сравнение выбрасывает половину возможностей.
Ответ 2
Как slavik262 точки, карты обычно реализуются с красно-черными деревьями, которые являются самобалансированными. Проверьте сложность красно-черного дерева, например, в wikipedia Я не знаю никакой реализации карты с бинарным деревом; если Марк Рэнсом знает один, я был бы рад узнать, какой из них.