В std::set сложность поиска в среднем O(\log n), так как он основан на сбалансированных двоичных деревьях поиска (обычно красно-черных деревьях).
В std::unordered_set сложность поиска в среднем O(1). Однако, в худшем случае, из-за коллизий хешей, она может достигать O(n).