두 집합의 합집합(Union)은 어느 한쪽 집합 또는 양쪽 집합 모두에 존재하는 원소들로 구성됩니다. 이때 첫 번째 집합에 이미 동일한 원소가 있는 경우, 두 번째 집합의 해당 원소는 결과 집합에 중복되어 복사되지 않습니다.
C++ STL에서 대표적인 집합 연산은 다음과 같습니다.
- 합집합 (Set Union)
- 교집합 (Set Intersection)
- 대칭 차집합 또는 배타적 OR (Symmetric Difference)
- 차집합 또는 뺄셈 (Set Difference)
알고리즘
시작
정수 벡터 v와 반복자(iterator) st를 선언한다.
st = set_union(set1, set1 + n, set2, set2 + n, v.begin()) 으로 초기화한다.
결과 원소들을 출력한다.
끝.예제 코드
아래 예제에서는 두 개의 정수 배열을 정렬한 후, STL의 set_union 알고리즘을 사용하여 합집합을 계산합니다. 반환된 반복자를 이용해 실제 결과 크기만큼 벡터 크기를 조정하는 점에 유의하세요.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int set1[] = {5, 6, 7, 8, 9, 10};
int set2[] = {1, 2, 3, 4, 6, 7};
vector<int> v(10);
vector<int>::iterator st;
// set_union은 정렬된 범위를 요구하므로 먼저 정렬
sort(set1, set1 + 6);
sort(set2, set2 + 6);
st = set_union(set1, set1 + 6, set2, set2 + 6, v.begin());
v.resize(st - v.begin());
cout << "두 집합의 합집합은 " << v.size() << "개의 원소를 가집니다:" << endl;
for (st = v.begin(); st != v.end(); ++st)
cout << *st << " ";
cout << endl;
return 0;
}실행 결과
두 집합의 합집합은 10개의 원소를 가집니다: 1 2 3 4 5 6 7 8 9 10
핵심 포인트
set_union은 입력 범위가 정렬되어 있어야 올바르게 동작합니다.- 결과는 다섯 번째 인자로 전달된 출력 반복자 위치에 저장되며, 함수는 생성된 마지막 원소 다음 위치를 가리키는 반복자를 반환합니다.
- 중복 원소(예: 6, 7)는 한 번만 결과에 포함됩니다.