Algorithms library
算法库定义了用于多种目的（例如搜索、排序、计数、操作）的函数，这些函数对元素范围进行操作。请注意，
范围
被定义为
[
first
,
last
)
，其中
last
指向待检查或修改的最后一个元素的
后一
位置。
目录 |
受约束算法 (since C++20)
C++20 在命名空间
std::ranges
中提供了大多数算法的
约束
版本。在这些算法中，
范围
可以通过
迭代器
-
哨兵
对或单个
range
参数来指定，并且支持投影和成员指针可调用对象。此外，大多数算法的
返回类型
已改为返回算法执行期间计算的所有潜在有用信息。
std::vector<int> v{7, 1, 4, 0, -1}; std::ranges::sort(v); // 约束算法
执行策略 (自 C++17 起)
大多数算法都接受执行策略的重载版本。标准库算法支持多种 执行策略 ，库提供了相应的执行策略类型和对象。用户可以通过使用对应类型的 执行策略对象 调用并行算法来静态选择执行策略。
标准库实现（但非用户）可以定义额外的执行策略作为扩展。使用实现定义类型的执行策略对象调用并行算法时，其语义由实现定义。
并行版本的算法（除
std::for_each
和
std::for_each_n
外）允许对范围内的元素进行任意复制，只要满足
std::
is_trivially_copy_constructible_v
<
T
>
和
std::
is_trivially_destructible_v
<
T
>
均为
true
的条件，其中
T
表示元素类型。
|
定义于头文件
<execution>
|
|
|
定义于命名空间
std::execution
|
|
|
(C++17)
(C++17)
(C++17)
(C++20)
|
执行策略类型
(类) |
|
(C++17)
(C++17)
(C++17)
(C++20)
|
全局执行策略对象
(常量) |
|
定义于命名空间
std
|
|
|
(C++17)
|
检测一个类是否表示执行策略
(类模板) |
| 功能测试 宏 | 值 | 标准 | 功能 |
|---|---|---|---|
__cpp_lib_parallel_algorithm
|
201603L
|
(C++17) | 并行算法 |
__cpp_lib_execution
|
201603L
|
(C++17) | 执行策略 |
201902L
|
(C++20) | std::execution::unsequenced_policy |
非修改型序列操作
批量操作
|
定义于头文件
<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)
|
检查范围是否以另一范围结尾
(算法函数对象) |
折叠操作 (since C++23)
|
定义于头文件
<algorithm>
|
|
|
(C++23)
|
左折叠元素范围
(算法函数对象) |
|
(C++23)
|
使用首个元素作为初始值左折叠元素范围
(算法函数对象) |
|
(C++23)
|
右折叠元素范围
(算法函数对象) |
|
(C++23)
|
使用末尾元素作为初始值右折叠元素范围
(算法函数对象) |
|
(C++23)
|
左折叠元素范围，并返回
pair
(迭代器, 值)
(算法函数对象) |
|
使用首个元素作为初始值左折叠元素范围，并返回
pair
(迭代器,
optional
)
(算法函数对象) |
|
修改序列操作
复制操作
|
定义于头文件
<algorithm>
|
|
|
(C++11)
|
复制元素范围到新位置
(函数模板) |
|
(C++20)
(C++20)
|
复制元素范围到新位置
(算法函数对象) |
|
(C++11)
|
复制指定数量的元素到新位置
(函数模板) |
|
(C++20)
|
复制指定数量的元素到新位置
(算法函数对象) |
|
按逆序复制元素范围
(函数模板) |
|
|
(C++20)
|
按逆序复制元素范围
(算法函数对象) |
|
(C++11)
|
移动元素范围到新位置
(函数模板) |
|
(C++20)
|
移动元素范围到新位置
(算法函数对象) |
|
(C++11)
|
按逆序移动元素范围到新位置
(函数模板) |
|
(C++20)
|
按逆序移动元素范围到新位置
(算法函数对象) |
交换操作
|
定义于头文件
<string_view>
|
|
|
交换两个对象的值
(函数模板) |
|
|
定义于头文件
<algorithm>
|
|
|
交换两个范围的元素
(函数模板) |
|
|
(C++20)
|
交换两个范围的元素
(算法函数对象) |
|
交换两个迭代器所指向的元素
(函数模板) |
|
变换操作
|
定义于头文件
<algorithm>
|
|
|
对范围内的元素应用函数，并将结果存储到目标范围
(函数模板) |
|
|
(C++20)
|
对范围内的元素应用函数
(算法函数对象) |
|
将所有满足特定条件的值替换为另一个值
(函数模板) |
|
|
(C++20)
(C++20)
|
将所有满足特定条件的值替换为另一个值
(算法函数对象) |
|
复制范围，并将满足特定条件的元素替换为另一个值
(函数模板) |
|
|
(C++20)
(C++20)
|
复制范围，并将满足特定条件的元素替换为另一个值
(算法函数对象) |
生成操作
|
定义于头文件
<algorithm>
|
|
|
将给定值复制赋值给范围中的每个元素
(函数模板) |
|
|
(C++20)
|
为范围中的元素赋值
(算法函数对象) |
|
将给定值复制赋值给范围中的 N 个元素
(函数模板) |
|
|
(C++20)
|
为一定数量的元素赋值
(算法函数对象) |
|
将连续函数调用的结果赋值给范围中的每个元素
(函数模板) |
|
|
(C++20)
|
将函数结果保存到范围中
(算法函数对象) |
|
将连续函数调用的结果赋值给范围中的 N 个元素
(函数模板) |
|
|
(C++20)
|
将函数调用 N 次的结果保存
(算法函数对象) |
移除操作
|
定义于头文件
<algorithm>
|
|
|
移除满足特定条件的元素
(函数模板) |
|
|
(C++20)
(C++20)
|
移除满足特定条件的元素
(算法函数对象) |
|
复制范围中元素，省略满足特定条件的元素
(函数模板) |
|
|
(C++20)
(C++20)
|
复制范围中元素，省略满足特定条件的元素
(算法函数对象) |
|
移除范围中的连续重复元素
(函数模板) |
|
|
(C++20)
|
移除范围中的连续重复元素
(算法函数对象) |
|
创建不含连续重复元素的元素范围副本
(函数模板) |
|
|
(C++20)
|
创建不含连续重复元素的元素范围副本
(算法函数对象) |
顺序变更操作
|
定义于头文件
<algorithm>
|
|
|
反转范围中的元素顺序
(函数模板) |
|
|
(C++20)
|
反转范围中的元素顺序
(算法函数对象) |
|
创建反转后的范围副本
(函数模板) |
|
|
(C++20)
|
创建反转后的范围副本
(算法函数对象) |
|
旋转范围中的元素顺序
(函数模板) |
|
|
(C++20)
|
旋转范围中的元素顺序
(算法函数对象) |
|
复制并旋转元素范围
(函数模板) |
|
|
(C++20)
|
复制并旋转元素范围
(算法函数对象) |
|
(C++20)
|
移动范围中的元素
(函数模板) |
|
移动范围中的元素
(算法函数对象) |
|
|
(until C++17)
(C++11)
|
随机重排范围中的元素
(函数模板) |
|
(C++20)
|
随机重排范围中的元素
(算法函数对象) |
采样操作
|
定义于头文件
<algorithm>
|
|
|
(C++17)
|
从序列中选择 N 个随机元素
(函数模板) |
|
(C++20)
|
从序列中选择 N 个随机元素
(算法函数对象) |
需求规范
某些算法要求参数所表示的序列是“已排序”或“已分区”的。若未满足该要求，则行为未定义。
|
一个序列是 相对于比较器 comp 已排序的 ，当对于每个指向该序列的迭代器 iter 和每个非负整数 n ，只要 iter + n [1] 是指向序列元素的有效迭代器，就有 comp ( * ( iter + n ) , * iter ) == false [1] 。 |
(C++20 前) |
|
对于比较器
comp
和投影
proj
，一个序列是
相对于
comp
和
proj
已排序的
，当对于每个指向该序列的迭代器
iter
和每个非负整数
n
，只要
iter
+
n
[1]
是指向序列元素的有效迭代器，就有
bool
(
std::
invoke
(
comp,
std::
invoke
(
proj,
*
(
iter
+
n
)
)
,
一个序列是 相对于比较器 comp 已排序的 ，当该序列相对于 comp 和 std:: identity { } （恒等投影）已排序。 |
(C++20 起) |
一个序列
[
start
,
finish
)
被称为
相对于表达式
f
(
e
)
被划分
，当且仅当存在整数
n
，使得对于所有
i
在
[
0
,
std::
distance
(
start, finish
)
)
范围内，
f
(
*
(
start
+
i
)
)
[1]
为
true
当且仅当
i
<
n
。
分区操作
|
定义于头文件
<algorithm>
|
|
|
(C++11)
|
判断范围是否按给定谓词划分
(函数模板) |
|
(C++20)
|
判断范围是否按给定谓词划分
(算法函数对象) |
|
将元素范围划分为两组
(函数模板) |
|
|
(C++20)
|
将元素范围划分为两组
(算法函数对象) |
|
(C++11)
|
复制范围并将元素划分为两组
(函数模板) |
|
(C++20)
|
复制范围并将元素划分为两组
(算法函数对象) |
|
将元素划分为两组并保持相对顺序
(函数模板) |
|
|
(C++20)
|
将元素划分为两组并保持相对顺序
(算法函数对象) |
|
(C++11)
|
定位已划分范围的划分点
(函数模板) |
|
(C++20)
|
定位已划分范围的划分点
(算法函数对象) |
排序操作
|
定义于头文件
<algorithm>
|
|
|
将范围按升序排序
(函数模板) |
|
|
(C++20)
|
将范围按升序排序
(算法函数对象) |
|
排序范围元素并保持相等元素间的顺序
(函数模板) |
|
|
(C++20)
|
排序范围元素并保持相等元素间的顺序
(算法函数对象) |
|
排序范围的前 N 个元素
(函数模板) |
|
|
(C++20)
|
排序范围的前 N 个元素
(算法函数对象) |
|
复制并部分排序范围元素
(函数模板) |
|
|
(C++20)
|
复制并部分排序范围元素
(算法函数对象) |
|
(C++11)
|
检查范围是否已按升序排序
(函数模板) |
|
(C++20)
|
检查范围是否已按升序排序
(算法函数对象) |
|
(C++11)
|
找出最大的已排序子范围
(函数模板) |
|
(C++20)
|
找出最大的已排序子范围
(算法函数对象) |
|
部分排序给定范围，确保其按给定元素划分
(函数模板) |
|
|
(C++20)
|
部分排序给定范围，确保其按给定元素划分
(算法函数对象) |
二分查找操作（作用于分区范围）
|
定义于头文件
<algorithm>
|
|
|
返回指向首个
不小于
给定值的元素的迭代器
(函数模板) |
|
|
(C++20)
|
返回指向首个
不小于
给定值的元素的迭代器
(算法函数对象) |
|
返回指向首个
大于
某值的元素的迭代器
(函数模板) |
|
|
(C++20)
|
返回指向首个
大于
某值的元素的迭代器
(算法函数对象) |
|
返回匹配特定键的元素范围
(函数模板) |
|
|
(C++20)
|
返回匹配特定键的元素范围
(算法函数对象) |
|
判断元素是否存在于部分有序范围中
(函数模板) |
|
|
(C++20)
|
判断元素是否存在于部分有序范围中
(算法函数对象) |
集合操作（针对已排序范围）
|
定义于头文件
<algorithm>
|
|
|
若一个序列是另一个序列的子序列则返回
true
(函数模板) |
|
|
(C++20)
|
若一个序列是另一个序列的子序列则返回
true
(算法函数对象) |
|
计算两个集合的并集
(函数模板) |
|
|
(C++20)
|
计算两个集合的并集
(算法函数对象) |
|
计算两个集合的交集
(函数模板) |
|
|
(C++20)
|
计算两个集合的交集
(算法函数对象) |
|
计算两个集合的差集
(函数模板) |
|
|
(C++20)
|
计算两个集合的差集
(算法函数对象) |
|
计算两个集合的对称差
(函数模板) |
|
|
(C++20)
|
计算两个集合的对称差
(算法函数对象) |
合并操作（针对已排序范围）
|
定义于头文件
<algorithm>
|
|
|
合并两个已排序范围
(函数模板) |
|
|
(C++20)
|
合并两个已排序范围
(算法函数对象) |
|
就地合并两个有序范围
(函数模板) |
|
|
(C++20)
|
就地合并两个有序范围
(算法函数对象) |
堆操作
|
当对于所有整数
i
在区间
|
(C++20 前) |
|
当对于所有整数
i
在区间
若范围是关于
comp
和
std::
identity
{
}
（恒等投影）的堆，则随机访问
范围
|
(C++20 起) |
堆可以通过 std::make_heap 和 ranges::make_heap (自 C++20 起) 创建。
有关堆的更多属性，请参见 最大堆 。
|
定义于头文件
<algorithm>
|
|
|
向最大堆添加元素
(函数模板) |
|
|
(C++20)
|
向最大堆添加元素
(算法函数对象) |
|
从最大堆中移除最大元素
(函数模板) |
|
|
(C++20)
|
从最大堆中移除最大元素
(算法函数对象) |
|
从元素范围创建最大堆
(函数模板) |
|
|
(C++20)
|
从元素范围创建最大堆
(算法函数对象) |
|
将最大堆转换为按升序排序的元素范围
(函数模板) |
|
|
(C++20)
|
将最大堆转换为按升序排序的元素范围
(算法函数对象) |
|
(C++11)
|
检查给定范围是否构成最大堆
(函数模板) |
|
(C++20)
|
检查给定范围是否构成最大堆
(算法函数对象) |
|
(C++11)
|
寻找能构成最大堆的最大子范围
(函数模板) |
|
(C++20)
|
寻找能构成最大堆的最大子范围
(算法函数对象) |
最小/最大值操作
|
定义于头文件
<algorithm>
|
|
|
返回给定值中的较大者
(函数模板) |
|
|
(C++20)
|
返回给定值中的较大者
(算法函数对象) |
|
返回范围内的最大元素
(函数模板) |
|
|
(C++20)
|
返回范围内的最大元素
(算法函数对象) |
|
返回给定值中的较小者
(函数模板) |
|
|
(C++20)
|
返回给定值中的较小者
(算法函数对象) |
|
返回范围内的最小元素
(函数模板) |
|
|
(C++20)
|
返回范围内的最小元素
(算法函数对象) |
|
(C++11)
|
返回两个元素的较小者和较大者
(函数模板) |
|
(C++20)
|
返回两个元素的较小者和较大者
(算法函数对象) |
|
(C++11)
|
返回范围内的最小和最大元素
(函数模板) |
|
(C++20)
|
返回范围内的最小和最大元素
(算法函数对象) |
|
(C++17)
|
将值限制在一对边界值之间
(函数模板) |
|
(C++20)
|
将值限制在一对边界值之间
(算法函数对象) |
字典序比较操作
|
定义于头文件
<algorithm>
|
|
|
若一个范围按字典序小于另一个范围则返回
true
(函数模板) |
|
|
(C++20)
|
若一个范围按字典序小于另一个范围则返回
true
(算法函数对象) |
|
使用三路比较比较两个范围
(函数模板) |
|
排列操作
|
定义于头文件
<algorithm>
|
|
|
生成元素范围的下一个较大字典序排列
(函数模板) |
|
|
(C++20)
|
生成元素范围的下一个较大字典序排列
(算法函数对象) |
|
生成元素范围的下一个较小字典序排列
(函数模板) |
|
|
(C++20)
|
生成元素范围的下一个较小字典序排列
(算法函数对象) |
|
(C++11)
|
判断一个序列是否为另一个序列的排列
(函数模板) |
|
(C++20)
|
判断一个序列是否为另一个序列的排列
(算法函数对象) |
数值运算
|
定义于头文件
<numeric>
|
|
|
(C++11)
|
以起始值的连续增量填充范围
(函数模板) |
|
(C++23)
|
以起始值的连续增量填充范围
(算法函数对象) |
|
对一个范围内的元素进行求和或折叠
(函数模板) |
|
|
计算两个元素范围的内积
(函数模板) |
|
|
计算范围内相邻元素的差值
(函数模板) |
|
|
计算元素范围的部分和
(函数模板) |
|
|
(C++17)
|
类似于
std::accumulate
，但无序执行
(函数模板) |
|
(C++17)
|
类似于
std::partial_sum
，在第
i
th
个和中排除第
i
th
个输入元素
(函数模板) |
|
(C++17)
|
类似于
std::partial_sum
，在第
i
th
个和中包含第
i
th
个输入元素
(函数模板) |
|
(C++17)
|
应用可调用对象后无序规约
(函数模板) |
|
(C++17)
|
应用可调用对象后计算排除性扫描
(函数模板) |
|
(C++17)
|
应用可调用对象后计算包含性扫描
(函数模板) |
未初始化内存操作
|
定义于头文件
<memory>
|
|
|
复制对象范围到未初始化的内存区域
(函数模板) |
|
|
(C++20)
|
复制对象范围到未初始化的内存区域
(算法函数对象) |
|
(C++11)
|
复制指定数量对象到未初始化的内存区域
(函数模板) |
|
(C++20)
|
复制指定数量对象到未初始化的内存区域
(算法函数对象) |
|
复制对象到由范围定义的未初始化内存区域
(函数模板) |
|
|
(C++20)
|
复制对象到由范围定义的未初始化内存区域
(算法函数对象) |
|
复制对象到由起始点和计数定义的未初始化内存区域
(函数模板) |
|
|
(C++20)
|
复制对象到由起始点和计数定义的未初始化内存区域
(算法函数对象) |
|
(C++17)
|
移动对象范围到未初始化的内存区域
(函数模板) |
|
(C++20)
|
移动对象范围到未初始化的内存区域
(算法函数对象) |
|
(C++17)
|
移动指定数量对象到未初始化的内存区域
(函数模板) |
|
(C++20)
|
移动指定数量对象到未初始化的内存区域
(算法函数对象) |
|
(C++17)
|
通过
默认初始化
在由范围定义的未初始化内存区域中构造对象
(函数模板) |
|
通过
默认初始化
在由范围定义的未初始化内存区域中构造对象
(算法函数对象) |
|
|
通过
默认初始化
在由起始点和计数定义的未初始化内存区域中构造对象
(函数模板) |
|
|
通过
默认初始化
在由起始点和计数定义的未初始化内存区域中构造对象
(算法函数对象) |
|
|
(C++17)
|
通过
值初始化
在由范围定义的未初始化内存区域中构造对象
(函数模板) |
|
通过
值初始化
在由范围定义的未初始化内存区域中构造对象
(算法函数对象) |
|
|
(C++17)
|
通过
值初始化
在由起始点和计数定义的未初始化内存区域中构造对象
(函数模板) |
|
通过
值初始化
在由起始点和计数定义的未初始化内存区域中构造对象
(算法函数对象) |
|
|
(C++17)
|
销毁对象范围
(函数模板) |
|
(C++20)
|
销毁对象范围
(算法函数对象) |
|
(C++17)
|
销毁范围内的指定数量对象
(函数模板) |
|
(C++20)
|
销毁范围内的指定数量对象
(算法函数对象) |
|
(C++17)
|
销毁给定地址处的对象
(函数模板) |
|
(C++20)
|
销毁给定地址处的对象
(算法函数对象) |
|
(C++20)
|
在给定地址处创建对象
(函数模板) |
随机数生成 (始于 C++26)
|
定义于头文件
<random>
|
|
|
(C++26)
|
使用均匀随机位生成器填充范围内的随机数
(算法函数对象) |
注释
| 功能测试 宏 | 值 | 标准 | 功能 |
|---|---|---|---|
__cpp_lib_algorithm_iterator_requirements
|
202207L
|
(C++23) | 范围迭代器作为非范围算法的输入 |
__cpp_lib_clamp
|
201603L
|
(C++17) | std::clamp |
__cpp_lib_constexpr_algorithms
|
201806L
|
(C++20) | 算法的常量表达式支持 |
202306L
|
(C++26) | 常量表达式稳定排序 | |
__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++标准。
| 缺陷报告 | 应用于 | 发布时行为 | 正确行为 |
|---|---|---|---|
| LWG 193 | C++98 | 堆要求 * first 必须是最大元素 | 允许存在与 * first 相等的元素 |
| LWG 2150 | C++98 | 有序序列的定义存在错误 | 已修正 |
| LWG 2166 | C++98 | 堆要求与 最大堆 的定义匹配度不足 | 要求已改进 |
参见
|
C 文档
关于
Algorithms
|