Algorithms

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

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 命名空间下（尽管全局对象如 std::par 在 std 命名空间）。

示例:

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

并行算法的技术限制

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

对于大多数并行算法（除了 std::for_each 和 std::for_each_n）：

• 如果 Range 中的元素类型 \( T \) 满足 Trivial Copy Construction (std::is_trivially_copy_constructible_v<T> == true) 和 Trivial Destruction (std::is_trivially_destructible_v<T> == true)，库可以对元素进行任意复制，以便在不同的并行线程之间分发数据。

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

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

主要头文件：

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

批处理操作 (Batch operations)

搜索操作 (Search operations)

折叠操作 (Fold operations)

二、修改序列操作 (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。

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

主要头文件：

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

六、其他算法和工具

随机数生成 (Random number generation)

主要头文件：

• <ranges>

C 库函数 (C library functions)

主要头文件：

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

附注：执行策略 (Execution policies)

主要头文件：

• <execution>