set 과 unordered_set

set 과 unordered_set

 

set과  unordered_set은 C++ 표준 라이브러리의 컨테이너이다.

둘 다 중복되지 않는 고유의 값을 저장하는데 사용되지만 내부 동작 방식에 차이가 있다.

 

set은 Red-Black Tree / 이진 검색 트리 구조를 가지고 있어,데이터를 항상 정렬된 상태로 유지해 정렬된 데이터에 대한 검색이나 순차적인 접근이 필요할 때 적합하다.

따라서 데이터 삽입 시 자동으로 정렬되어 별도의 정렬 작업이 필요 없는 것이 장점이다.

그리고 메모리 사용량이 비교적으로 적다.

하지만 삽입/삭제 연산이 느린 단점을 가지고 있다. / O(log n)

 

unordered_set은 삽입, 삭제, 탐색의 시간 복잡도가 평균적으로 O(1)로 매우 빠른 대신 데이터가 정렬되지 않는다.

그리고 데이터가 해시 테이블에 저장되어서 오버헤드 발생시에 O(n) 으로 느려질 수 있다.

 

정리하자면 순차적으로 데이터를 순회하거나, 가장 큰 값 혹은 작은 값을 빠르게 찾아야하는 경우 그리고 메모리 사용을 최소화해야 하는 경우엔 set을 사용하는게 좋을 것이고,

데이터 정렬이 중요하지 않고, 삽입 및 검색 속도가 중요한 경우엔 unodered_set을 사용하는 것이 더 효율적이다.