Временная сложность find () в std :: map?

Question

Насколько эффективна функция find () в классе std :: map? Проходит ли он все элементы, ища ключ, так что он равен O (n), или он находится в сбалансированном дереве, или он использует хеш-функцию или как?

Answer 1

Log (n) Он основан на красном черном дереве.

Редактировать: n - это, конечно, количество членов на карте.

Answer 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длина данной строки, которую нужно найти.

Answer 3

Он не повторяет все элементы, он выполняет бинарный поиск (который является O (log (n))).Для поиска используется оператор <или компаратор. </p>

Если вам нужна хеш-карта, вы можете использовать std :: unordered_map (добавлено на C ++ - 0x), который использует хеш-функцию и в среднем (в зависимости от хеш-функции и данных, которые вы предоставляете) find () будет O (1).