Насколько эффективна функция find() в классе std:: map? Проводит ли он все элементы, которые ищут ключ, такой, что он O (n), или он находится в сбалансированном дереве, или использует хэш-функцию или что?
Сложность времени find() в std:: map?
Ответ 1
Журнал (n) Он основан на красном черном дереве.
Изменить: n - это, конечно, количество членов на карте.
Ответ 2
std::map и std::set реализуются поставщиками компиляторов с использованием высоко сбалансированных двоичных деревьев поиска (например, красно-черного дерева, дерева AVL).
Как правильно указал Дэвид, find будет принимать время O (log n), где n - количество элементов в контейнере.
Но с примитивными типами данных, такими как int, long, char, double и т.д., а не с строками.
Если std:string, скажем, размер 'm', используется как ключ, для перемещения по высоте сбалансированного дерева двоичного поиска потребуется log n сравнения данного ключа с записью дерева.
Когда std::string является ключом операций std::map или std::set, find и insert будет стоить O (m log n), где m - длина заданной строки, которая должна быть найдена.
Ответ 3
Он не выполняет итерацию всех элементов, он выполняет двоичный поиск (это O (log (n))). Он использует оператор < или компаратор для выполнения поиска.
Если вы хотите создать хэш-карту, вы можете использовать std:: unordered_map (добавленный на С++ - 0x), который использует хеш-функцию и в среднем (в зависимости от хэш-функции и данных, которые вы предоставляете) find() будет O (1).