이 글에서는 C++ STL(표준 템플릿 라이브러리)의 멀티셋(multiset)에 대해 자세히 알아보겠습니다. 멀티셋의 기본 개념부터 삽입, 삭제, 탐색까지 실제 예제 코드를 통해 쉽게 이해할 수 있도록 정리했습니다.
멀티셋(multiset)이란?
멀티셋은 연관 컨테이너(associative container)의 일종으로, 일반적인 셋(set)과 매우 유사하게 동작합니다. 두 컨테이너의 가장 큰 차이점은 다음과 같습니다.
- 셋(set): 중복된 값을 허용하지 않습니다.
- 멀티셋(multiset): 중복된 값도 함께 저장할 수 있습니다.
멀티셋은 내부적으로 균형 이진 탐색 트리(레드-블랙 트리)로 구현되어 있어, 요소가 항상 정렬된 상태로 유지됩니다. 따라서 삽입, 삭제, 탐색 연산이 O(log n)의 시간 복잡도로 수행됩니다.
예제 코드
아래 예제에서는 내림차순 정렬 옵션(greater<int>)을 사용한 멀티셋 생성, 값 삽입, 반복자를 이용한 순회, 특정 범위 삭제, 그리고 lower_bound와 upper_bound 함수의 사용법을 확인할 수 있습니다.
#include <iostream>
#include <set>
#include <iterator>
using namespace std;
int main(){
// 내림차순 정렬되는 멀티셋 선언
multiset <int, greater <int> > gquiz1;
// 값 삽입 (50은 중복으로 삽입)
gquiz1.insert(40);
gquiz1.insert(30);
gquiz1.insert(60);
gquiz1.insert(20);
gquiz1.insert(50);
gquiz1.insert(50);
gquiz1.insert(10);
// 반복자 선언 및 첫 번째 멀티셋 출력
multiset <int, greater <int> > :: iterator itr;
cout << "\nThe multiset gquiz1 is : ";
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr)
{
cout << '\t' << *itr;
}
cout << endl;
// gquiz1의 begin()부터 end()까지 복사하여 gquiz2 생성
multiset <int> gquiz2(gquiz1.begin(), gquiz1.end());
cout << "\nThe multiset gquiz2 after assign from gquiz1 is : ";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
{
cout << '\t' << *itr;
}
cout << endl;
// 30 미만인 요소들 삭제
cout << "\ngquiz2 after removal of elements less than 30 : ";
gquiz2.erase(gquiz2.begin(), gquiz2.find(30));
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
{
cout << '\t' << *itr;
}
// 값 50을 모두 삭제하고 삭제된 개수 반환받기
int num;
num = gquiz2.erase(50);
cout << "\ngquiz2.erase(50) : ";
cout << num << " removed \t";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
{
cout << '\t' << *itr;
}
cout << endl;
// lower_bound와 upper_bound 확인
cout << "gquiz1.lower_bound(40) : " << *gquiz1.lower_bound(40) << endl;
cout << "gquiz1.upper_bound(40) : " << *gquiz1.upper_bound(40) << endl;
cout << "gquiz2.lower_bound(40) : " << *gquiz2.lower_bound(40) << endl;
cout << "gquiz2.upper_bound(40) : " << *gquiz2.upper_bound(40) << endl;
return 0;
}실행 결과
The multiset gquiz1 is : 60 50 50 40 30 20 10 The multiset gquiz2 after assign from gquiz1 is : 10 20 30 40 50 50 60 gquiz2 after removal of elements less than 30 : 30 40 50 50 60 gquiz2.erase(50) : 2 removed 30 40 60 gquiz1.lower_bound(40) : 40 gquiz1.upper_bound(40) : 30 gquiz2.lower_bound(40) : 40 gquiz2.upper_bound(40) : 60
코드 핵심 포인트
1. 내림차순 정렬 멀티셋
multiset<int, greater<int>>처럼 비교 연산자를 지정하면 기본 오름차순 대신 내림차순으로 정렬됩니다. 그래서 gquiz1은 60 50 50 40 30 20 10 순서로 출력됩니다.
2. 반복자를 통한 복사 생성
multiset<int> gquiz2(gquiz1.begin(), gquiz1.end());와 같이 다른 멀티셋의 반복자 범위를 전달하면 새로운 멀티셋을 만들 수 있습니다. 이때 gquiz2는 기본 정렬 기준(오름차순)을 따릅니다.
3. erase() 함수의 두 가지 동작
- 범위 삭제:
erase(begin(), find(30))은 시작 위치부터 값 30을 찾기 전까지의 모든 요소를 제거합니다. - 값 삭제:
erase(50)은 값 50에 해당하는 모든 중복 요소를 삭제하고, 삭제된 개수를 반환합니다. 위 예제에서는 50이 두 개 저장되어 있으므로 '2 removed'가 출력됩니다. 이것이 멀티셋이 셋과 다른 점을 보여주는 대표적인 예입니다.
4. lower_bound와 upper_bound
- lower_bound(k): 값 k 이상인 첫 번째 요소의 반복자를 반환합니다.
- upper_bound(k): 값 k보다 큰 첫 번째 요소의 반복자를 반환합니다.
정렬 방향에 따라 결과가 달라진다는 점에 주의하세요. 내림차순으로 정렬된 gquiz1에서 upper_bound(40)은 40보다 작은 값 중 첫 번째인 30을 반환하고, 오름차순으로 정렬된 gquiz2에서는 40보다 큰 값인 60을 반환합니다.
마무리
멀티셋은 중복 데이터를 정렬된 상태로 관리해야 할 때 매우 유용한 컨테이너입니다. 빈도수 계산, 구간 검색 등 다양한 알고리즘 문제에서 활용되므로, insert, erase, lower_bound, upper_bound 같은 핵심 멤버 함수의 동작을 확실히 익혀두는 것이 좋습니다.