multiset(다중 집합)은 C++ STL에서 제공하는 연관 컨테이너(associative container)의 일종으로, 중복된 값을 가지는 여러 요소를 저장할 수 있다는 점이 set과 가장 큰 차이점입니다. 내부적으로 균형 이진 탐색 트리(레드-블랙 트리)로 구현되어 있어 삽입, 삭제, 검색 연산이 모두 O(log n)의 시간 복잡도를 가집니다.
multiset의 주요 함수
이번 예제에서 사용되는 multiset의 핵심 멤버 함수는 다음과 같습니다.
ms.size(): multiset에 저장된 요소의 개수를 반환합니다.ms.insert(): multiset에 새로운 요소를 삽입합니다. 반복자를 인자로 넘기면 해당 위치 근처에 삽입을 시도해 성능을 높일 수 있습니다.ms.erase(): 지정한 값을 multiset에서 삭제합니다. 값이 여러 개일 경우 해당 값을 가진 모든 요소가 제거됩니다.ms.find(): 검색한 요소가 존재하면 해당 위치의 반복자를 반환하고, 없으면end()반복자를 반환합니다.ms.count(): 특정 키와 일치하는 요소의 개수를 반환합니다. multiset은 중복을 허용하므로 1보다 큰 값이 나올 수 있습니다.ms.begin(): multiset의 첫 번째 요소를 가리키는 반복자를 반환합니다.ms.end(): 마지막 요소 다음 위치를 가리키는 반복자를 반환합니다.
예제 코드
아래 프로그램은 메뉴 기반으로 multiset의 다양한 연산을 직접 테스트할 수 있도록 작성된 예제입니다.
#include<iostream>
#include <set>
#include <string>
#include <cstdlib>
using namespace std;
int main() {
multiset<int> ms;
multiset<int>::iterator it, it1;
int c, i;
while (1) {
cout<<"1.Size of the Multiset"<<endl;
cout<<"2.Insert Element into the Multiset"<<endl;
cout<<"3.Delete Element from the Multiset"<<endl;
cout<<"4.Find Element in a Multiset"<<endl;
cout<<"5.Count Elements with a specific key"<<endl;
cout<<"6.Display Multiset"<<endl;
cout<<"7.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Size of the Multiset: "<<ms.size()<<endl;
break;
case 2:
cout<<"Enter value to be inserted: ";
cin>>i;
if (ms.empty())
it1 = ms.insert(i);
else
it1 = ms.insert(it1, i);
break;
case 3:
cout<<"Enter value to be deleted: ";
cin>>i;
ms.erase(i);
break;
case 4:
cout<<"Enter element to find ";
cin>>i;
it = ms.find(i);
if (it != ms.end())
cout<<"Element found"<<endl;
else
cout<<"Element not found"<<endl;
break;
case 5:
cout<<"Enter element to be counted: ";
cin>>i;
cout<<i<<" appears "<<ms.count(i)<<" times."<<endl;
break;
case 6:
cout<<"Elements of the Multiset: ";
for (it = ms.begin(); it != ms.end(); it++)
cout<<*it<<" ";
cout<<endl;
break;
case 7:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
실행 결과
1.Size of the Multiset 2.Insert Element into the Multiset 3.Delete Element from the Multiset 4.Find Element in a Multiset 5.Count Elements with a specific key 6.Display Multiset 7.Exit Enter your Choice: 1 Size of the Multiset: 0 ... Enter your Choice: 2 Enter value to be inserted: 1 ... Enter your Choice: 2 Enter value to be inserted: 2 ... Enter your Choice: 2 Enter value to be inserted: 3 ... Enter your Choice: 2 Enter value to be inserted: 4 ... Enter your Choice: 6 Elements of the Multiset: 1 2 3 4 ... Enter your Choice: 3 Enter value to be deleted: 4 ... Enter your Choice: 4 Enter element to find 1 Element found ... Enter your Choice: 5 Enter element to be counted: 2 2 appears 1 times. ... Enter your Choice: 7 Exit code: 1
코드 설명 및 참고 사항
실행 결과를 보면 사용자가 메뉴 번호를 입력하여 multiset의 크기 확인, 요소 삽입·삭제, 검색, 개수 세기, 전체 출력 등의 기능을 순서대로 테스트한 것을 알 수 있습니다. 몇 가지 유의할 점은 다음과 같습니다.
- 자동 정렬: multiset에 요소를 삽입하면 항상 오름차순으로 자동 정렬되어 저장됩니다. 위 예제에서도 1, 2, 3, 4 순서로 출력됩니다.
- 중복 허용: 동일한 값을 여러 번 삽입하면 모두 저장되며,
count()함수로 중복 개수를 확인할 수 있습니다. - erase()의 동작: 값으로 삭제할 경우 그 값과 일치하는 모든 요소가 한꺼번에 제거됩니다. 하나만 삭제하려면 반복자를 이용해야 합니다.
- find() 활용: 반환된 반복자가
end()와 같은지 비교하여 요소의 존재 여부를 판단하는 것이 일반적인 패턴입니다.
이처럼 multiset은 중복 데이터를 정렬된 상태로 관리해야 할 때 매우 유용한 컨테이너입니다. 우선순위 큐나 빈도 계산 등 다양한 알고리즘 문제에서도 폭넓게 활용되니, 위 예제를 직접 실행해 보며 각 함수의 동작을 익혀 보시기 바랍니다.