includes
includes (정렬 범위가 다른 정렬 범위를 포함하는지)
첫 번째 정렬된 범위가 두 번째 정렬된 범위의 모든 원소를 포함하는지 확인하는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
includes는 정렬된 범위 [first1, last1)이 정렬된 범위 [first2, last2)를 포함하는지 판정해요.
template< class InputIt1, class InputIt2 >
bool includes( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2 ); // (1)
비교기 comp를 받는 버전도 있어요.
template< class InputIt1, class InputIt2, class Compare >
bool includes( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, Compare comp ); // (2)
두 범위는 반드시 비교 기준으로 정렬되어 있어야 해요. [first2, last2)의 모든 원소가 [first1, last1)에 존재하면(개수까지 고려) true를 반환해요.
-
operator<로, 2)comp로 비교해요.
- 복잡도: 최대
2·(N1 + N2 - 1)번의 비교(N1, N2는 각 범위 크기).
std::vector<int> a{1, 2, 3, 4, 5, 6};
std::vector<int> b{2, 4, 6};
bool sub = std::includes(a.begin(), a.end(), b.begin(), b.end()); // true
집합 연산(set_union 등) 계열의 일부예요. 집합 이론의 "부분집합 포함"을 정렬된 시퀀스로 확인할 때 써요.