algorithm_partial_sum
algorithm_partial_sum (부분 합계)
std::partial_sum는 범위의 요소들에 대한 부분 합계(prefix sum)를 계산해서 출력 범위에 저장해요. 각 위치에 시작부터 그 위치까지의 누적 합이 저장돼요.
출처: cppreference
본문
std::partial_sum는 <numeric> 헤더에 정의되어 있어요.
template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first, InputIt last,
OutputIt d_first );
template< class InputIt, class OutputIt, class BinaryOp >
OutputIt partial_sum( InputIt first, InputIt last,
OutputIt d_first, BinaryOp op );
- 1번 오버로드 —
[first, last)가 비어 있으면 아무것도 하지 않아요. 그렇지 않으면:InputIt의 값 타입 누적기acc를 만들어*first로 초기화해요.acc를*d_first에 할당해요.[1, std::distance(first, last))의 각 정수i에 대해acc를acc + *(first + i)(또는op)로 갱신하고*(d_first + i)에 할당해요.
- 2번 오버로드 —
+대신 이항 연산op를 사용해요.
반환값 (Return value)
출력 범위의 끝(past-the-end) 반복자예요.
복잡도 (Complexity)
정확히 std::distance(first, last) - 1번의 이항 연산 적용이 필요해요.
예제 (Example)
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
int main()
{
std::vector<int> v{2, 2, 2, 2, 2, 2, 2, 2, 2, 2};
std::partial_sum(v.cbegin(), v.cend(), v.begin());
for (int n : v) std::cout << n << ' ';
std::cout << '\n';
}
출력:
2 4 6 8 10 12 14 16 18 20