Algorithms

C++ 标准库中的算法 (Algorithms) 是一组强大的函数模板，用于对容器或其他范围（[first, last)）内的元素进行搜索、排序、计数、修改等操作。自 C++20 以来，Ranges (约束算法) 的引入极大地简化了算法的使用，并增强了其通用性。C++17 则引入了执行策略，允许算法进行并行或乱序执行以提升性能。

版本速览

算法库的演进大致可以按下面的时间线理解，后文各表格中的「C++ 版本」列标注的就是各个算法首次引入（或 ranges:: 版本首次引入）的标准版本。

C++20 约束算法 (Constrained Algorithms / Ranges)

Ranges 是 C++20 引入的一项革命性特性，它极大地简化了 STL 算法的使用，并增强了它们的组合性。

核心概念与优势

示例:

std::vector<int> v{7, 1, 4, 0, -1};

// 经典算法：需要显式传入begin()和end()
std::sort(v.begin(), v.end());

// C++20 Ranges 算法：更简洁
std::ranges::sort(v);

C++17/C++20 执行策略 (Execution Policies)

执行策略 是 C++17 引入的功能，它允许程序员通过向算法传递一个策略对象，来指示算法如何执行——是串行、并行还是乱序执行，从而在多核 CPU 上实现性能优化。

核心策略类型

头文件： 所有执行策略都定义在 <execution> 头文件中。策略类型位于 std::execution 命名空间（sequenced_policy、parallel_policy、parallel_unsequenced_policy、unsequenced_policy），而全局策略对象 seq、par、par_unseq、unseq 位于 std 命名空间（即 std::execution::par 也可用，两者是同一对象）。

示例:

#include <algorithm>
#include <execution>
#include <vector>

std::vector<int> data = ...;

// 使用并行策略对数据进行排序，以利用多核CPU
std::sort(std::execution::par, data.begin(), data.end());

// C++20 Ranges 版本也支持策略（如果算法有重载）
std::ranges::sort(std::execution::par, data);

并行算法的技术限制

在使用执行策略时，有一个关键的安全限制需要注意：

除另有说明外，只要元素类型 ( T ) 同时满足 Trivial Copy Construction (std::is_trivially_copy_constructible_v<T> == true) 和 Trivial Destruction (std::is_trivially_destructible_v<T> == true)，库就可以对元素进行任意复制，以便在不同的并行线程之间分发数据。

这意味着： 如果你的自定义对象具有非平凡（复杂）的构造函数、析构函数或资源管理，使用并行策略时需要额外小心，以确保你的操作是线程安全的。对于基本类型（如 int, float）和简单的 C 结构体，这通常不是问题。

另外，使用 par_unseq 和 unseq 时，函数调用之间是无序（unsequenced）的，可以交错执行，因此不允许分配/释放内存、获取互斥锁、使用非无锁的 std::atomic，或执行其它“不利于向量化”的操作。

C++26 变更： 从 C++26 开始，std::ranges 下的算法也支持执行策略（并行范围算法）。例如 std::ranges::sort(std::execution::par, v)、std::ranges::copy(std::execution::par, src, dst) 都已可用。在 C++26 之前，ranges:: 算法并不接受执行策略参数。

一、非修改序列操作 (Non-modifying sequence operations)

主要头文件：

• <algorithm>：包含绝大多数经典的非修改序列操作。
• <ranges>：包含所有 ranges:: 版本的算法。

批处理操作 (Batch operations)

搜索操作 (Search operations)

折叠操作 (Fold operations)

注意： 折叠算法没有非 ranges:: 版本，它们只在 <ranges> 中提供。

Ranges 返回类型 (Return types)

std::ranges 算法不再只返回一个迭代器，而是返回下面这些结构体（class template），它们提供了算法执行过程中计算出的全部有用信息。这也是 Ranges 算法与经典算法在接口上的一个重要区别。

二、修改序列操作 (Modifying sequence operations)

主要头文件：

