Как работает метод find() у контейнера set в C++?
В set элементы по стандарту становятся в порядке возрастания и при этом удаляются дубликаты.
Как именно find() ищет в set нужный нам элемент? Он проходится по порядку начиная с первого элемента и сопоставляет значения? Или же использует алгоритм бинарного поиска, так как элементы отсортированы и это становится возможным?
Просто алгоритм бинарного поиска работает гораздо быстрее и в данном конкретном случае кажется более логичным.
Мне интересно, продумали ли разработчики C++ всё настолько серьезно или в этом нет абсолютно никакого смысла и за бинарный поиск в set отвечает какой-то другой метод или функция?
Ответы (1 шт):
По стандарту set является ассоциативным контейнером, как map, только без значений, только ключи.
Стандарт не требует линейного расположения элементов.
Стандарт требует логарифмической сложности для алгоритма поиска.
Например в GCC (GNU Compiler Collection) set реализован на основе красно-черного дерева. У него точно сложность поиска логарифмическая.
Если интересно, то вот ссылка на стандарт 2020 года.