算法库
来自 cppreference.com
< cpp
算法库定义了用于各种目的（例如搜索、排序、计数、操作）的函数，这些函数作用于元素范围。注意，范围定义为[first, last)，其中 last 指向要检查或修改的最后一个元素之后的元素。
约束算法C++20 提供了 std::vector<int> v {7, 1, 4, 0, -1}; std::ranges::sort(v); // constrained algorithm |
(自 C++20 起) |
执行策略大多数算法都有接受执行策略的重载。标准库算法支持多种 执行策略，库提供了相应的执行策略类型和对象。用户可以通过使用对应类型的 执行策略对象 调用并行算法来静态选择执行策略。 标准库实现（但不是用户）可以定义额外的执行策略作为扩展。使用实现定义类型的执行策略对象调用的并行算法的语义是实现定义的。 并行版本的算法（除了 std::for_each 和 std::for_each_n）允许从范围中任意复制元素，只要 std::is_trivially_copy_constructible_v<T> 和 std::is_trivially_destructible_v<T> 为 true，其中
|
(自 C++17 起) | |||||||||||||||||||||||||||
[编辑] 非修改序列操作
[编辑] 批量操作
| 在头文件
<algorithm> 中定义 | |
| 将函数应用于元素范围 (函数模板) | |
| (C++20) |
将函数应用于元素范围 (非阻塞函数) |
| (C++17) |
将函数对象应用于序列的前 N 个元素 (函数模板) |
| (C++20) |
将函数对象应用于序列的前 N 个元素 (非阻塞函数) |
[编辑] 搜索操作
| 在头文件
<algorithm> 中定义 | |
| (C++11)(C++11)(C++11) |
检查谓词是否在范围内的所有元素、任何元素或无元素上为 true (函数模板) |
| (C++20)(C++20)(C++20) |
检查谓词是否在范围内的所有元素、任何元素或无元素上为 true (非阻塞函数) |
| (C++23)(C++23) |
检查范围是否包含给定的元素或子范围 (非阻塞函数) |
| (C++11) |
查找第一个满足特定条件的元素 (函数模板) |
| (C++20)(C++20)(C++20) |
查找第一个满足特定条件的元素 (非阻塞函数) |
| (C++23)(C++23)(C++23) |
查找最后一个满足特定条件的元素 (非阻塞函数) |
| 查找某个范围内的最后一个元素序列 (函数模板) | |
| (C++20) |
查找某个范围内的最后一个元素序列 (非阻塞函数) |
| 搜索一组元素中的任何一个 (函数模板) | |
| (C++20) |
搜索一组元素中的任何一个 (非阻塞函数) |
| 查找第一个相等的两个相邻项（或满足给定谓词） (函数模板) | |
| (C++20) |
查找第一个相等的两个相邻项（或满足给定谓词） (非阻塞函数) |
| 返回满足特定条件的元素数量 (函数模板) | |
| (C++20)(C++20) |
返回满足特定条件的元素数量 (非阻塞函数) |
| 查找两个范围不同的第一个位置 (函数模板) | |
| (C++20) |
查找两个范围不同的第一个位置 (非阻塞函数) |
| 确定两组元素是否相同 (函数模板) | |
| (C++20) |
确定两组元素是否相同 (非阻塞函数) |
| 搜索元素范围的第一次出现 (函数模板) | |
| (C++20) |
搜索元素范围的第一次出现 (非阻塞函数) |
| 搜索范围内元素的第一个连续副本的出现 (函数模板) | |
| (C++20) |
搜索范围内元素的第一个连续副本的出现 (非阻塞函数) |
| (C++23) |
检查范围是否以另一个范围开头 (非阻塞函数) |
| (C++23) |
检查范围是否以另一个范围结尾 (非阻塞函数) |
[编辑] 折叠操作
| 在头文件
<algorithm> 中定义 | |
| (C++23) |
左折叠元素范围 (非阻塞函数) |
| (C++23) |
使用第一个元素作为初始值左折叠元素范围 (非阻塞函数) |
| (C++23) |
右折叠元素范围 (非阻塞函数) |
| (C++23) |
使用最后一个元素作为初始值右折叠元素范围 (非阻塞函数) |
| (C++23) |
左折叠元素范围，并返回一个 pair (迭代器, 值) (非阻塞函数) |
| 使用第一个元素作为初始值左折叠元素范围，并返回一个 pair (迭代器, 可选) (非阻塞函数) | |
[编辑] 修改序列操作
[编辑] 复制操作
| 在头文件
<algorithm> 中定义 | |
| (C++11) |
将元素范围复制到新位置 (函数模板) |
| (C++20)(C++20) |
将元素范围复制到新位置 (非阻塞函数) |
| (C++11) |
将一定数量的元素复制到新位置 (函数模板) |
| (C++20) |
将一定数量的元素复制到新位置 (niebloid) |
| 以倒序复制元素范围 (函数模板) | |
| (C++20) |
以倒序复制元素范围 (niebloid) |
| (C++11) |
将元素范围移动到新位置 (函数模板) |
| (C++20) |
将元素范围移动到新位置 (niebloid) |
| (C++11) |
将元素范围以倒序移动到新位置 (函数模板) |
| (C++20) |
将元素范围以倒序移动到新位置 (niebloid) |
[编辑] 交换操作
| 定义在头文件
<string_view> | |
| 交换两个对象的数值 (函数模板) | |
| 在头文件
<algorithm> 中定义 | |
| 交换两个元素范围 (函数模板) | |
| (C++20) |
交换两个元素范围 (niebloid) |
| 交换两个迭代器指向的元素 (函数模板) | |
[编辑] 转换操作
| 在头文件
<algorithm> 中定义 | |
| 将函数应用于元素范围，并将结果存储在目标范围中 (函数模板) | |
| (C++20) |
将函数应用于元素范围 (niebloid) |
| 用另一个值替换所有满足特定条件的值 (函数模板) | |
| (C++20)(C++20) |
用另一个值替换所有满足特定条件的值 (niebloid) |
| 复制范围，用另一个值替换满足特定条件的元素 (函数模板) | |
| (C++20)(C++20) |
复制范围，用另一个值替换满足特定条件的元素 (niebloid) |
[编辑] 生成操作
| 在头文件
<algorithm> 中定义 | |
| 将给定值复制赋值给范围中的每个元素 (函数模板) | |
| (C++20) |
为元素范围分配特定值 (niebloid) |
| 将给定值复制赋值给范围中的 N 个元素 (函数模板) | |
| (C++20) |
将值分配给多个元素 (niebloid) |
| 将连续函数调用的结果分配给范围中的每个元素 (函数模板) | |
| (C++20) |
将函数的结果保存在范围内 (niebloid) |
| 将连续函数调用的结果分配给范围中的 N 个元素 (函数模板) | |
| (C++20) |
保存函数 N 次应用的结果 (niebloid) |
[编辑] 移除操作
| 在头文件
<algorithm> 中定义 | |
| 移除满足特定条件的元素 (函数模板) | |
| (C++20)(C++20) |
移除满足特定条件的元素 (niebloid) |
| 复制元素范围，省略满足特定条件的元素 (函数模板) | |
| (C++20)(C++20) |
复制元素范围，省略满足特定条件的元素 (niebloid) |
| 移除范围内连续的重复元素 (函数模板) | |
| (C++20) |
移除范围内连续的重复元素 (niebloid) |
| 创建一个不包含连续重复元素的元素范围副本 (函数模板) | |
| (C++20) |
创建一个不包含连续重复元素的元素范围副本 (niebloid) |
[编辑] 顺序更改操作
| 在头文件
<algorithm> 中定义 | |
| 颠倒范围中元素的顺序 (函数模板) | |
| (C++20) |
颠倒范围中元素的顺序 (niebloid) |
| 创建一个反转的范围副本 (函数模板) | |
| (C++20) |
创建一个反转的范围副本 (niebloid) |
| 旋转范围中元素的顺序 (函数模板) | |
| (C++20) |
旋转范围中元素的顺序 (niebloid) |
| 复制并旋转元素范围 (函数模板) | |
| (C++20) |
复制并旋转元素范围 (niebloid) |
| (C++20) |
移动范围中的元素 (函数模板) |
| (直到 C++17)(C++11) |
随机重新排列范围中的元素 (函数模板) |
| (C++20) |
随机重新排列范围中的元素 (niebloid) |
| 移动范围中的元素 (niebloid) | |
[编辑] 采样操作
| 在头文件
<algorithm> 中定义 | |
| (C++17) |
从序列中选择 N 个随机元素 (函数模板) |
| (C++20) |
从序列中选择 N 个随机元素 (niebloid) |
[edit]
[edit] 要求
某些算法要求参数表示的序列为“已排序”或“已分区”。如果未满足此要求，则行为未定义。
|
如果对于指向序列的每个迭代器 iter 和每个非负整数 n，只要 iter + n[1] 是一个指向序列元素的有效迭代器，则序列是相对于比较器 comp 排序的，comp(*(iter + n), *iter) == false[1]。 |
(直到 C++20) |
|
对于比较器 comp 和投影 proj，如果对于指向序列的每个迭代器 iter 和每个非负整数 n，只要 iter + n[1] 是一个指向序列元素的有效迭代器，则序列是相对于 comp 和 proj 排序的，bool(std::invoke(comp, std::invoke(proj, *(iter + n)), 如果序列相对于 comp 和 std::identity{}（恒等投影）排序，则序列是相对于比较器 comp 排序的。 |
(自 C++20 起) |
序列 [start, finish) 是相对于表达式 f(e) 分区的，如果存在一个整数 n，使得对于 [0, std::distance(start, finish)) 中的所有 i，f(*(start + i))[1] 为真，当且仅当 i < n 为真。
[edit] 分区操作
| 在头文件
<algorithm> 中定义 | |
| (C++11) |
确定范围是否由给定谓词分区 (函数模板) |
| (C++20) |
确定范围是否由给定谓词分区 (niebloid) |
| 将元素范围划分为两组 (函数模板) | |
| (C++20) |
将元素范围划分为两组 (niebloid) |
| (C++11) |
复制范围，将元素划分为两组 (函数模板) |
| (C++20) |
复制范围，将元素划分为两组 (niebloid) |
| 将元素划分为两组，同时保留它们之间的相对顺序 (函数模板) | |
| (C++20) |
将元素划分为两组，同时保留它们之间的相对顺序 (niebloid) |
| (C++11) |
定位已分区范围的分区点 (函数模板) |
| (C++20) |
定位已分区范围的分区点 (niebloid) |
[edit] 排序操作
| 在头文件
<algorithm> 中定义 | |
| 将范围排序为升序 (函数模板) | |
| (C++20) |
将范围排序为升序 (niebloid) |
| 排序元素范围，同时保留相等元素之间的顺序 (函数模板) | |
| (C++20) |
排序元素范围，同时保留相等元素之间的顺序 (niebloid) |
| 对范围的前 N 个元素进行排序 (函数模板) | |
| (C++20) |
对范围的前 N 个元素进行排序 (niebloid) |
| 复制并部分排序元素范围 (函数模板) | |
| (C++20) |
复制并部分排序元素范围 (niebloid) |
| (C++11) |
检查范围是否已排序为升序 (函数模板) |
| (C++20) |
检查范围是否已排序为升序 (niebloid) |
| (C++11) |
查找最大的已排序子范围 (函数模板) |
| (C++20) |
查找最大的已排序子范围 (niebloid) |
| 部分排序给定范围，确保其按给定元素分区 (函数模板) | |
| (C++20) |
部分排序给定范围，确保其按给定元素分区 (niebloid) |
[edit] 二分查找操作（在已分区范围上）
| 在头文件
<algorithm> 中定义 | |
| 返回指向第一个不小于给定值的元素的迭代器 (函数模板) | |
| (C++20) |
返回指向第一个不小于给定值的元素的迭代器 (niebloid) |
| 返回指向第一个大于某个值的元素的迭代器 (函数模板) | |
| (C++20) |
返回指向第一个大于某个值的元素的迭代器 (niebloid) |
| 返回与特定键匹配的元素范围 (函数模板) | |
| (C++20) |
返回与特定键匹配的元素范围 (niebloid) |
| 确定元素是否存在于部分排序的范围内 (函数模板) | |
| (C++20) |
确定元素是否存在于部分排序的范围内 (niebloid) |
[编辑] 集合操作（在排序的范围内）
| 在头文件
<algorithm> 中定义 | |
| 如果一个序列是另一个序列的子序列，则返回 true (函数模板) | |
| (C++20) |
如果一个序列是另一个序列的子序列，则返回 true (niebloid) |
| 计算两个集合的并集 (函数模板) | |
| (C++20) |
计算两个集合的并集 (niebloid) |
| 计算两个集合的交集 (函数模板) | |
| (C++20) |
计算两个集合的交集 (niebloid) |
| 计算两个集合的差集 (函数模板) | |
| (C++20) |
计算两个集合的差集 (niebloid) |
| 计算两个集合的对称差集 (函数模板) | |
| 计算两个集合的对称差集 (niebloid) | |
[编辑] 合并操作（在排序的范围内）
| 在头文件
<algorithm> 中定义 | |
| 合并两个排序的范围 (函数模板) | |
| (C++20) |
合并两个排序的范围 (niebloid) |
| 将两个有序的范围合并到内存中 (函数模板) | |
| (C++20) |
将两个有序的范围合并到内存中 (niebloid) |
[编辑] 堆操作
|
一个随机访问的 范围 |
(直到 C++20) |
|
一个随机访问的 范围 一个随机访问的范围 |
(自 C++20 起) |
堆可以通过 std::make_heap和 ranges::make_heap(自 C++20 起) 创建。
有关堆的更多属性，请参阅 最大堆。
| 在头文件
<algorithm> 中定义 | |
| 将一个元素添加到最大堆中 (函数模板) | |
| (C++20) |
将一个元素添加到最大堆中 (niebloid) |
| 从最大堆中移除最大元素 (函数模板) | |
| (C++20) |
从最大堆中移除最大元素 (niebloid) |
| 从元素范围内创建一个最大堆 (函数模板) | |
| (C++20) |
从元素范围内创建一个最大堆 (niebloid) |
| 将最大堆转换为按升序排序的元素范围 (函数模板) | |
| (C++20) |
将最大堆转换为按升序排序的元素范围 (niebloid) |
| (C++11) |
检查给定范围是否为最大堆 (函数模板) |
| (C++20) |
检查给定范围是否为最大堆 (niebloid) |
| (C++11) |
找到是最大堆的最大子范围 (函数模板) |
| (C++20) |
找到是最大堆的最大子范围 (niebloid) |
[编辑] 最小值/最大值操作
| 在头文件
<algorithm> 中定义 | |
| 返回给定值中较大的值 (函数模板) | |
| (C++20) |
返回给定值中较大的值 (niebloid) |
| 返回范围内的最大元素 (函数模板) | |
| (C++20) |
返回范围内的最大元素 (niebloid) |
| 返回给定值中较小的值 (函数模板) | |
| (C++20) |
返回给定值中较小的值 (niebloid) |
| 返回范围内的最小元素 (函数模板) | |
| (C++20) |
返回范围内的最小元素 (niebloid) |
| (C++11) |
返回两个元素中较小和较大的值 (函数模板) |
| (C++20) |
返回两个元素中较小和较大的值 (niebloid) |
| (C++11) |
返回范围内的最小元素和最大元素 (函数模板) |
| (C++20) |
返回范围内的最小元素和最大元素 (niebloid) |
| (C++17) |
将值夹在边界值对之间 (函数模板) |
| (C++20) |
将值夹在边界值对之间 (niebloid) |
[编辑] 字典序比较操作
| 在头文件
<algorithm> 中定义 | |
| 如果一个范围字典序小于另一个范围，则返回 true (函数模板) | |
| 如果一个范围字典序小于另一个范围，则返回 true (niebloid) | |
| 使用三路比较来比较两个范围 (函数模板) | |
[编辑] 排列操作
| 在头文件
<algorithm> 中定义 | |
| 生成一系列元素的下一个字典序排列 (函数模板) | |
| (C++20) |
生成一系列元素的下一个字典序排列 (niebloid) |
| 生成一系列元素的下一个较小的字典序排列 (函数模板) | |
| (C++20) |
生成一系列元素的下一个较小的字典序排列 (niebloid) |
| (C++11) |
确定序列是否为另一个序列的排列 (函数模板) |
| (C++20) |
确定序列是否为另一个序列的排列 (niebloid) |
[编辑] 数值操作
| 在头文件
<numeric> 中定义 | |
| (C++11) |
用起始值的连续增量填充范围 (函数模板) |
| (C++23) |
用起始值的连续增量填充范围 (niebloid) |
| 将一系列元素加起来或折叠起来 (函数模板) | |
| 计算两个元素范围的内积 (函数模板) | |
| 计算范围中相邻元素之间的差异 (函数模板) | |
| 计算一系列元素的偏和 (函数模板) | |
| (C++17) |
类似于 std::accumulate，但顺序不同 (函数模板) |
| (C++17) |
类似于 std::partial_sum，从第 ith 和中排除第 ith 输入元素 (函数模板) |
| (C++17) |
类似于 std::partial_sum，在第 ith 和中包含第 ith 输入元素 (函数模板) |
| (C++17) |
应用一个可调用对象，然后进行降序归约 (函数模板) |
| (C++17) |
应用一个可调用对象，然后计算独占扫描 (函数模板) |
| (C++17) |
应用一个可调用对象，然后计算包含扫描 (函数模板) |
[编辑] 对未初始化内存的操作
| 在头文件
<memory> 中定义 | |
| 将一系列对象复制到未初始化的内存区域 (函数模板) | |
| (C++20) |
将一系列对象复制到未初始化的内存区域 (niebloid) |
| (C++11) |
将一定数量的对象复制到未初始化的内存区域 (函数模板) |
| (C++20) |
将一定数量的对象复制到未初始化的内存区域 (niebloid) |
| 将一个对象复制到由范围定义的未初始化内存区域 (函数模板) | |
| (C++20) |
将一个对象复制到由范围定义的未初始化内存区域 (非阻塞) |
| 将一个对象复制到由起始位置和数量定义的未初始化内存区域。 (函数模板) | |
| (C++20) |
将一个对象复制到由起始位置和数量定义的未初始化内存区域。 (非阻塞) |
| (C++17) |
将一系列对象移动到未初始化的内存区域。 (函数模板) |
| (C++20) |
将一系列对象移动到未初始化的内存区域。 (非阻塞) |
| (C++17) |
将一定数量的对象移动到未初始化的内存区域。 (函数模板) |
| (C++20) |
将一定数量的对象移动到未初始化的内存区域。 (非阻塞) |
| 通过默认初始化在由范围定义的未初始化内存区域中构造对象。 (函数模板) | |
| 通过默认初始化在由范围定义的未初始化内存区域中构造对象。 (非阻塞) | |
| 通过默认初始化在由起始位置和数量定义的未初始化内存区域中构造对象。 (函数模板) | |
| 通过默认初始化在由起始位置和数量定义的未初始化内存区域中构造对象。 (非阻塞) | |
| 通过值初始化在由范围定义的未初始化内存区域中构造对象。 (函数模板) | |
| 通过值初始化在由范围定义的未初始化内存区域中构造对象。 (非阻塞) | |
| 通过值初始化在由起始位置和数量定义的未初始化内存区域中构造对象。 (函数模板) | |
| 通过值初始化在由起始位置和数量定义的未初始化内存区域中构造对象。 (非阻塞) | |
| (C++17) |
销毁一系列对象。 (函数模板) |
| (C++20) |
销毁一系列对象。 (非阻塞) |
| (C++17) |
销毁范围内一定数量的对象。 (函数模板) |
| (C++20) |
销毁范围内一定数量的对象。 (非阻塞) |
| (C++17) |
销毁给定地址上的对象。 (函数模板) |
| (C++20) |
销毁给定地址上的对象。 (非阻塞) |
| (C++20) |
在给定地址处创建一个对象。 (函数模板) |
| (C++20) |
在给定地址处创建一个对象。 (非阻塞) |
[编辑] 随机数生成
| 在头文件
<random> 中定义。 | |
| (C++26) |
使用均匀随机位生成器填充范围内的随机数。 (非阻塞) |
[编辑] 备注
| 特性测试 宏 | 值 | Std | 特性 |
|---|---|---|---|
__cpp_lib_algorithm_iterator_requirements |
202207L | (C++23) | 范围迭代器作为非范围算法的输入。 |
__cpp_lib_clamp |
201603L | (C++17) | std::clamp |
__cpp_lib_constexpr_algorithms |
201806L | (C++20) | 算法的 constexpr 支持。 |
| 202306L | (C++26) | 稳定排序的 constexpr 支持。 | |
__cpp_lib_algorithm_default_value_type |
202403L | (C++26) | 算法的列表初始化。 |
__cpp_lib_freestanding_algorithm |
202311L | (C++26) | 在<algorithm> 中的独立设施。 |
__cpp_lib_robust_nonmodifying_seq_ops |
201304L | (C++14) | 使非修改序列操作更加健壮（std::mismatch、std::equal 和 std::is_permutation 的双范围重载）。 |
__cpp_lib_sample |
201603L | (C++17) | std::sample |
__cpp_lib_shift |
201806L | (C++20) | std::shift_left 和 std::shift_right |
[编辑] C 库
| 在头文件
<cstdlib> 中定义。 | |
| 对一组未指定类型元素进行排序。 (函数) | |
| 在数组中搜索未指定类型的元素。 (函数) | |
[编辑] 缺陷报告
以下行为变更缺陷报告被追溯应用于先前发布的 C++ 标准。
| DR | 应用于 | 已发布的行为 | 正确行为 |
|---|---|---|---|
| LWG 193 | C++98 | 堆需要 *first 是最大元素 | 可能存在 等于 *first 的元素 |
| LWG 2150 | C++98 | 排序序列的定义不正确 | 已更正 |
| LWG 2166 | C++98 | 堆要求与 对最大堆 的定义不完全匹配 |
要求得到改进 |
[编辑] 另请参阅
| C 文档 用于 算法
|
