algorithm_includes
algorithm_includes (부분 수열 포함 검사)
std::includes는 정렬된 대상 범위가 정렬된 소스 범위의 부분 수열(subsequence)인지 검사해요. 집합 연산의 포함 관계를 확인하는 데 써요.
출처: cppreference
본문
std::includes는 정렬된 대상 범위 [first2, last2)가 정렬된 소스 범위 [first1, last1)의 부분 수열인지 검사해요. 수열 S가 다른 수열 T의 부분 수열이라는 것은 T의 요소를 임의로 제거해서 남은 요소의 순서를 그대로 유지했을 때 S를 얻을 수 있음을 뜻해요. <algorithm> 헤더에 정의되어 있어요.
template< class InputIt1, class InputIt2 >
bool includes( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2 );
template< class InputIt1, class InputIt2, class Compare >
bool includes( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, Compare comp );
- 1번 오버로드 — 두 범위가
operator<(즉std::less{})로 정렬되어 있어야 해요. - 2번 오버로드 — 두 범위가 비교 함수
comp로 정렬되어 있어야 해요.
병렬 실행 정책을 받는 오버로드도 있어요.
반환값 (Return value)
두 번째 범위가 첫 번째 범위의 부분 수열이면 true, 아니면 false예요.
복잡도 (Complexity)
N₁을 std::distance(first1, last1), N₂를 std::distance(first2, last2)라고 하면 최대 N₁ + N₂ - 1번의 비교(또는 comp 적용)가 필요해요.
예제 (Example)
#include <algorithm>
#include <cctype>
#include <iostream>
int main()
{
std::cout << std::boolalpha;
std::vector<char> v1{'a', 'b', 'c', 'f', 'h', 'x'};
std::vector<char> v2{'a', 'b', 'c'};
std::vector<char> v3{'a', 'c'};
std::vector<char> v4{'g'};
std::cout << std::includes(v1.begin(), v1.end(), v2.begin(), v2.end()) << ' ';
std::cout << std::includes(v1.begin(), v1.end(), v3.begin(), v3.end()) << ' ';
std::cout << std::includes(v1.begin(), v1.end(), v4.begin(), v4.end()) << '\n';
}
출력:
true true false