두 집합의 차집합(Difference)은 첫 번째 집합에는 포함되어 있지만 두 번째 집합에는 없는 원소들로만 구성됩니다. set_difference 함수가 복사하는 원소는 항상 첫 번째 집합에서 가져오며, 원래의 순서가 그대로 유지됩니다. 이때 주의할 점은 두 집합의 원소들이 반드시 미리 정렬되어 있어야 한다는 것입니다.
C++에서 자주 사용되는 대표적인 집합 연산은 다음과 같습니다.
- 합집합(Union): 두 집합의 모든 원소를 포함
- 교집합(Intersection): 두 집합에 공통으로 존재하는 원소만 포함
- 대칭 차집합(Symmetric Difference, XOR): 한쪽에만 존재하는 원소 포함
- 차집합(Difference, Subtraction): 첫 번째 집합에만 존재하는 원소 포함
알고리즘
set_difference를 활용한 차집합 계산 절차는 다음과 같습니다.
Begin
벡터 v와 반복자 st를 선언한다.
st = set_difference(set1, set1 + n, set2, set2 + n, v.begin()) 으로 초기화한다.
두 집합 간 서로 다른 원소의 개수를 출력한다.
End.
예제 코드
아래 예제는 두 개의 정수 배열을 정렬한 뒤, set_difference로 차집합을 계산하고 그 결과를 출력합니다.
#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 it;
sort (set1, set1 + 6);
sort (set2, set2 + 6);
it = set_difference(set1, set1 + 6, set2, set2 + 6, v.begin());
v.resize(it - v.begin());
cout << "The difference between the sets has " << (v.size()) << " elements: "<<endl;
for (it = v.begin(); it != v.end(); ++it)
cout<< *it<<" ";
cout <<endl;
return 0;
}
실행 결과
The difference between the sets has 4 elements
5 8 9 10
코드 설명
위 코드에서 set1 = {5,6,7,8,9,10}과 set2 = {1,2,3,4,6,7}을 비교하면, 첫 번째 집합에만 존재하는 원소는 5, 8, 9, 10입니다. 공통 원소인 6과 7은 차집합에서 제외됩니다.
set_difference는 결과의 끝 위치를 가리키는 반복자를 반환하므로, v.resize(it - v.begin())을 통해 벡터 크기를 실제 결과 개수에 맞게 조정하는 것이 좋습니다. 또한 이 알고리즘은 내부적으로 정렬된 데이터를 전제로 동작하기 때문에, 입력 배열이 정렬되어 있지 않다면 반드시 sort를 먼저 호출해야 올바른 결과를 얻을 수 있습니다.