<unordered_set>

unordered_set

C++ Standard Library의 컨테이너로, 고유한 값을 저장하는데 사용됩니다. 이름에서 알 수 있듯이, 이 컨테이너는 순서에 상관없이 데이터를 저장합니다. 내부적으로 해시 테이블을 사용하여 데이터를 저장하고 검색하기 때문에, 순서가 중요한 경우에는 적합하지 않습니다.

주요 특징

• 해시 테이블(hash table)을 기반으로 합니다.
• 정렬되지 않습니다.
• 평균적으로 O(1)의 시간 복잡도로 검색, 삽입, 삭제가 가능합니다. 하지만 문제가 발생하면 최악의 경우 O(n)의 시간 복잡도를 가질 수 있습니다.
• std::hash가 제공하는 해시 함수를 사용합니다.
• 해시 테이블을 사용하기 때문에 메모리 사용량이 큽니다.

set VS unordered_set

1. 구조

• set : 내부적으로 Red-Black Tree를 사용
• unordered_set : 내부적으로 Hash Table을 사용

2. 정렬

• set : 값을 오름차순으로 정렬
• unordered_set : 무작위

3. 시간 복잡도

• set : O(log n)
• unordered_set : 평균적으로 O(1) (최악의 경우 O(n))

4. 순회

• set : 정렬된 순서로 순회
• unordered_set : 순서 예측 불가능

5. 메모리 사용

• set : 상대적으로 적음
• unordered_set : 더 많을 수 있음

set과 unordered_set의 함수는 거의 동일하지만 set은 정렬과 관련된 함수를 가지고 있고 unordered_set은 해시/버킷 관련 함수를 가지고 있습니다.