[C++][STL] set과 unordered_set의 차이

set

키들을 이진 탐색 트리를 기반으로 저장한다. 따라서 자동 정렬되는 컨테이너이고 탐색 시간은 O( log n ) 입니다. 삽입과 제거가 빈번해지면 느리다.

 

undorderd_set

해쉬 테이블 기반으로 저장한다. 어떤 해쉬를 쓰느냐에 따라 다르겠지만, 같은 해쉬값을 중복적으로 저장한다면 최대 O(n)의 시간복잡도를 갖는다. 따라서 탐색시간이 기본적으론 O(1) 이지만 최악의 경우 O(n) 입니다. 자동 정렬되지 않는 set이다.  버킷 때문에 메모리 사용량이 증가할 수 있다.

 

결론 : 알고리즘 문제의 경우 최악의 복잡도가 중요하므로 기본 set을 이용하여 풀자. (이진탐색의 경우 set을 쓰면 좋다.)