두 집합의 교집합(intersection)은 두 집합에 공통으로 존재하는 원소들만으로 구성됩니다. std::set_intersection 함수가 복사하는 원소는 항상 첫 번째 집합에서 가져오며, 원래의 순서를 그대로 유지합니다. 이 함수를 사용하려면 두 집합의 원소들이 반드시 이미 정렬되어 있어야 한다는 점에 유의해야 합니다.
주요 집합 연산의 종류
C++ STL에서 자주 사용되는 집합 연산은 다음과 같습니다.
- 합집합(Union) — 두 집합의 모든 원소를 포함
- 교집합(Intersection) — 두 집합에 공통으로 있는 원소만 포함
- 대칭 차집합(Symmetric Difference, XOR) — 한쪽에만 존재하는 원소 포함
- 차집합(Difference) — 첫 번째 집합에만 있는 원소 포함
알고리즘
Begin
정수형 벡터 v와 반복자(iterator) st를 선언한다.
st = set_intersection(set1, set1 + n, set2, set2 + n, v.begin()) 으로 초기화한다.
두 집합의 교집합을 출력한다.
End.
예제 코드
#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;
// 교집합 연산 전에 반드시 정렬 필요
sort(set1, set1 + 6);
sort(set2, set2 + 6);
st = set_intersection(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;
}
실행 결과
두 집합의 교집합은 2개의 원소를 가집니다:
6 7
코드 설명
위 예제에서는 배열 set1과 set2를 각각 정렬한 후, set_intersection 함수를 호출하여 교집합을 계산합니다. 함수는 결과를 벡터 v의 시작 위치부터 저장하며, 반환된 반복자 st를 이용해 실제로 저장된 원소의 개수만큼 벡터 크기를 조정(resize)합니다. 마지막으로 반복자를 순회하며 교집합 원소인 6과 7을 출력합니다.
참고: set_intersection, set_union, set_difference 등의 STL 집합 연산 함수들은 모두 정렬된 입력 범위를 요구하므로, 사용 전에 sort() 또는 std::set 같은 정렬된 컨테이너를 활용하는 것이 좋습니다.