• <algorithm>：包含绝大多数经典的修改序列操作。
• <ranges>：包含所有 ranges:: 版本的算法。
• <utility>：包含 std::swap 和 std::iter_swap。

复制操作 (Copy operations)

交换操作 (Swap operations)

变换操作 (Transformation operations)

生成操作 (Generation operations)

移除操作 (Removing operations)

这里的“移除”通常是逻辑移除，通过将未被移除的元素移动到范围的前部来实现，并返回新的逻辑尾部。

顺序改变操作 (Order-changing operations)

采样操作 (Sampling operations)

三、排序及相关操作 (Sorting and related operations)

主要头文件：

• <algorithm>：包含绝大多数经典的排序及相关操作。
• <ranges>：包含所有 ranges:: 版本的算法。

分区操作 (Partitioning operations)

排序操作 (Sorting operations)

二分搜索操作 (Binary search operations)

这些操作要求输入范围必须是已排序的。

集合操作 (Set operations)

这些操作要求输入范围必须是已排序的。

合并操作 (Merge operations)

堆操作 (Heap operations)

这些操作用于维护最大堆 (max heap) 的属性。

最小/最大操作 (Minimum/maximum operations)

字典序比较操作 (Lexicographical comparison operations)

排列操作 (Permutation operations)

四、数值操作 (Numeric operations)

主要头文件：

• <numeric>：包含所有传统的数值算法和 C++17 的并行数值算法。
• <ranges>：包含 ranges::iota。

注意： 除 ranges::iota 外，数值算法目前都没有 ranges:: 版本。

五、未初始化内存操作 (Operations on uninitialized memory)

主要头文件：

• <memory>：包含所有未初始化内存操作。

六、其他算法和工具

随机数生成 (Random number generation)

主要头文件：

• <random>

C 库函数 (C library functions)

主要头文件：

• <cstdlib> (或 <stdlib.h>)

附注：执行策略 (Execution policies)

主要头文件：

• <execution>

七、C++26 新特性

C++26 对算法库的改动主要集中在并行范围算法和随机数填充两块。

并行范围算法（Parallel range algorithms）

这是 C++26 最重要的一项变化：std::ranges 下的算法开始接受执行策略参数，从而把 Ranges 的便利性和 C++17 的并行能力结合了起来。在此之前，只有经典的 std:: 算法支持执行策略，ranges:: 版本并不接受。

#include <algorithm>
#include <execution>
#include <vector>

std::vector<int> v = /* ... */;

// C++26 起可用：Ranges 算法 + 并行策略
std::ranges::sort(std::execution::par, v);
std::ranges::copy(std::execution::par, src, dst);

需要注意的是，并行范围算法对迭代器有更严格的要求：通常要求 random_access_iterator 与 sized_sentinel_for，范围参数则要求是 sized random access range。此外，如果并行化所需的临时内存不足，会抛出 std::bad_alloc。

ranges::generate_random

std::ranges::generate_random 用一个均匀随机位生成器（uniform random bit generator）填充范围，也可以额外传入一个分布对象。它会优先调用生成器或分布的 generate_random 成员函数（如果存在），否则退化为逐个元素调用 ranges::generate。

#include <algorithm>
#include <random>

std::default_random_engine eng;
int arr[16]{};
std::ranges::generate_random(arr, eng);   // 用 eng 填充 arr

其它相关变化

• <algorithm> 的 freestanding 支持：C++26 起算法库的部分设施可用于 freestanding（无宿主）环境。
• constexpr 稳定排序：stable_sort 等稳定排序算法在 C++26 起可用于常量求值。
• 列表初始化支持：部分算法在 C++26 起支持对元素类型使用列表初始化（如 ranges::find(v, {1, 2}) 这类写法）。

提示： 并行范围算法需要标准库与并行后端（如 GCC 的 TBB）支持，实际可用性取决于编译器实现。使用前建议先检查 __cpp_lib_parallel_algorithm 的值：C++26 起为 202506L。