Numeric Algorithms — accumulate, inner_product, partial_sum, iota, reduce

Q: What is the associativity requirement for reduce?

The binary operation must be associative: op(a, op(b, c)) == op(op(a, b), c). Addition and multiplication are associative; subtraction and division are not.

Q: What is `exclusive_scan` vs `inclusive_scan`?

Inclusive scan includes the current element: {1, 1+2=3, 1+2+3=6}. Exclusive scan starts with identity: {0, 1, 1+2=3}.

Q: Is `iota` named after the Greek letter?

Yes. The name comes from APL's ⍳ (iota) function that generates an array of incrementing integers.

Q: Can I use `reduce` with std::string?

Yes, but parallel execution requires thread-safe operations. String concatenation is not commutative, so avoid parallel reduce with strings.

DodaTech Updated 2026-06-28 8 min read

In this tutorial, you will learn about Numeric Algorithms. We cover key concepts, practical examples, and best practices to help you master this topic.

C++ numeric algorithms in include accumulate (fold), inner_product (dot product), partial_sum (prefix scan), adjacent_difference, iota (increment fill), and C++17 parallel reduce variants.

What You'll Learn

You will sum and fold ranges with std::accumulate, compute dot products with std::inner_product, generate prefix sums with std::partial_sum, compute differences with std::adjacent_difference, fill sequences with std::iota, and use parallel execution policies with std::reduce and std::transform_reduce for multi-threaded performance.

Why It Matters

Numeric algorithms Express common mathematical operations compactly. accumulate replaces manual sum loops. inner_product replaces nested dot product loops. The parallel versions (C++17) leverage multi-core CPUs with minimal code changes. These algorithms are building blocks for Data Science, Machine Learning, and scientific computing.

Learning Path

graph LR
    A["38: Modifying Algorithms"] --> B["39: Numeric Algorithms"]
    B --> C["40: Ranges Library"]
    C --> D["41: Iterator Types"]
    style A fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style B fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style C fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style D fill:#4a90d9,stroke:#2c5f8a,color:#fff

`std::accumulate`

#include <iostream>
#include <vector>
#include <numeric>
#include <string>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // Sum (default: addition)
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Sum: " << sum << "\n";  // 15
    
    // Product (using custom operation)
    int product = std::accumulate(v.begin(), v.end(), 1,
                                  std::multiplies<int>());
    std::cout << "Product: " << product << "\n";  // 120
    
    // String concatenation
    std::vector<std::string> words = {"Hello", " ", "World", "!"};
    std::string concat = std::accumulate(words.begin(), words.end(),
                                         std::string());
    std::cout << concat << "\n";
    
    // Custom fold
    auto result = std::accumulate(v.begin(), v.end(), std::pair<int,int>{0,0},
                        [](auto acc, int x) {
                            return std::pair{acc.first + x, acc.second + x * x};
                        });
    std::cout << "Sum: " << result.first << ", Sum of squares: "
              << result.second << "\n";
}

`std::inner_product`

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<double> a = {1.0, 2.0, 3.0};
    std::vector<double> b = {4.0, 5.0, 6.0};
    
    // Dot product: (1*4) + (2*5) + (3*6) = 4 + 10 + 18 = 32
    double dot = std::inner_product(a.begin(), a.end(), b.begin(), 0.0);
    std::cout << "Dot product: " << dot << "\n";
    
    // Custom version: sum of absolute differences
    auto sumAbsDiff = std::inner_product(
        a.begin(), a.end(), b.begin(), 0.0,
        std::plus<>(),                                // combine
        [](double x, double y) { return std::abs(x - y); }  // per-element
    );
    std::cout << "Sum of abs diffs: " << sumAbsDiff << "\n";  // |1-4| + |2-5| + |3-6| = 9
    
    // Euclidean distance
    auto sumSq = std::inner_product(a.begin(), a.end(), b.begin(), 0.0,
        std::plus<>(),
        [](double x, double y) {
            double diff = x - y;
            return diff * diff;
        });
    double euclidean = std::sqrt(sumSq);
    std::cout << "Euclidean distance: " << euclidean << "\n";
}

