C++ 标准库 numeric

作者likuolei

以下对 C++ 标准库中 <numeric> 头文件所提供的数值算法与工具做一次系统、深入的梳理，包括算法功能、示例代码、复杂度分析及实践建议。

一、概述

  • <numeric> 中定义了一组对数值序列进行累加、内积、差分、扫描等操作的算法，以及部分辅助工具（如 std::iota、std::gcd/std::lcm 等）。
  • 所有算法均作用于迭代器区间，符合 STL 风格，可与任意容器或原始数组配合使用。
  • 从 C++17、20 起，又陆续加入了并行友好的 std::reduce、std::inclusive_scan、std::exclusive_scan、std::transform_reduce 等新算法。

二、核心算法

1. std::accumulate

  • 功能：对区间 [first, last) 内所有元素做累加（或自定义二元操作），并将初值 init 加入计算。
  • 原型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);
  • 默认行为：init + *first + *next + …；自定义时执行 op(op(init, *first), *next)…。
  • 时间复杂度：O(N)
#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);
    // 计算阶乘之和
    int fact_sum = std::accumulate(v.begin(), v.end(), 1, [](int a, int b){ return a * b; });
    std::cout << sum << ", " << fact_sum;  // 输出 15, 120
}

2. std::inner_product

  • 功能：计算两序列点积，并加上初值 init。
  • 原型template<class InputIt1, class InputIt2, class T> T inner_product(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init); template<class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2> T inner_product(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init, BinaryOp1 op_sum, BinaryOp2 op_mul);
  • 默认行为：init + Σ (a[i] * b[i])
  • 时间复杂度：O(N)
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> a{1,2,3}, b{4,5,6};
    int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0);
    std::cout << dot;  // 输出 32
}

3. std::partial_sum

  • 功能：对区间进行前缀累加，生成与原区间等长的结果序列。
  • 原型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);
  • 默认行为：输出 [a[0], a[0]+a[1], a[0]+a[1]+a[2], …]；可用自定义 op 替换 +。
  • 时间复杂度：O(N)
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v{1,2,3,4};
    std::vector<int> out(v.size());
    std::partial_sum(v.begin(), v.end(), out.begin());
    // out = {1,3,6,10}
    for (int x : out) std::cout << x << ' ';
}

4. std::adjacent_difference

  • 功能：计算相邻元素差分，同样生成等长序列。
  • 原型template<class InputIt, class OutputIt> OutputIt adjacent_difference(InputIt first, InputIt last, OutputIt d_first); template<class InputIt, class OutputIt, class BinaryOp> OutputIt adjacent_difference(InputIt first, InputIt last, OutputIt d_first, BinaryOp op);
  • 默认行为：输出 [a[0], a[1]−a[0], a[2]−a[1], …]；自定义 op 替换减法。
  • 时间复杂度：O(N)
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v{1,3,6,10};
    std::vector<int> diff(v.size());
    std::adjacent_difference(v.begin(), v.end(), diff.begin());
    // diff = {1,2,3,4}
    for (int x : diff) std::cout << x << ' ';
}

5. std::iota

  • 功能：按等差序列填充区间。
  • 原型template<class ForwardIt, class T> void iota(ForwardIt first, ForwardIt last, T value);
  • 行为：*first = value; *(first+1) = value+1; …。
  • 时间复杂度：O(N)
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v(5);
    std::iota(v.begin(), v.end(), 10);
    // v = {10,11,12,13,14}
    for (int x : v) std::cout << x << ' ';
}

6. std::gcd 与 std::lcm（C++17 起）

  • 功能：分别计算两个整数的最大公约数和最小公倍数。
  • 原型template<class M, class N> constexpr std::common_type_t<M,N> gcd(M m, N n); template<class M, class N> constexpr std::common_type_t<M,N> lcm(M m, N n);
  • 复杂度：基于欧几里得算法，O(log⁡min⁡(m,n))。
#include <numeric>
#include <iostream>

int main() {
    std::cout << std::gcd(48, 18) << ' ';  // 输出 6
    std::cout << std::lcm(48, 18);         // 输出 144
}

三、C++17/20 新增并行与扫描算法

从 C++17 起，<numeric> 中加入更高效且可并行化的算法。

算法功能
std::reduce类似 accumulate，但可并行优化，无序二元操作要满足交换结合性
std::inclusive_scan包含当前元素的前缀扫描（即 partial_sum 的并行版）
std::exclusive_scan不包含当前元素的前缀扫描
std::transform_reduce先对每个元素做一元转换，再并行归约
std::transform_scan先转换后扫描
  • 原型举例// inclusive_scan template<class InputIt, class OutputIt, class BinaryOp> OutputIt inclusive_scan(InputIt first, InputIt last, OutputIt d_first, BinaryOp op); // reduce template<class InputIt, class T> T reduce(InputIt first, InputIt last, T init);
  • 并行执行策略：可传入执行策略（std::execution::seq、par、par_unseq）以启用多线程或向量化。
#include <numeric>
#include <vector>
#include <execution>
#include <iostream>

int main() {
    std::vector<int> v(1'000'000, 1);
    // 并行归约
    long sum = std::reduce(std::execution::par, v.begin(), v.end(), 0L);
    std::cout << sum;
}

四、实践建议

  1. 小序列优先用 accumulate，大规模数据考虑 reduce
    • accumulate 简单、易读；reduce 在结合律满足时能获得并行加速。
  2. 前缀和与差分模式
    • partial_sum/inclusive_scan 可快速构建前缀和用于区间查询；
    • adjacent_difference 在信号处理、数值微分等场景非常高效。
  3. 避免整数溢出
    • 累加大量元素或大值时，选择合适的初值类型（如 long long、double）。
  4. 选择合适的操作符重载
    • 自定义 BinaryOp 时，要保证满足需要的结合性、幂等性等特性，以免并行时结果不确定。
  5. 利用 iota 快速生成测试数据
    • 在调试或测试中，std::iota 可快速构造等差、递增序列。

通过以上对 <numeric> 中各类数值算法的全面详解，相信你能在科学计算、信号处理、统计分析乃至日常开发中高效地利用标准库功能，写出简洁且高性能的代码。祝学习顺利！

类似文章

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注