unordered_map: какой из них быстрее find() или count()?

Question

Какой самый быстрый способ выяснить, если unordered_map В контейнере есть элемент с указанным ключом?

Answer 1

У них будет примерно одинаковая производительность. Вы должны использовать алгоритм, который наилучшим образом выражает то, что вы пытаетесь сделать.

Чтобы уточнить это, как правило, count() будет реализовано с использованием find(), Например, в libcxx, count() реализуется как return (find(__k) != end());

Answer 2

C++20 разрешил дилемму, предоставив метод, который по-прежнему имеет ту же производительность, но прямо говорит о том, что вы имеете в виду.

Answer 3

find() а также count() применимы ко многим контейнерам в C++.

Для карт, наборов и т. Д. Find всегда будет иметь постоянное время выполнения, поскольку он просто вычисляет хеш и возвращает итератор для первого найденного элемента (end() если не найден).

count() с другой стороны, имеет постоянное время выполнения O(e), где e - количество раз, когда был найден предоставленный ключ. В худшем случае это коллекция, в которой все члены одинаковы, поэтому count может иметь сложность O(n)

map или же unordered_map не допускайте дубликатов, поэтому их асимптотическое время выполнения будет таким же.

Выбор зависит от семантики в вашем коде. Если вы хотите просто проверить, существует ли ключ, вы можете просто использовать count, Если вы хотите проверить, существует ли ключ, и использовать его значение, перейдите к find поскольку у вас уже будет итератор, указывающий на этот элемент.

Answer 4

Я думаю, что Find - лучший вариант здесь, нет необходимости идти дальше.

http://www.cplusplus.com/reference/unordered_map/unordered_map/find/