C++ STL에는 네 가지 종류의 집합(set) 컨테이너가 존재합니다. 바로 set, multiset, unordered_set, unordered_multiset입니다. 이들은 정렬 여부와 중복 허용 여부에 따라 서로 다른 특성을 가지며, 상황에 맞는 컨테이너를 선택하는 것이 성능과 코드 품질에 큰 영향을 미칩니다.
이 글에서는 각 컨테이너의 핵심 속성을 살펴보고, 동일한 데이터를 삽입했을 때 어떤 차이가 발생하는지 예제와 함께 확인해 보겠습니다.
1. set — 정렬된 고유 값 저장
set은 가장 기본적인 연관 컨테이너로, 다음과 같은 특징을 가집니다.
- 데이터를 항상 정렬된 순서로 저장합니다.
- 중복 값을 허용하지 않으며 고유한 값만 저장됩니다.
- 요소의 삽입과 삭제는 가능하지만, 이미 저장된 값은 직접 수정할 수 없습니다.
- 시작 반복자(begin)와 끝 반복자(end)를 사용해 여러 요소를 한 번에 삭제할 수 있습니다.
- 반복자(iterator)를 이용해 순회할 수 있습니다.
- 내부적으로 이진 탐색 트리(Binary Search Tree)(일반적으로 레드-블랙 트리)로 구현되어 있습니다.
예제 코드
#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;
}
}실행 결과
Item: 11 Item: 22 Item: 23 Item: 33 Item: 41 Item: 44 Item: 55 Item: 66 Item: 77 Item: 88 Item: 99
입력 데이터에 중복값(11, 22, 66 등)이 있었지만, 출력 결과를 보면 각 값이 하나씩만 저장되고 오름차순으로 정렬되어 있는 것을 확인할 수 있습니다.
2. multiset — 중복을 허용하는 정렬 컨테이너
multiset은 set과 거의 같지만 중복 값을 허용한다는 점이 다릅니다.
- 데이터를 정렬된 순서로 저장합니다.
- 중복 데이터 저장을 허용합니다.
- 시작 반복자와 끝 반복자를 사용해 여러 요소를 한 번에 삭제할 수 있습니다.
예제 코드
#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};
multiset<int> my_set;
for(int i = 0; i < 15; i++) {
my_set.insert(data[i]);
}
multiset<int>::iterator it;
for(it = my_set.begin(); it != my_set.end(); it++) {
cout << "Item: " << *it << endl;
}
}실행 결과
Item: 11 Item: 11 Item: 22 Item: 22 Item: 23 Item: 33 Item: 41 Item: 44 Item: 55 Item: 66 Item: 66 Item: 66 Item: 77 Item: 88 Item: 99
출력 결과를 보면 11이 두 번, 22가 두 번, 66이 세 번 나타나는 것처럼 중복 값이 모두 유지되면서도 정렬은 유지됩니다.
3. unordered_set — 해시 기반의 비정렬 집합
unordered_set은 이름 그대로 정렬을 보장하지 않는 집합입니다.
- 데이터가 임의의 순서로 저장될 수 있습니다.
- 중복 데이터는 자동으로 버려집니다.
- 내부적으로 해시 테이블(Hash Table)로 구현되어 있습니다.
- 반복자가 가리키는 단일 요소만 삭제할 수 있습니다.
예제 코드
#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;
}
}실행 결과
Item: 11 Item: 55 Item: 22 Item: 66 Item: 33 Item: 44 Item: 77 Item: 88 Item: 99 Item: 23 Item: 41
중복값은 제거되지만, 정렬 없이 해시 함수에 따라 결정된 순서로 출력됩니다. 참고로 이 순서는 구현 환경에 따라 달라질 수 있으므로 실행할 때마다 또는 컴파일러마다 다르게 나타날 수 있습니다.
4. unordered_multiset — 중복 허용 + 해시 기반
unordered_multiset은 해시 테이블 기반이면서 중복을 허용하는 컨테이너입니다.
- 데이터가 임의의 순서로 저장됩니다.
- 중복 데이터가 허용됩니다.
- 내부적으로 해시 테이블로 구현되어 있습니다.
- 반복자가 가리키는 단일 요소만 삭제할 수 있습니다.
예제 코드
#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_multiset<int> my_set;
for(int i = 0; i < 15; i++) {
my_set.insert(data[i]);
}
unordered_multiset<int>::iterator it;
for(it = my_set.begin(); it != my_set.end(); it++) {
cout << "Item: " << *it << endl;
}
}실행 결과
Item: 11 Item: 55 Item: 22 Item: 66 Item: 33 Item: 22 Item: 11 Item: 44 Item: 77 Item: 88 Item: 66 Item: 99 Item: 66 Item: 23 Item: 41
입력된 15개의 모든 요소가 중복 포함하여 그대로 저장되며, 정렬은 전혀 이루어지지 않습니다.
핵심 정리: 언제 어떤 컨테이너를 사용해야 할까?
| 컨테이너 | 정렬 여부 | 중복 허용 | 내부 구조 | 평균 시간 복잡도 |
|---|---|---|---|---|
| set | O | X | 이진 탐색 트리 | O(log n) |
| multiset | O | O | 이진 탐색 트리 | O(log n) |
| unordered_set | X | X | 해시 테이블 | O(1) |
| unordered_multiset | X | O | 해시 테이블 | O(1) |
- 정렬된 순서가 필요하고 중복이 없어야 한다면 → set
- 정렬된 순서가 필요하고 중복도 필요하다면 → multiset
- 빠른 조회만 필요하고 순서가 중요하지 않다면 → unordered_set
- 순서는 상관없고 중복 조회까지 빠르게 하고 싶다면 → unordered_multiset
네 컨테이너 모두 삽입, 삭제, 검색 기능을 제공하지만 내부 구조의 차이 때문에 성능 특성이 다릅니다. 정렬이 필요한 경우 트리 기반 컨테이너(O(log n))를, 순서가 무관하고 최대 성능이 필요한 경우 해시 기반 컨테이너(평균 O(1))를 선택하는 것이 좋습니다.