`std::partial_sum`

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> prefix(v.size());
    
    // Prefix sums: 1, 1+2=3, 1+2+3=6, 1+2+3+4=10, 1+2+3+4+5=15
    std::partial_sum(v.begin(), v.end(), prefix.begin());
    for (int x : prefix) std::cout << x << " ";
    std::cout << "\n";  // 1 3 6 10 15
    
    // Running product
    std::vector<int> runningProduct;
    std::partial_sum(v.begin(), v.end(),
                     std::back_inserter(runningProduct),
                     std::multiplies<int>());
    // 1, 2, 6, 24, 120
    
    // Inclusive vs exclusive scan
    // Exclusive scan: first element is identity (0), then partial sums
    std::vector<int> exclusive(6);
    // partial_sum is always inclusive
    // For exclusive, use 0 + cumulative sums shifted
    std::partial_sum(v.begin(), v.end(), exclusive.begin() + 1);
    exclusive[0] = 0;
    // 0, 1, 3, 6, 10, 15
}

`std::adjacent_difference`

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> v = {1, 3, 6, 10, 15};
    std::vector<int> diff(v.size());
    
    // Differences: 1, 3-1=2, 6-3=3, 10-6=4, 15-10=5
    std::adjacent_difference(v.begin(), v.end(), diff.begin());
    for (int x : diff) std::cout << x << " ";
    std::cout << "\n";  // 1 2 3 4 5
    
    // Reconstruct original from differences
    std::vector<int> reconstructed;
    std::partial_sum(diff.begin(), diff.end(),
                     std::back_inserter(reconstructed));
    for (int x : reconstructed) std::cout << x << " ";
    std::cout << "\n";  // 1 3 6 10 15
    
    // Custom operation
    std::vector<int> ratios;
    std::adjacent_difference(v.begin(), v.end(),
                             std::back_inserter(ratios),
                             [](int a, int b) { return a * 1.0 / b; });
}

`std::iota`

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> v(10);
    
    // Fill with 0, 1, 2, 3, ...
    std::iota(v.begin(), v.end(), 0);
    
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 0 1 2 3 4 5 6 7 8 9
    
    // With different starting value
    std::iota(v.begin(), v.end(), 100);
    // 100 101 102 ...
    
    // Generate indices matching another container
    std::vector<double> scores = {95.5, 82.3, 91.0, 78.6};
    std::vector<int> indices(scores.size());
    std::iota(indices.begin(), indices.end(), 0);
    
    // Sort indices by scores (argsort pattern)
    std::sort(indices.begin(), indices.end(),
              [&](int a, int b) { return scores[a] > scores[b]; });
    
    std::cout << "Rankings:\n";
    for (int i : indices) {
        std::cout << "  #" << (i + 1) << ": " << scores[i] << "\n";
    }
}

Parallel Execution Policies (C++17)

#include <iostream>
#include <vector>
#include <numeric>
#include <execution>
#include <chrono>

int main() {
    std::vector<double> v(100000000);
    std::iota(v.begin(), v.end(), 1.0);
    
    auto start = std::chrono::high_resolution_clock::now();
    
    // Sequential
    double sum1 = std::accumulate(v.begin(), v.end(), 0.0);
    
    // Parallel (C++17)
    double sum2 = std::reduce(std::execution::par, v.begin(), v.end(), 0.0);
    
    // Parallel with transform (reduce is a fold)
    double sumSq = std::transform_reduce(
        std::execution::par,
        v.begin(), v.end(), 0.0, std::plus<>(),
        [](double x) { return x * x; }
    );
    
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration<double, std::milli>(end - start).count();
    
    std::cout << "Sum (seq): " << sum1 << "\n";
    std::cout << "Sum (par): " << sum2 << "\n";
    std::cout << "Sum of squares: " << sumSq << "\n";
    std::cout << "Time: " << ms << " ms\n";
}

Comparison: `accumulate` vs `reduce`

Algorithm	Execution	Associativity	Order
`accumulate`	Sequential only	Left fold	Left-to-right
`reduce`	Parallelizable	Any order	Non-deterministic
`transform_reduce`	Parallelizable	Any order	Non-deterministic

Use accumulate when you need a specific order. Use reduce and transform_reduce for performance on large arrays.

Common Mistakes

Mistake 1: Forgetting the Initial Value

std::accumulate(v.begin(), v.end());  // Error: needs 3 arguments

Mistake 2: Wrong Type for Initial Value

