exclusive_scan
exclusive_scan (접두 합계 — 자기 제외)
범위에 누적 연산(기본 덧셈)을 적용해 접두 합계를 구하되, 각 위치가 자기 자신을 제외한 이전 원소들의 합을 갖도록 하는 알고리즘이에요. <numeric> 헤더, C++17부터.
출처: cppreference
본문
exclusive_scan은 입력 범위 [first, last)를 읽어, d_first부터 각 위치에 "이전 원소들의 누적 + init"을 저장해요. 현재 원소 자신은 포함하지 않아서 "exclusive(배타적)"이라는 이름이 붙었어요.
template< class InputIt, class OutputIt, class T >
OutputIt exclusive_scan( InputIt first, InputIt last,
OutputIt d_first, T init ); // (1)
-
init으로 시작해 각 단계에서 이전까지의 합을 저장하고,+를 누적해요.
-
- 실행 정책 버전(C++17).
- 3,4) 사용자 정의 이진 연산
binary_op버전.
예를 들어 {1, 2, 3, 4}에 init = 0으로 exclusive_scan을 하면 결과는 {0, 1, 3, 6}이에요. 각 출력이 "자기 이전까지의 합"이죠. (inclusive_scan은 {1, 3, 6, 10}이 돼요.)
병렬 실행이 가능해서 큰 배열의 접두 합계를 여러 스레드로 나눠 계산할 때 유용해요. 반환 값은 마지막으로 쓰인 출력 다음 반복자예요.
init이 결과 시퀀스의 첫 원소로 들어간다는 점(즉 첫 원소보다 하나 앞선 "누적 시작값")을 기억하면 inclusive/exclusive가 헷갈리지 않아요.