C++ STL set_intersection()으로 두 벡터의 공통 요소 찾는 방법

이 글에서는 C++의 STL(표준 템플릿 라이브러리)을 활용해 두 벡터 사이의 공통 요소를 찾는 방법을 알아보겠습니다.

두 벡터에서 공통으로 존재하는 요소를 추출하려면 set_intersection() 메서드를 사용하는 것이 가장 간단합니다. 이 함수는 이름 그대로 두 집합의 교집합에 해당하는 요소들을 구해주며, 단 두 범위가 모두 사전에 정렬되어 있어야 올바르게 동작한다는 점에 유의해야 합니다.

구현 절차

1. 두 개의 벡터를 선언하고 값을 초기화합니다.
2. sort() 함수를 사용해 두 벡터를 모두 오름차순으로 정렬합니다.
3. 결과를 저장할 충분히 큰 크기의 벡터를 준비합니다.
4. set_intersection()을 호출해 공통 요소를 찾고, 반환된 반복자까지만 순회하며 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int main(){
   //벡터 정의
   vector<int> vector1 = { 1, 45, 54, 71, 76, 12 };
   vector<int> vector2 = { 1, 7, 5, 4, 6, 12 };
   sort(vector1.begin(), vector1.end());
   sort(vector2.begin(), vector2.end());
   cout << "First Vector: ";
   for (int i = 0; i < vector1.size(); i++)
      cout << vector1[i] << " ";
   cout << endl;
   cout << "Second Vector: ";
   for (int i = 0; i < vector2.size(); i++)
      cout << vector2[i] << " ";
   cout << endl;
   vector<int> v(vector1.size() + vector2.size());
   vector<int>::iterator it, st;
   //공통 요소 찾기
   it = set_intersection(vector1.begin(), vector1.end(), vector2.begin(), vector2.end(), v.begin());
   cout << "\nCommon elements:\n";
   for (st = v.begin(); st != it; ++st)
      cout << *st << ", ";
   cout << '\n';
   return 0;
}

실행 결과

First Vector: 1 12 45 54 71 76
Second Vector: 1 4 5 6 7 12
Common elements:
1, 12,

코드 설명

위 예제에서 먼저 두 벡터를 sort()로 정렬하는 이유는 set_intersection()이 정렬된 입력 범위를 전제로 동작하기 때문입니다. 함수는 네 개의 반복자 인수로 두 범위의 시작과 끝을 받고, 다섯 번째 인수로 지정된 출력 위치에 공통 요소를 복사한 뒤, 실제로 마지막으로 기록된 바로 다음 위치를 가리키는 반복자를 반환합니다.

따라서 결과 벡터의 시작부터 반환된 반복자 it까지 순회하면 중복 없이 공통 요소인 1과 12만 깔끔하게 얻을 수 있습니다. 참고로 결과 벡터의 크기를 두 벡터 크기의 합으로 잡은 것은 최악의 경우(모든 요소가 겹치는 경우)에도 결과를 담을 수 있도록 하기 위함입니다.