std::vector<double> v = {1.1, 2.2, 3.3};
int sum = std::accumulate(v.begin(), v.end(), 0);  // truncates to 6!

Use 0.0 for double accumulation.

Mistake 3: Using `reduce` with Non-Associative Operations

std::vector<double> v = {1, 2, 3};
double avg = std::reduce(std::execution::par, v.begin(), v.end(), 0.0)
             / v.size();  // correct
// But not:
double result = std::reduce(..., [](double a, double b) { return a - b; });
// Subtraction is not associative!

Mistake 4: Forgetting that `iota` Increases by 1

std::iota fills with incrementing values. If you need a custom pattern, use std::generate.

Mistake 5: Using `partial_sum` for Non-Associative Operations

Like accumulate, partial_sum evaluates left-to-right. Custom operations must be associative for correct parallel prefix sums.

Mistake 6: Modifying Input During Reduce

std::reduce may read elements multiple times. Do not modify the range during reduction.

Practice Questions

What is the difference between accumulate and reduce?
How do you compute the product of all elements in a vector?
Write an argsort function using iota and sort.
What does std::partial_sum with std::multiplies produce?
How would you compute the variance of a dataset using numeric algorithms?

Challenge

Compute the standard deviation of a large dataset (>10M elements) using transform_reduce with parallel execution. Compare the performance with a sequential accumulate implementation.

FAQ

Why does `accumulate` need an initial value?

The initial value determines the result type and handles empty ranges. Without it, accumulate on an empty range would be undefined.

Is `std::reduce` always faster than `std::accumulate`?

Yes for large datasets with multi-core CPUs. But there is overhead for thread creation. For small ranges (< 1000 elements), accumulate is faster.

What is the associativity requirement for reduce?

The binary operation must be associative: op(a, op(b, c)) == op(op(a, b), c). Addition and multiplication are associative; subtraction and division are not.

What is `exclusive_scan` vs `inclusive_scan`?

Inclusive scan includes the current element: {1, 1+2=3, 1+2+3=6}. Exclusive scan starts with identity: {0, 1, 1+2=3}.

Is `iota` named after the Greek letter?

Yes. The name comes from APL's ⍳ (iota) function that generates an array of incrementing integers.

Can I use `reduce` with std::string?

Yes, but parallel execution requires thread-safe operations. String concatenation is not commutative, so avoid parallel reduce with strings.

Mini Project

Build a statistics calculator:

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <execution>

class Statistics {
private:
    std::vector<double> data_;
    
public:
    Statistics(const std::vector<double>& data) : data_(data) {}
    
    double min() const {
        return *std::min_element(data_.begin(), data_.end());
    }
    
    double max() const {
        return *std::max_element(data_.begin(), data_.end());
    }
    
    double mean() const {
        return std::accumulate(data_.begin(), data_.end(), 0.0) / data_.size();
    }
    
    double variance() const {
        double m = mean();
        double sumSqDiff = std::transform_reduce(
            std::execution::par,
            data_.begin(), data_.end(), 0.0, std::plus<>(),
            [m](double x) { return (x - m) * (x - m); }
        );
        return sumSqDiff / data_.size();
    }
    
    double stddev() const {
        return std::sqrt(variance());
    }
    
    double median() const {
        auto copy = data_;
        auto mid = copy.begin() + copy.size() / 2;
        std::nth_element(copy.begin(), mid, copy.end());
        return *mid;
    }
};

int main() {
    std::vector<double> data = {2.5, 3.7, 1.8, 4.2, 3.1, 5.0, 2.9, 3.3};
    
    Stats stats(data);
    std::cout << "Statistics:\n";
    std::cout << "  Min: " << stats.min() << "\n";
    std::cout << "  Max: " << stats.max() << "\n";
    std::cout << "  Mean: " << stats.mean() << "\n";
    std::cout << "  Variance: " << stats.variance() << "\n";
    std::cout << "  StdDev: " << stats.stddev() << "\n";
    std::cout << "  Median: " << stats.median() << "\n";
}

What's Next

Numeric algorithms handle mathematical computation. The next lesson covers the ranges library (C++20): composable views, pipe operators, lazy evaluation, and range adaptors.

← Previous Modifying Algorithms — copy, move, transform, replace, Erase-Remove Idiom Next → Ranges Library — std::ranges, Views, Pipe Operator, Range Adaptors

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Cpp