C++에서 Set과 MultiSet은 모두 데이터를 효율적으로 저장하고 빠르게 접근·삽입할 수 있도록 설계된 연관 컨테이너(associative container)입니다. 두 자료구조는 사용 방법이 매우 유사하지만, 중복 값을 처리하는 방식에서 결정적인 차이가 있습니다.
아래 표에서 Set과 MultiSet의 핵심적인 차이점을 항목별로 살펴보겠습니다.
Set과 MultiSet의 주요 차이점
| 번호 | 구분 기준 | Set | MultiSet |
|---|---|---|---|
| 1 | 정의 | Set은 C++의 연관 컨테이너로, 각 원소의 값(value)이 곧 그 원소를 식별하는 키(key) 역할을 하며, 모든 원소는 반드시 고유해야 합니다. | MultiSet은 C++ STL(표준 템플릿 라이브러리)에 포함된 연관 컨테이너로, Set처럼 정렬된 키-값 쌍을 저장합니다. 단, Set과 달리 중복된 키를 허용합니다. |
| 2 | 정렬 | 데이터가 항상 정렬된 상태로 저장됩니다. | 마찬가지로 데이터가 정렬된 순서로 저장됩니다. |
| 3 | 중복 값 | 중복된 값을 저장할 수 없습니다. | 중복된 값을 저장할 수 있습니다. |
| 4 | 값 변경 | 한 번 삽입된 값은 직접 수정할 수 없으며, 삭제 후 다시 삽입하는 방식으로만 변경할 수 있습니다. | 역시 한 번 삽입된 값은 직접 수정할 수 없습니다. |
예제 1: Set 사용하기
다음 예제는 중복된 값이 포함된 배열의 요소들을 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};
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
배열에는 11, 22, 66이 여러 번 등장하지만, Set은 중복을 허용하지 않으므로 각 값이 한 번씩만 출력됩니다.
예제 2: MultiSet 사용하기
동일한 데이터를 이번에는 MultiSet에 삽입해 보겠습니다. 중복 값이 그대로 유지되면서 정렬되어 출력됩니다.
#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;
}
return 0;
}
출력 결과
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
MultiSet은 중복을 허용하므로 11은 2번, 22는 2번, 66은 3번 출력됩니다. 즉, 입력된 모든 값이 개수와 함께 보존됩니다.
정리
두 컨테이너 모두 내부적으로 균형 이진 탐색 트리(레드-블랙 트리)를 기반으로 구현되어 있어 삽입, 삭제, 탐색이 O(log n)의 시간 복잡도로 동작하며, 데이터는 항상 정렬된 상태로 유지됩니다. 따라서 선택 기준은 단순합니다. 고유한 값의 집합이 필요하다면 Set을, 동일한 값이 여러 번 나타나는 것을 허용해야 한다면 MultiSet을 사용하는 것이 적합합니다.