Какова сложность поиска элементов в структурах данных set и unordered_set?

В std::set сложность поиска в среднем $O(\log n)$, так как он основан на сбалансированных двоичных деревьях поиска (обычно красно-черных деревьях).

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