C++ Numeric Algorithms Complete Guide | accumulate· reduce

Introduction

C++ <numeric> header provides numeric algorithms specialized for mathematical operations. Sum, product, inner product, prefix sums can be expressed concisely with standard library, and C++17 adds parallel execution policies for massive performance gains on large datasets.

What You’ll Learn

• Understand differences between accumulate, reduce, transform_reduce
• Implement prefix sums with partial_sum, inclusive_scan, exclusive_scan
• Optimize performance with parallel execution policies
• Apply common production patterns

---

Table of Contents

1. Basic Algorithms
2. Practical Implementation
3. Advanced Usage
4. Performance Comparison
5. Production Use Cases
6. Troubleshooting
7. Summary

---

Basic Algorithms

Algorithm List

Algorithm	Purpose	C++ Version
accumulate	Range aggregation (sequential)	C++98
reduce	Range aggregation (parallel-capable)	C++17
transform_reduce	Transform then aggregate	C++17
inner_product	Dot product	C++98
partial_sum	Prefix sum	C++98
inclusive_scan	Prefix sum (parallel)	C++17
exclusive_scan	Prefix sum (exclude current)	C++17
adjacent_difference	Adjacent differences	C++98
iota	Sequential value generation	C++11

---

Practical Implementation

1. accumulate - Range Aggregation

Signature:

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);

Basic Usage

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // Sum
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Sum: " << sum << std::endl;  // 15
    
    // Product
    int product = std::accumulate(v.begin(), v.end(), 1, 
        [](int a, int b) { return a * b; });
    std::cout << "Product: " << product << std::endl;  // 120
    
    return 0;
}

Output:

Sum: 15
Product: 120

Custom Operations

#include <numeric>
#include <vector>
#include <string>
int main() {
    std::vector<std::string> words = {"Hello", " ", "World", "!"};
    
    // String concatenation
    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;
}

Output:

Hello World!

Time complexity: O(n)
Space complexity: O(1)

2. reduce - Parallel Aggregation (C++17)

Signature:

template<class ExecutionPolicy, class ForwardIt, class T>
T reduce(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init);

Basic Usage

#include <numeric>
#include <vector>
#include <execution>
#include <iostream>
int main() {
    std::vector<int> v(1000000, 1);
    
    // Sequential
    auto sum1 = std::reduce(v.begin(), v.end(), 0);
    
    // Parallel
    auto sum2 = std::reduce(std::execution::par, v.begin(), v.end(), 0);
    
    // Parallel + vectorization
    auto sum3 = std::reduce(std::execution::par_unseq, v.begin(), v.end(), 0);
    
    std::cout << "Sum: " << sum2 << std::endl;  // 1000000
    
    return 0;
}

Output:

Sum: 1000000

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: order guaranteed (left-to-right)
    double sum1 = std::accumulate(v.begin(), v.end(), 0.0);
    
    // reduce: order not guaranteed (parallel-capable)
    double sum2 = std::reduce(v.begin(), v.end(), 0.0);
    
    // Floating-point results may differ slightly due to order
    std::cout << "accumulate: " << sum1 << std::endl;
    std::cout << "reduce: " << sum2 << std::endl;
    
    return 0;
}

Output:

accumulate: 15
reduce: 15

Cautions:

• reduce assumes associativity
• Floating-point results may differ based on order
• Parallel execution: watch for data races

---

3. transform_reduce - Transform Then Aggregate (C++17)

Signature:

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};
    
    // Dot product: sum(v1[i] * v2[i])
    int dotProduct = std::transform_reduce(
        std::execution::par,
        v1.begin(), v1.end(),
        v2.begin(),
    );
    
    std::cout << "Dot product: " << dotProduct << std::endl;  // 30
    
    return 0;
}

Output:

Dot product: 30

Sum of Squares

#include <numeric>
#include <vector>
#include <execution>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // Sum of squares: 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 << "Sum of squares: " << sumOfSquares << std::endl;  // 55
    
    return 0;
}

Output:

Sum of squares: 55

Time complexity: O(n)
Space complexity: O(1)

4. inner_product - Dot Product

Signature:

template<class InputIt1, class InputIt2, class T>
T inner_product(InputIt1 first1, InputIt1 last1,
                InputIt2 first2, T init);

Basic Usage

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    
    // Dot product: 1*4 + 2*5 + 3*6 = 32
    int result = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
    
    std::cout << "Dot product: " << result << std::endl;  // 32
    
    return 0;
}

Output:

Dot product: 32

Custom Operations

