C++에서 set과 unordered_set은 모두 데이터를 효율적으로 저장하고 빠르게 접근·삽입할 수 있도록 설계된 연관 컨테이너(associative container)입니다. 두 컨테이너는 이름이 비슷해 같은 기능을 하는 것처럼 보이지만, 내부 구현 방식과 데이터 저장 순서, 성능 특성에서 중요한 차이가 있습니다.
아래 표에서 set과 unordered_set의 핵심적인 차이점을 확인해 보세요.
set과 unordered_set의 주요 차이점
| 번호 | 구분 | set | unordered_set |
|---|---|---|---|
| 1 | 정의 | C++ STL(표준 템플릿 라이브러리)에서 제공하는 연관 컨테이너로, 고유한(key-value) 요소를 정렬된 상태로 저장합니다. 각 요소는 그 값 자체가 식별자 역할을 하므로 반드시 유일해야 합니다. | 역시 STL의 연관 컨테이너로 고유한 요소만 저장한다는 점은 set과 같지만, 해시 함수를 기반으로 동작하므로 정렬 순서를 보장하지 않습니다. |
| 2 | 정렬 여부 | 데이터가 항상 오름차순으로 자동 정렬되어 저장됩니다. | 데이터가 정렬되지 않은 채 해시 버킷에 저장되며, 출력 순서는 구현 환경에 따라 달라질 수 있습니다. |
| 3 | 중복 값 처리 | 중복된 값의 저장이 허용되지 않으며, 이미 존재하는 값을 insert하면 무시됩니다. | 마찬가지로 중복된 값은 저장되지 않고 폐기(discard)됩니다. |
| 4 | 내부 구현 | 레드-블랙 트리(Red-Black Tree)와 같은 균형 이진 탐색 트리(Binary Search Tree)로 구현됩니다. | 해시 테이블(Hash Table)을 기반으로 구현됩니다. |
| 5 | 시간 복잡도 | 탐색·삽입·삭제 모두 O(log n)의 시간 복잡도를 가집니다. | 평균적으로 O(1)의 매우 빠른 속도를 보이지만, 최악의 경우(해시 충돌) O(n)까지 느려질 수 있습니다. |
예제 1 — set 사용하기
다음 예제는 15개의 정수 배열을 set에 삽입한 후 순회하며 출력합니다. 중복된 값(11, 22, 66 등)은 한 번만 저장되고, 결과는 항상 오름차순으로 정렬됩니다.
#include <iostream>
#include <set>
using namespace std;
int main() {
int data[15] = {11, 55, 22, 66, 33, 22, 11, 44, 77, 88, 66, 99, 66, 23, 41};
set<int> my_set;
for (int i = 0; i < 15; i++) {
my_set.insert(data[i]);
}
set<int>::iterator it;
for (it = my_set.begin(); it != my_set.end(); it++) {
cout << "Item: " << *it << endl;
}
return 0;
}
실행 결과
Item: 11
Item: 22
Item: 23
Item: 33
Item: 41
Item: 44
Item: 55
Item: 66
Item: 77
Item: 88
Item: 99
입력 순서와 무관하게 값이 정렬된 순서로 출력되는 것을 확인할 수 있습니다.
예제 2 — unordered_set 사용하기
동일한 데이터를 unordered_set에 삽입하면 어떻게 될까요? 중복 제거는 동일하게 이루어지지만, 출력 순서는 정렬되지 않습니다.
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
int data[15] = {11, 55, 22, 66, 33, 22, 11, 44, 77, 88, 66, 99, 66, 23, 41};
unordered_set<int> my_set;
for (int i = 0; i < 15; i++) {
my_set.insert(data[i]);
}
unordered_set<int>::iterator it;
for (it = my_set.begin(); it != my_set.end(); it++) {
cout << "Item: " << *it << endl;
}
return 0;
}
실행 결과
Item: 11
Item: 55
Item: 22
Item: 66
Item: 33
Item: 44
Item: 77
Item: 88
Item: 99
Item: 23
Item: 41
값들이 입력 순서나 크기 순서와 상관없이 해시 함수가 결정하는 임의의 순서로 출력됩니다. 참고로 이 순서는 컴파일러나 라이브러리 버전에 따라 달라질 수 있습니다.
정리: 어떤 것을 선택해야 할까?
- set — 정렬된 순서로 데이터를 순회해야 하거나, 범위 기반 조회(range query), 최솟값·최댓값 접근이 필요한 경우에 적합합니다.
- unordered_set — 순서가 중요하지 않고, 단순히 존재 여부 확인이나 빠른 삽입·삭제가 필요한 경우 평균 O(1)의 성능으로 더 유리합니다.
두 컨테이너 모두 중복을 허용하지 않는다는 공통점이 있으므로, 정렬이 필요한지 여부와 성능 요구사항을 기준으로 선택하면 됩니다.