std::unordered_set реализован в виде таблицы ha sh. Его find метод имеет среднюю сложность O(1) и наихудшую сложность O(set.size()) сравнений ключей, как указано [tab: container.ha sh .req] .
По умолчанию std::unordered_set<std::string> использует operator== для сравнения ключей, поэтому каждое сравнение ключей выполняется в O(str.size()), как указано в [string.view.ops] (operator==(const std::string&, const std::string&) определяется как эквивалентный std::string_view(str1) == std::string_view(str2), который определяется как эквивалентный std::string_view(str1).compare(std::string_view(str2) == 0).
Для std::unordered_set<std::string> контейнер должен вычислить га sh строки для поиска. По умолчанию для этого используется std::hash<std::string>. Стандарт не устанавливает никаких требований к сложности для std::hash<std::string>, но, скорее всего, O(str.size()).