#include <numeric>
#include <vector>
int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    
    // Product of sums instead of sum of products
    // (1+4) * (2+5) * (3+6) = 5 * 7 * 9 = 315
    int result = std::inner_product(
        v1.begin(), v1.end(), v2.begin(), 1,
        std::multiplies<>(),  // Outer op: multiply
        std::plus<>()         // Inner op: add
    );
    
    std::cout << "Result: " << result << std::endl;  // 315
    
    return 0;
}

Output:

Result: 315

---

5. partial_sum - Prefix Sum

Signature:

template<class InputIt, class OutputIt>
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first);

Basic Usage

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> result(v.size());
    
    // Prefix sum: [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;
}

Output:

1 3 6 10 15

Prefix Product

#include <numeric>
#include <vector>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> result(v.size());
    
    // Prefix product
    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;
}

Output:

1 2 6 24 120

---

6. 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());
    
    // Prefix sum (parallel)
    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;
}

Output:

1 3 6 10 15

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());
    
    // Prefix sum (exclude current element)
    std::exclusive_scan(
        std::execution::par,
        v.begin(), v.end(),
        result.begin(),
        0  // Initial value
    );
    
    for (int x : result) {
        std::cout << x << " ";  // 0 1 3 6 10
    }
    
    return 0;
}

Output:

0 1 3 6 10

Difference:

• inclusive_scan: includes current element
• exclusive_scan: excludes current element

---

7. adjacent_difference - Adjacent Differences

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 3, 6, 10, 15};
    std::vector<int> result(v.size());
    
    // Adjacent differences: [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;
}

Output:

1 2 3 4 5

Use case: Convert prefix sums back to original values.

8. iota - Sequential Value Generation

#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v(10);
    
    // Generate sequence starting from 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;
}

Output:

1 2 3 4 5 6 7 8 9 10

Use case: Initialize index arrays, generate test data.

Advanced Usage

1. Parallel Execution Policies

Execution policies:

Policy	Description	Use Case
seq	Sequential	Default (order guaranteed)
par	Parallel	Multi-core utilization
par_unseq	Parallel + vectorization	SIMD optimization

Benchmark

#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();
    
    // Sequential
    auto sum1 = std::reduce(v.begin(), v.end(), 0);
    
    auto mid = std::chrono::high_resolution_clock::now();
    
    // Parallel
    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 << "Sequential: " << seq_time << "ms" << std::endl;
    std::cout << "Parallel: " << par_time << "ms" << std::endl;
    std::cout << "Speedup: " << (double)seq_time / par_time << "x" << std::endl;
    
    return 0;
}

Typical output:

Sequential: 25ms
Parallel: 8ms
Speedup: 3.1x

2. transform_reduce Advanced Patterns

Weighted Average

#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(),
    );
    
    double weight_sum = std::reduce(
        std::execution::par,
        weights.begin(), weights.end(),
    );
    
    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 << "Weighted average: " << avg << std::endl;  // 86.7
    
    return 0;
}

Output:

Weighted average: 86.7

3. Range-Based Accumulation (C++20 Ranges)

#include <numeric>
#include <vector>
#include <ranges>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // C++20 ranges
    auto filtered = v | std::views::filter([](int x) { return x % 2 == 0; });
    auto sum = std::accumulate(filtered.begin(), filtered.end(), 0);
    
    std::cout << "Even sum: " << sum << std::endl;  // 6 (2+4)
    
    return 0;
}

Output:

Even sum: 6

---

Performance Comparison

accumulate vs reduce Benchmark

Test: Sum of 10 million integers

Algorithm	Execution Policy	Time	Speedup
accumulate	-	25ms	1x
reduce	seq	26ms	1x
reduce	par	8ms	3.1x
reduce	par_unseq	6ms	4.2x
Conclusion: Parallel execution provides 4x improvement

Memory Usage

Algorithm	Additional Memory	Notes
accumulate	O(1)	In-place
reduce	O(1)	In-place
partial_sum	O(n)	Output buffer
inclusive_scan	O(n)	Output buffer

---

Production Use Cases

Use Case 1: Statistics - Mean, Variance, Standard Deviation

#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(),
        );
        
        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 << "Mean: " << Statistics::mean(scores) << std::endl;
    std::cout << "Variance: " << Statistics::variance(scores) << std::endl;
    std::cout << "Std dev: " << Statistics::stddev(scores) << std::endl;
    
    return 0;
}

Output:

Mean: 86.2857
Variance: 51.9048
Std dev: 7.20449

Use Case 2: Finance - Compound Interest

#include <numeric>
#include <vector>
#include <cmath>
double compound_interest(double principal, double rate, int years) {
    std::vector<double> rates(years, 1.0 + rate);
    
    // Compound: principal * (1+rate)^years
    double multiplier = std::accumulate(
        rates.begin(), rates.end(),
        1.0,
        std::multiplies<>()
    );
    
    return principal * multiplier;
}
int main() {
    double principal = 1000000;  // $1M
    double rate = 0.05;          // 5% annual rate
    int years = 10;
    
    double result = compound_interest(principal, rate, years);
    std::cout << "After 10 years: $" << result << std::endl;
    // ~$1,628,895
    
    return 0;
}

