algorithm_accumulate
algorithm_accumulate (구간 누적 합계)
std::accumulate는 범위 [first, last)의 요소들과 초기값 init을 더한 총합을 계산해요. 이항 연산자를 직접 전달해서 동작을 바꿀 수도 있답니다.
출처: cppreference
본문
std::accumulate는 주어진 초기값 init과 범위 [first, last)의 요소들을 순서대로 처리해서 값을 축적해요. <numeric> 헤더에 정의되어 있어요.
template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );
template< class InputIt, class T, class BinaryOp >
T accumulate( InputIt first, InputIt last, T init, BinaryOp op );
T 타입의 누적기(accumulator) acc를 초기값 init으로 시작해요.
- 1번 오버로드 —
acc = acc + *i(C++20부터는acc = std::move(acc) + *i)로 범위의 각 반복자i를 순서대로 처리해요. - 2번 오버로드 —
acc = op(acc, *i)(C++20부터는acc = op(std::move(acc), *i))로 사용자 정의 이항 연산자op를 적용해요.
다음 조건이 하나라도 만족되면 동작이 정의되지 않아요(undefined behavior):
T가CopyConstructible(복사 생성 가능)하지 않을 때T가CopyAssignable(복사 할당 가능)하지 않을 때op가 범위[first, last)의 요소를 수정할 때op가 범위[first, last]의 반복자나 하위 범위를 무효화할 때
매개변수 (Parameters)
first,last— 누적할 요소들의 범위init— 누적의 초기값op— 적용할 이항 연산
반환값 (Return value)
모든 수정을 거친 후의 acc예요.
복잡도 (Complexity)
N을 std::distance(first, last)라고 하면 N번의 이항 연산 적용이 필요해요.
참고 (Notes)
std::accumulate는 왼쪽 폴드(left fold)를 수행해요. 오른쪽 폴드(right fold)를 하려면 이항 연산자의 인자 순서를 뒤집고 역방향 반복자를 사용해야 해요.
타입 추론에 맡기면 op는 init과 같은 타입으로 동작해서 반복자 요소가 원치 않게 형변환될 수 있어요. 예를 들어 v가 std::vector<double>일 때 std::accumulate(v.begin(), v.end(), 0)은 원하는 결과를 주지 못할 가능성이 높아요.
예제 (Example)
#include <functional>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
int main()
{
std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int sum = std::accumulate(v.begin(), v.end(), 0);
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
auto dash_fold = [](std::string a, int b)
{
return std::move(a) + '-' + std::to_string(b);
};
std::string s = std::accumulate(std::next(v.begin()), v.end(),
std::to_string(v[0]), // start with first element
dash_fold);
// Right fold using reverse iterators
std::string rs = std::accumulate(std::next(v.rbegin()), v.rend(),
std::to_string(v.back()), // start with last element
dash_fold);
std::cout << "sum: " << sum << '\n'
<< "product: " << product << '\n'
<< "dash-separated string: " << s << '\n'
<< "dash-separated string (right-folded): " << rs << '\n';
}
출력:
sum: 55
product: 3628800
dash-separated string: 1-2-3-4-5-6-7-8-9-10
dash-separated string (right-folded): 10-9-8-7-6-5-4-3-2-1
가능한 구현 (Possible implementation)
template<class InputIt, class T>
constexpr // since C++20
T accumulate(InputIt first, InputIt last, T init)
{
for (; first != last; ++first)
init = std::move(init) + *first; // std::move since C++20
return init;
}
template<class InputIt, class T, class BinaryOperation>
constexpr // since C++20
T accumulate(InputIt first, InputIt last, T init, BinaryOperation op)
{
for (; first != last; ++first)
init = op(std::move(init), *first); // std::move since C++20
return init;
}