C++ Algorithm Numeric | accumulate·reduce
이 글의 핵심
accumulate에 초기값으로 0을 넘기면 double 합계가 정수로 잘리는 것처럼, 수치 알고리즘은 타입과 순서에서 조용한 버그가 생기기 쉽습니다. 병렬 실행 정책을 쓸 수 있는 reduce가 결합 법칙을 요구하는 이유, 오버플로와 부동소수점 정밀도 문제, C++20 Ranges에서의 누적 방식까지 다룹니다.
들어가며
C++ <numeric> 헤더는 수치 연산에 특화된 알고리즘을 제공합니다. 합계, 곱셈, 내적, 누적 합 등 수학적 연산을 표준 라이브러리로 간결하게 표현할 수 있으며, C++17부터는 병렬 실행 정책을 지원해 대용량 데이터를 여러 코어로 나눠 처리할 수 있습니다.
<numeric>의 알고리즘은 대부분 for 루프 몇 줄로도 쓸 수 있는 일을 합니다. 그래도 표준 알고리즘을 쓰는 이유는 의도가 이름으로 드러나고, C++17 이후 버전은 실행 정책 하나만 바꿔 병렬화할 수 있기 때문입니다. 대신 이 알고리즘들은 “초기값의 타입으로 누적한다”, “reduce는 순서를 바꿔도 된다고 가정한다” 같은 조용한 전제를 깔고 있어서, 루프로 직접 썼다면 보였을 버그가 호출 한 줄 안에 숨어 버리기도 합니다. 아래에서는 각 알고리즘의 사용법과 함께 이 전제들을 짚습니다.
기본 알고리즘
주요 알고리즘 목록
| 알고리즘 | 용도 | C++ 버전 |
|---|---|---|
| accumulate | 범위 집계 (순차) | C++98 |
| reduce | 범위 집계 (병렬 가능) | C++17 |
| transform_reduce | 변환 후 집계 | C++17 |
| inner_product | 내적 | C++98 |
| partial_sum | 누적 합 | C++98 |
| inclusive_scan | 누적 합 (병렬) | C++17 |
| exclusive_scan | 누적 합 (현재 제외) | C++17 |
| adjacent_difference | 인접 차이 | C++98 |
| iota | 순차 값 생성 | C++11 |
실전 구현
accumulate - 범위 집계
시그니처:
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);기본 사용
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
// 합계
int sum = std::accumulate(v.begin(), v.end(), 0);
std::cout << "합: " << sum << std::endl; // 15
// 곱
int product = std::accumulate(v.begin(), v.end(), 1,
[](int a, int b) { return a * b; });
std::cout << "곱: " << product << std::endl; // 120
return 0;
}커스텀 연산
#include <numeric>
#include <vector>
#include <string>
int main() {
std::vector<std::string> words = {"Hello", " ", "World", "!"};
// 문자열 연결
std::string sentence = std::accumulate(
words.begin(),
words.end(),
std::string(""),
[](const std::string& a, const std::string& b) {
return a + b;
}
);
std::cout << sentence << std::endl; // Hello World!
return 0;
}시간 복잡도: O(n)
공간 복잡도: O(1)
accumulate의 반환 타입과 누적 중간값의 타입은 원소 타입이 아니라 초기값 T의 타입입니다. 시그니처가 T accumulate(InputIt, InputIt, T init)이기 때문입니다. 그래서 std::vector<double>을 accumulate(v.begin(), v.end(), 0)으로 더하면 매 단계 int + double의 결과가 다시 int로 잘려 소수점이 모두 사라지고, 컴파일러는 경고도 거의 하지 않습니다(GCC의 -Wconversion을 켜야 보입니다). 문자열 연결 예제에서 std::string("")을 명시한 것도 같은 이유입니다. ""만 넘기면 T가 const char*로 추론되어 const char* + std::string 연산이 되고, 람다의 반환값을 다시 const char*에 넣으려다 컴파일 에러가 납니다.
문자열 연결을 accumulate로 하는 것이 느리다는 말도 있었는데, C++20부터는 표준이 init = std::move(init) + *first 형태로 누적하도록 바뀌어 매 단계 문자열 전체를 복사하지는 않습니다. 다만 위 람다처럼 const std::string& a로 받으면 이동의 이점이 사라지므로, 큰 문자열을 모은다면 std::string a를 값으로 받거나 reserve 후 루프로 +=하는 편이 확실합니다.
reduce - 병렬 집계 (C++17)
시그니처:
template<class ExecutionPolicy, class ForwardIt, class T>
T reduce(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init);기본 사용
#include <numeric>
#include <vector>
#include <execution>
#include <iostream>
int main() {
std::vector<int> v(1000000, 1);
// 순차 실행
auto sum1 = std::reduce(v.begin(), v.end(), 0);
// 병렬 실행
auto sum2 = std::reduce(std::execution::par, v.begin(), v.end(), 0);
// 병렬 + 벡터화
auto sum3 = std::reduce(std::execution::par_unseq, v.begin(), v.end(), 0);
std::cout << "합: " << sum2 << std::endl; // 1000000
return 0;
}accumulate vs reduce
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<double> v = {1.0, 2.0, 3.0, 4.0, 5.0};
// accumulate: 순서 보장 (왼쪽부터)
double sum1 = std::accumulate(v.begin(), v.end(), 0.0);
// reduce: 순서 보장 안 됨 (병렬 가능)
double sum2 = std::reduce(v.begin(), v.end(), 0.0);
// 부동소수점은 순서에 따라 결과 미세하게 다를 수 있음
std::cout << "accumulate: " << sum1 << std::endl;
std::cout << "reduce: " << sum2 << std::endl;
return 0;
}주의사항:
reduce는 결합법칙을 가정- 부동소수점은 순서에 따라 결과 다를 수 있음
- 병렬 실행 시 데이터 경합 주의
정확히는 reduce의 연산은 결합법칙뿐 아니라 교환법칙도 만족해야 합니다. 표준은 원소를 어떤 순서로 묶고 어떤 순서로 합쳐도 된다고 허용하기 때문입니다. 덧셈과 곱셈은 괜찮지만, 앞의 문자열 연결처럼 순서가 의미를 갖는 연산을 reduce에 넘기면 병렬 정책에서 "World!Hello "처럼 순서가 뒤섞인 결과가 나올 수 있고, 순차 버전에서도 구현이 순서를 바꾸는 것을 막지 않습니다. 순서가 중요한 집계는 accumulate를 써야 합니다. 부동소수점 덧셈은 수학적으로는 교환·결합이 성립하지만 반올림 때문에 실제로는 결합 순서에 따라 결과가 조금씩 달라지므로, 병렬 reduce의 결과가 실행할 때마다 마지막 자리에서 달라지는 것은 버그가 아니라 정상입니다. 테스트에서 ==로 비교하면 가끔 실패하는 테스트가 되므로 허용 오차를 두고 비교해야 합니다.
transform_reduce - 변환 후 집계 (C++17)
시그니처:
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T>
T transform_reduce(ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, T init);내적 (Dot Product)
#include <numeric>
#include <vector>
#include <execution>
#include <iostream>
int main() {
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {2, 2, 2, 2, 2};
// 내적: v1[i] * v2[i]의 합 (기본 연산: 원소끼리 multiplies, 합칠 때 plus)
int dotProduct = std::transform_reduce(
std::execution::par,
v1.begin(), v1.end(),
v2.begin(),
0
);
std::cout << "내적: " << dotProduct << std::endl; // 30
return 0;
}제곱합
#include <numeric>
#include <vector>
#include <execution>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
// 제곱합: sum(v[i]^2)
int sumOfSquares = std::transform_reduce(
std::execution::par,
v.begin(), v.end(),
0,
std::plus<>(),
[](int x) { return x * x; }
);
std::cout << "제곱합: " << sumOfSquares << std::endl; // 55
return 0;
}시간 복잡도: O(n)
공간 복잡도: O(1)
transform_reduce에는 두 가지 형태가 있습니다. 두 범위를 받는 형태는 대응 원소를 “곱하고(transform) 더하는(reduce)” 내적이 기본값이고, 한 범위를 받는 형태는 초기값 다음에 합치기 연산과 변환 연산을 차례로 받습니다. 제곱합 예제에서 std::plus<>()가 먼저, 람다가 나중에 오는 것이 이 순서입니다. 두 연산의 순서를 바꿔 쓰면 타입이 맞는 경우 컴파일은 되는데 엉뚱한 값이 나오므로 헷갈리기 쉽습니다. transform과 reduce를 따로 호출하면 중간 결과를 담을 벡터가 필요하지만, transform_reduce는 변환한 값을 바로 누적하므로 메모리를 한 번만 훑고 추가 할당이 없다는 것이 장점입니다.
inner_product - 내적
시그니처:
template<class InputIt1, class InputIt2, class T>
T inner_product(InputIt1 first1, InputIt1 last1,
InputIt2 first2, T init);기본 사용
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};
// 내적: 1*4 + 2*5 + 3*6 = 32
int result = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
std::cout << "내적: " << result << std::endl; // 32
return 0;
}커스텀 연산
#include <numeric>
#include <vector>
int main() {
std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};
// 합(곱) 대신 곱(합) 사용
// (1+4) * (2+5) * (3+6) = 5 * 7 * 9 = 315
int result = std::inner_product(
v1.begin(), v1.end(), v2.begin(), 1,
std::multiplies<>(), // 외부 연산: 곱
std::plus<>() // 내부 연산: 합
);
std::cout << "결과: " << result << std::endl; // 315
return 0;
}inner_product는 두 번째 범위의 끝을 받지 않습니다. 첫 번째 범위 길이만큼 두 번째 범위를 읽으므로, v2가 v1보다 짧으면 범위 밖을 읽는 미정의 동작이 되고 컴파일러도 런타임도 이를 알려 주지 않습니다. 호출 전에 크기가 같은지 확인하는 습관이 필요하고, C++23 이전의 Ranges에는 두 범위의 길이를 함께 검사하는 대체 알고리즘이 없어 직접 assert를 두는 경우가 많습니다. inner_product는 항상 왼쪽부터 순차로 계산하므로, 병렬화나 순서 무관 최적화가 필요하다면 같은 일을 하는 transform_reduce를 쓰면 됩니다.
partial_sum - 누적 합
시그니처:
template<class InputIt, class OutputIt>
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first);기본 사용
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> result(v.size());
// 누적 합: [1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5]
std::partial_sum(v.begin(), v.end(), result.begin());
for (int x : result) {
std::cout << x << " "; // 1 3 6 10 15
}
std::cout << std::endl;
return 0;
}누적 곱
#include <numeric>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> result(v.size());
// 누적 곱
std::partial_sum(v.begin(), v.end(), result.begin(),
std::multiplies<>());
for (int x : result) {
std::cout << x << " "; // 1 2 6 24 120
}
return 0;
}inclusive_scan vs exclusive_scan (C++17)
inclusive_scan
#include <numeric>
#include <vector>
#include <execution>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> result(v.size());
// 누적 합 (병렬)
std::inclusive_scan(
std::execution::par,
v.begin(), v.end(),
result.begin()
);
for (int x : result) {
std::cout << x << " "; // 1 3 6 10 15
}
return 0;
}exclusive_scan
#include <numeric>
#include <vector>
#include <execution>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> result(v.size());
// 누적 합 (현재 원소 제외)
std::exclusive_scan(
std::execution::par,
v.begin(), v.end(),
result.begin(),
0 // 초기값
);
for (int x : result) {
std::cout << x << " "; // 0 1 3 6 10
}
return 0;
}차이점:
inclusive_scan: 현재 원소 포함exclusive_scan: 현재 원소 제외
inclusive_scan은 결과만 보면 partial_sum과 같지만, reduce와 마찬가지로 연산의 결합법칙을 가정하고 순서를 바꿔 계산할 수 있다는 점이 다릅니다. 그래서 병렬 정책을 쓸 수 있는 대신, 부동소수점 누적 합은 partial_sum과 마지막 자리가 다를 수 있습니다. exclusive_scan은 “i번째 원소 앞까지의 합”을 주므로, 가변 길이 항목들을 한 버퍼에 이어 붙일 때 각 항목의 시작 오프셋을 구하는 용도로 자주 쓰입니다. 크기가 {3, 5, 2}인 항목이라면 결과 {0, 3, 8}이 바로 각 항목이 들어갈 위치입니다.
누적 합에서 흔히 놓치는 것은 중간값의 타입입니다. partial_sum은 초기값 인자가 없어 입력 원소 타입으로 누적하므로, int 배열의 누적 합이 21억을 넘으면 결과 벡터를 long long으로 만들어도 이미 int에서 오버플로가 일어난 값이 들어갑니다. inclusive_scan은 초기값을 받는 오버로드(inclusive_scan(first, last, out, std::plus<>(), 0LL))가 있어 누적 타입을 넓힐 수 있습니다. 누적 합 배열은 “구간 [l, r]의 합 = prefix[r] − prefix[l−1]“로 구간 합을 O(1)에 구하는 코딩 테스트의 기본 도구이기도 합니다.
adjacent_difference - 인접 차이
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 3, 6, 10, 15};
std::vector<int> result(v.size());
// 인접 차이: [v[0], v[1]-v[0], v[2]-v[1], ...]
std::adjacent_difference(v.begin(), v.end(), result.begin());
for (int x : result) {
std::cout << x << " "; // 1 2 3 4 5
}
return 0;
}iota - 순차 값 생성
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v(10);
// 1부터 순차 생성
std::iota(v.begin(), v.end(), 1);
for (int x : v) {
std::cout << x << " "; // 1 2 3 4 5 6 7 8 9 10
}
return 0;
}고급 활용
병렬 실행 정책
실행 정책:
| 정책 | 설명 | 사용 시나리오 |
|---|---|---|
| seq | 순차 실행 | 기본 (순서 보장) |
| par | 병렬 실행 | 멀티코어 활용 |
| par_unseq | 병렬 + 벡터화 | SIMD 최적화 |
벤치마크
#include <numeric>
#include <vector>
#include <execution>
#include <chrono>
#include <iostream>
int main() {
std::vector<int> v(10000000, 1);
auto start = std::chrono::high_resolution_clock::now();
// 순차
auto sum1 = std::reduce(v.begin(), v.end(), 0);
auto mid = std::chrono::high_resolution_clock::now();
// 병렬
auto sum2 = std::reduce(std::execution::par, v.begin(), v.end(), 0);
auto end = std::chrono::high_resolution_clock::now();
auto seq_time = std::chrono::duration_cast<std::chrono::milliseconds>(mid - start).count();
auto par_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - mid).count();
std::cout << "순차: " << seq_time << "ms" << std::endl;
std::cout << "병렬: " << par_time << "ms" << std::endl;
std::cout << "배속: " << (double)seq_time / par_time << "x" << std::endl;
return 0;
}이 측정 코드는 결과를 참고할 때 주의할 점이 있습니다. 1천만 개 정수 합계는 순차로도 몇 밀리초면 끝나서 par_time이 0ms로 나오면 배속이 inf가 되고, 첫 번째 측정은 벡터 메모리를 처음 캐시로 끌어오는 비용까지 포함해 불리합니다. 반복 측정해 평균을 내고, sum1, sum2를 출력해 컴파일러가 계산을 없애지 않게 하는 것이 좋습니다. 병렬 정책의 비용은 스레드 풀을 깨우고 구간을 나누는 고정 비용이라, 원소가 수만 개 이하인 작은 입력에서는 순차보다 느린 경우가 많습니다.
transform_reduce 고급 패턴
가중 평균
#include <numeric>
#include <vector>
#include <execution>
double weighted_average(const std::vector<double>& values,
const std::vector<double>& weights) {
double sum = std::transform_reduce(
std::execution::par,
values.begin(), values.end(),
weights.begin(),
0.0
);
double weight_sum = std::reduce(
std::execution::par,
weights.begin(), weights.end(),
0.0
);
return sum / weight_sum;
}
int main() {
std::vector<double> values = {85, 90, 78, 92};
std::vector<double> weights = {0.3, 0.3, 0.2, 0.2};
double avg = weighted_average(values, weights);
std::cout << "가중 평균: " << avg << std::endl; // 86.5 (25.5 + 27 + 15.6 + 18.4)
return 0;
}범위 기반 누적 (C++20 Ranges)
#include <algorithm>
#include <numeric>
#include <vector>
#include <ranges>
#include <functional>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
auto evens = v | std::views::filter([](int x) { return x % 2 == 0; });
// C++20: accumulate는 범위를 직접 받지 않으므로 begin/end로 넘김
int sum = std::accumulate(evens.begin(), evens.end(), 0);
// C++23: 범위를 직접 받는 접기 알고리즘
// int sum23 = std::ranges::fold_left(evens, 0, std::plus<>());
std::cout << "짝수 합: " << sum << std::endl; // 6 (2+4)
return 0;
}<numeric>의 알고리즘들은 C++20 Ranges 개편에서 범위 버전이 만들어지지 않았습니다. 그래서 std::accumulate(v | views::filter(...), 0)처럼 범위를 한 번에 넘기면 no matching function for call to 'accumulate' 에러가 나고, 위처럼 뷰의 begin()/end()를 넘겨야 합니다. C++23에서 범위를 직접 받는 std::ranges::fold_left가 추가되어 이 불편이 해소되었고, 빈 범위를 허용하지 않는 대신 초기값이 필요 없는 fold_left_first도 함께 들어왔습니다. 뷰를 accumulate에 넘길 때는 filter 뷰의 begin()이 첫 호출 결과를 캐시하기 위해 뷰를 수정하므로, const로 선언한 뷰에서는 begin()을 호출할 수 없다는 점도 알아 둘 만합니다.
성능 비교
accumulate vs reduce: 어디서 차이가 나는가
테스트 대상: 1천만 개 정수 합계 (위 벤치마크 코드)
| 알고리즘 | 실행 정책 | 예상되는 경향 |
|---|---|---|
| accumulate | - | 기준. 왼쪽부터 순서대로 더하므로 병렬화·재배열 불가 |
| reduce | seq | accumulate와 거의 같음 |
| reduce | par | 코어 수만큼 구간을 나눠 더한 뒤 합침. 스레드 시작 비용 때문에 작은 입력에서는 오히려 느릴 수 있음 |
| reduce | par_unseq | 각 스레드 안에서 SIMD 벡터화까지 허용 |
정수 합계처럼 연산이 가벼운 작업은 곧 메모리 대역폭이 병목이 되기 때문에, 코어가 8개라도 8배까지 빨라지지는 않습니다. 또 GCC(libstdc++)에서 std::execution::par는 Intel TBB를 링크해야(-ltbb) 실제로 병렬로 동작하고, 그렇지 않으면 순차 실행과 비슷한 결과가 나옵니다. 배수는 CPU·컴파일러·최적화 옵션에 따라 크게 달라지므로 위 코드를 -O2 이상으로 빌드해 자기 환경에서 직접 재 보는 것이 가장 정확합니다.
메모리 사용량
| 알고리즘 | 추가 메모리 | 비고 |
|---|---|---|
| accumulate | O(1) | In-place |
| reduce | O(1) | In-place |
| partial_sum | O(n) | 출력 버퍼 |
| inclusive_scan | O(n) | 출력 버퍼 |
실무 사례
사례 1: 통계 계산 - 평균, 분산, 표준편차
#include <numeric>
#include <vector>
#include <cmath>
#include <execution>
#include <iostream>
class Statistics {
public:
static double mean(const std::vector<double>& data) {
if (data.empty()) return 0.0;
double sum = std::reduce(
std::execution::par,
data.begin(), data.end(),
0.0
);
return sum / data.size();
}
static double variance(const std::vector<double>& data) {
if (data.size() < 2) return 0.0;
double avg = mean(data);
double sum_sq_diff = std::transform_reduce(
std::execution::par,
data.begin(), data.end(),
0.0,
std::plus<>(),
[avg](double x) {
double diff = x - avg;
return diff * diff;
}
);
return sum_sq_diff / (data.size() - 1);
}
static double stddev(const std::vector<double>& data) {
return std::sqrt(variance(data));
}
};
int main() {
std::vector<double> scores = {85, 90, 78, 92, 88, 76, 95};
std::cout << "평균: " << Statistics::mean(scores) << std::endl;
std::cout << "분산: " << Statistics::variance(scores) << std::endl;
std::cout << "표준편차: " << Statistics::stddev(scores) << std::endl;
return 0;
}분산을 n이 아니라 n − 1로 나누는 것은 표본 분산(불편 추정량)이기 때문입니다. 전체 모집단의 분산을 구한다면 n으로 나눠야 하므로, 엑셀의 VAR.S와 VAR.P, NumPy의 ddof 인자처럼 어느 쪽인지 명시해 두지 않으면 다른 시스템과 결과가 맞지 않습니다. 이 구현은 평균을 먼저 구하고 다시 편차를 구하는 두 번 훑기 방식인데, Σx²/n − 평균²로 한 번에 계산하는 공식은 값이 크고 분산이 작을 때 큰 두 수의 뺄셈에서 정밀도가 크게 떨어지므로 피하는 것이 좋습니다. 데이터를 한 번만 읽어야 하는 스트리밍 상황이라면 Welford 알고리즘이 정밀도와 단일 패스를 모두 만족합니다. 이 정도 크기의 데이터에 par 정책을 쓰는 것은 병렬화 비용이 더 크므로, 예제의 실행 정책은 대용량일 때를 가정한 것입니다.
사례 2: 금융 계산 - 복리 이자
#include <numeric>
#include <vector>
#include <cmath>
double compound_interest(double principal, double rate, int years) {
std::vector<double> rates(years, 1.0 + rate);
// 복리: principal * (1+rate)^years
double multiplier = std::accumulate(
rates.begin(), rates.end(),
1.0,
std::multiplies<>()
);
return principal * multiplier;
}
int main() {
double principal = 1000000; // 100만원
double rate = 0.05; // 5% 연이율
int years = 10;
double result = compound_interest(principal, rate, years);
std::cout << "10년 후: " << result << "원" << std::endl;
// 약 1,628,895원
return 0;
}사례 3: 데이터 분석 - 이동 평균
#include <numeric>
#include <vector>
#include <deque>
#include <iostream>
std::vector<double> moving_average(const std::vector<double>& data, size_t window) {
std::vector<double> result;
std::deque<double> window_data;
double sum = 0.0;
for (size_t i = 0; i < data.size(); ++i) {
window_data.push_back(data[i]);
sum += data[i];
if (window_data.size() > window) {
sum -= window_data.front();
window_data.pop_front();
}
if (window_data.size() == window) {
result.push_back(sum / window);
}
}
return result;
}
int main() {
std::vector<double> prices = {100, 102, 101, 105, 103, 107, 110};
auto ma = moving_average(prices, 3);
std::cout << "3일 이동 평균: ";
for (double avg : ma) {
std::cout << avg << " ";
}
// 101 102.67 103 105 106.67
return 0;
}트러블슈팅
문제 1: 초기값 타입 불일치
증상: 컴파일 오류 또는 잘못된 결과
std::vector<double> v = {1.5, 2.5, 3.5};
// ❌ 잘못된 초기값 타입: 매 단계 int로 잘림 (0+1.5→1, 1+2.5→3, 3+3.5→6)
double sum = std::accumulate(v.begin(), v.end(), 0); // 6 (기대값 7.5)
// ✅ 올바른 초기값
double sum = std::accumulate(v.begin(), v.end(), 0.0); // 7.5문제 2: 오버플로우
증상: 큰 수의 합계가 음수로 나옴
std::vector<int> v = {1000000000, 1000000000, 1000000000};
// ❌ int 오버플로우 (부호 있는 정수 오버플로는 미정의 동작, 흔히 음수로 보임)
int sum = std::accumulate(v.begin(), v.end(), 0);
// 결과 예: -1294967296
// ✅ long long 사용
long long sum = std::accumulate(v.begin(), v.end(), 0LL);
// 결과: 3000000000결과를 long long 변수에 받아도 초기값이 0(int)이면 소용이 없다는 점이 핵심입니다. 누적은 int로 끝난 뒤에 long long으로 변환되므로 이미 넘친 값이 들어갑니다. 초기값을 0LL로 줘야 누적 자체가 long long으로 일어납니다. 부호 있는 정수 오버플로는 미정의 동작이라 최적화된 빌드에서는 “음수가 된다”는 예측조차 보장되지 않으며, -fsanitize=undefined로 빌드하면 signed integer overflow 런타임 에러로 잡을 수 있습니다.
문제 3: 부동소수점 정밀도
증상: reduce와 accumulate 결과가 다름
std::vector<double> v = {0.1, 0.2, 0.3, 0.4, 0.5};
// accumulate: 순서 보장
double sum1 = std::accumulate(v.begin(), v.end(), 0.0);
// reduce: 순서 보장 안 됨
double sum2 = std::reduce(v.begin(), v.end(), 0.0);
// 미세한 차이 발생 가능해결: 순서가 중요하면 accumulate 사용
순서를 고정하는 것은 재현성을 줄 뿐 정확도를 높여 주지는 않습니다. 크기가 매우 다른 수를 순서대로 더하면 작은 값이 큰 누적값에 묻혀 사라지는 문제는 accumulate에서도 그대로 일어납니다. 예를 들어 1e16에 1.0을 천만 번 더해도 결과는 여전히 1e16입니다. 정밀도가 중요한 합계라면 누적 오차를 따로 보정하는 카한(Kahan) 합산을 쓰거나, 값을 크기 순으로 정렬해 작은 것부터 더하는 방법이 있습니다. 금액처럼 오차가 허용되지 않는 값은 처음부터 double 대신 정수(원 단위, 센트 단위)로 저장하는 것이 원칙입니다.
문제 4: 병렬 실행 데이터 경합
증상: 병렬 실행 시 잘못된 결과
int counter = 0;
// ❌ 데이터 경합
std::for_each(std::execution::par, v.begin(), v.end(),
[&counter](int x) { counter += x; }); // 경합!
// ✅ reduce 사용
int sum = std::reduce(std::execution::par, v.begin(), v.end(), 0);마무리
C++ <numeric> 헤더는 수치 연산을 표준 라이브러리로 간결하게 표현할 수 있게 합니다.
핵심 요약
- 집계
accumulate: 순차 집계 (순서 보장)reduce: 병렬 집계 (순서 비보장)transform_reduce: 변환 후 집계
- 누적
partial_sum: 누적 합 (순차)inclusive_scan: 누적 합 (병렬, 현재 포함)exclusive_scan: 누적 합 (병렬, 현재 제외)
- 기타
inner_product: 내적adjacent_difference: 인접 차이iota: 순차 값 생성
선택 가이드
| 상황 | 알고리즘 |
|---|---|
| 순차 합계 | accumulate |
| 병렬 합계 | reduce (par) |
| 내적 | inner_product 또는 transform_reduce |
| 누적 합 | partial_sum 또는 inclusive_scan |
| 순차 생성 | iota |
코드 예제 치트시트
// 합계
int sum = std::accumulate(v.begin(), v.end(), 0);
// 곱
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<>());
// 병렬 합계
int sum = std::reduce(std::execution::par, v.begin(), v.end(), 0);
// 내적
int dot = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
// 누적 합
std::partial_sum(v.begin(), v.end(), result.begin());
// 순차 생성
std::iota(v.begin(), v.end(), 1);다음 단계
- 알고리즘 가이드: C++ STL 알고리즘 기초
- 생성 알고리즘: C++ Algorithm Generate
- 힙 알고리즘: C++ Algorithm Heap
참고 자료
- cppreference: https://en.cppreference.com/w/cpp/algorithm
- “C++17 The Complete Guide” - Nicolai M. Josuttis
- “Effective STL” - Scott Meyers
한 줄 정리: 수치 연산은 <numeric> 알고리즘으로 간결하게 표현하며, 대용량 데이터는 병렬 실행 정책으로 최적화합니다.
자주 묻는 질문 (FAQ)
Q. double 값을 기대했는데 std::accumulate 결과가 정수로 잘리는 이유는 무엇인가요?
A. std::accumulate는 세 번째 인자로 넘긴 초기값의 타입으로 누적을 진행합니다. accumulate(v.begin(), v.end(), 0)처럼 초기값을 0으로 주면 합계가 int로 계산되어, 원소가 double이어도 매 단계 int로 변환되며 소수점이 사라집니다. 초기값을 0.0이나 필요한 타입의 값으로 명시해야 하고, 정수 합이 커질 수 있다면 0LL처럼 넓은 타입을 주어 오버플로도 함께 피해야 합니다.
같이 보면 좋은 글
- C++ std::async와 launch 정책
- C++17 병렬 알고리즘: std::execution::par·par_unseq로 sort·transform·reduce 병렬화할 때 주의점
- C++17 실행 정책 seq·par·par_unseq: 병렬 알고리즘과 데이터 레이스 함정