Output:

After 10 years: $1.62889e+06

Use Case 3: Data Analysis - Moving Average

#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-day moving average: ";
    for (double avg : ma) {
        std::cout << avg << " ";
    }
    // 101 102.67 103 105 106.67
    
    return 0;
}

Output:

3-day moving average: 101 102.667 103 105 106.667

---

Troubleshooting

Problem 1: Initial Value Type Mismatch

Symptom: Compile error or wrong result

std::vector<int> v = {1, 2, 3, 4, 5};
// ❌ Wrong initial value type
double sum = std::accumulate(v.begin(), v.end(), 0);  // Computed as int
// ✅ Correct initial value
double sum = std::accumulate(v.begin(), v.end(), 0.0);

Problem 2: Overflow

Symptom: Large sum becomes negative

std::vector<int> v = {1000000, 1000000, 1000000};
// ❌ int overflow
int sum = std::accumulate(v.begin(), v.end(), 0);
// Result: -1294967296 (overflow)
// ✅ Use long long
long long sum = std::accumulate(v.begin(), v.end(), 0LL);
// Result: 3000000

Problem 3: Floating-Point Precision

Symptom: reduce and accumulate give different results

std::vector<double> v = {0.1, 0.2, 0.3, 0.4, 0.5};
// accumulate: order guaranteed
double sum1 = std::accumulate(v.begin(), v.end(), 0.0);
// reduce: order not guaranteed
double sum2 = std::reduce(v.begin(), v.end(), 0.0);
// Slight difference may occur

Solution: Use accumulate when order matters for reproducibility.

Problem 4: Parallel Execution Data Race

Symptom: Wrong result with parallel execution

int counter = 0;
// ❌ Data race
std::for_each(std::execution::par, v.begin(), v.end(),
    [&counter](int x) { counter += x; });  // Race!
// ✅ Use reduce
int sum = std::reduce(std::execution::par, v.begin(), v.end(), 0);

---

Summary

C++ <numeric> header enables concise expression of numeric operations with standard library.

Key Points

1. Aggregation
   • accumulate: Sequential (order guaranteed)
   • reduce: Parallel-capable (order not guaranteed)
   • transform_reduce: Transform then aggregate
2. Prefix Sums
   • partial_sum: Sequential prefix sum
   • inclusive_scan: Parallel prefix sum (include current)
   • exclusive_scan: Parallel prefix sum (exclude current)
3. Other
   • inner_product: Dot product
   • adjacent_difference: Adjacent differences
   • iota: Sequential value generation

Selection Guide

Situation	Algorithm
Sequential sum	accumulate
Parallel sum	reduce (par)
Dot product	inner_product or transform_reduce
Prefix sum	partial_sum or inclusive_scan
Sequence generation	iota

Cheat Sheet

// Sum
int sum = std::accumulate(v.begin(), v.end(), 0);
// Product
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<>());
// Parallel sum
int sum = std::reduce(std::execution::par, v.begin(), v.end(), 0);
// Dot product
int dot = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
// Prefix sum
std::partial_sum(v.begin(), v.end(), result.begin());
// Sequence generation
std::iota(v.begin(), v.end(), 1);

Performance Summary

Operation	Sequential	Parallel (4 cores)	Speedup
Sum (10M ints)	25ms	6ms	4.2x
Transform-reduce	35ms	9ms	3.9x
Prefix sum	30ms	12ms	2.5x
Key: Parallel execution provides 2-4x speedup on multi-core systems.

---

Related Articles

• C++ Algorithm Complete Guide
• C++ Algorithm Generate
• C++ Algorithm Heap
• C++ Algorithm Count

Keywords

C++ numeric algorithms, std::accumulate, std::reduce, transform_reduce, partial_sum, inner_product, iota, parallel execution, STL One-line summary: Master C++ algorithms for efficient numeric operations with accumulate, reduce, transform_reduce, prefix sums, and parallel execution policies.

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Master C++ algorithms: std::accumulate vs std::reduce (associativity, parallel policies), transform_reduce.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• C++ Algorithm Generate | ‘생성 알고리즘’ 가이드
• C++ Algorithm Heap | ‘힙 알고리즘’ 가이드
• C++ Algorithm Count | ‘카운트 알고리즘’ 가이드

---

이 글에서 다루는 키워드 (관련 검색어)

C++, Algorithm, numeric, reduce, STL, accumulate, parallel 등으로 검색하시면 이 글이 도움이 됩니다.