using find() на неупорядоченной карте <string, vector <string>> принимает то же время, что и упорядоченная карта в C++

Question

У меня есть неупорядоченная карта строки и вектора строк, то есть un_map<string,vector<string> >. При поиске конкретной строки с помощью функции поиска:

find((un_map[A].begin(),un_map[A].end(),field)==un_map[A].end()) 

времени выполнения функции находки для неупорядоченных карт и заказать карту приходит то же самое. Может ли кто-нибудь объяснить, почему так? Насколько я знаю, неупорядоченная карта должна быть намного быстрее, чем упорядоченная карта из-за хеширования. Я хочу оптимизировать функцию поиска. Пожалуйста, помогите

Answer 1

std::find выполняет поиск по стандартной итерации по всему контейнеру, используя только инкремент итераторов. Итак, сложность здесь O (n).

Для ускорения нахождения элемента на основе контейнера необходимо вызвать метод контейнера find.

std::unordered_map::find сложность поиска O (1), потому что, как вы указали, используется хеширование.

std::map::find сложность поиска - O (log (n)), поскольку он использует двоичный поиск.