algorithm_set_intersection
algorithm_set_intersection (교집합)
std::set_intersection는 두 정렬된 소스 범위의 교집합을 구성해서 목적지 범위에 복사해요. 두 범위 모두에 있는 요소들로 구성돼요.
출처: cppreference
본문
std::set_intersection는 두 정렬된 소스 범위 [first1, last1)과 [first2, last2)의 교집합을 구성해요. 교집합은 두 소스 범위 모두에 존재하는 요소들로 이루어져요. 그 요소들을 d_first에서 시작하는 목적지 범위로 복사해요. <algorithm> 헤더에 정의되어 있어요.
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_intersection( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first );
template< class InputIt1, class InputIt2,
class OutputIt, class Compare >
OutputIt set_intersection( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first, Compare comp );
- 1번 오버로드 — 요소를
operator<(즉std::less{})로 비교해요. - 2번 오버로드 — 요소를 비교 함수
comp로 비교해요.
병렬 실행 정책을 받는 오버로드도 있어요.
반환값 (Return value)
복사된 마지막 요소 다음의 반복자예요.
복잡도 (Complexity)
최대 2·(N₁ + N₂) - 1번의 비교가 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
std::vector<int> v1{1, 2, 3, 4, 5};
std::vector<int> v2{3, 4, 5, 6, 7};
std::vector<int> out;
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::back_inserter(out));
for (int x : out) std::cout << x << ' ';
std::cout << '\n';
}
출력:
3 4 5