算法库

来自cppreference.com
< cpp
See More


 
C++
 
算法库
受约束算法及范围上的算法 (C++20)
包含算法例如 ranges::copy、ranges::sort、...
排序和相关操作
划分操作
(C++11)
(C++11)    

排序操作
二分搜索操作（在已划分范围上）
集合操作（在有序范围上）
归并操作（在有序范围上）
堆操作
最小/最大操作
(C++11)
(C++17)
字典序比较操作
(C++20)
排列操作




 

算法库提供大量用途的函数（例如查找、排序、计数、操作），它们在元素范围上操作。注意，范围定义为 [first, last)，其中 last 指代要查询或修改的最后元素的后一个 元素。

受约束算法 (C++20 起)

C++20 在命名空间 std::ranges 中提供大多数算法的受约束版本，在这些算法中，范围既可以由迭代器-哨位对，也可以由单个 range 实参指定，还支持投影和成员指针可调用对象。另外，还更改了大多数算法的返回类型，以返回算法执行过程中计算的所有潜在有用信息。 

std::vector<int> v{7, 1, 4, 0, -1};
std::ranges::sort(v); // 受约束算法

并行算法 (C++17 起)

并行算法 是算法库中带有名为 ExecutionPolicy 或由 execution-policy 约束(C++26 起)的模板形参的函数模板。这种模板形参被称为执行策略模板形参，它描述了可以将并行算法的执行以哪种方式并行化。

除非另有说明，并行算法可以从范围进行任意的元素复制，只要 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)
 测试类是否表示某种执行策略
(类模板) [编辑]
(C++26)
 指定一个类型表示某种执行策略
(仅用于阐述的概念*) [编辑]

不修改序列的操作

批量操作

在标头 <algorithm> 定义
应用一元函数对象到范围中的元素
(函数模板 & 算法函数对象)[编辑]
(C++20)
(C++17)
 应用函数对象到序列的前 N 个元素
(函数模板 & 算法函数对象)[编辑]
(C++20)

搜索操作

在标头 <algorithm> 定义
(C++11)(C++11)(C++11)
 检查谓词是否对范围中所有、任一或无元素为 true
(函数模板 & 算法函数对象)[编辑]
(C++20)(C++20)(C++20)
(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)
 检查一个范围是否终于另一范围
(算法函数对象) [编辑]

折叠操作 (C++23 起)

在标头 <algorithm> 定义
(C++23)
 左折叠范围中元素
(算法函数对象) [编辑]
(C++23)
 以首元素为初值左折叠范围中元素
(算法函数对象) [编辑]
(C++23)
 右折叠范围中元素
(算法函数对象) [编辑]
(C++23)
 以末元素为初值右折叠范围中元素
(算法函数对象) [编辑]
(C++23)
 左折叠范围中元素，并返回 pair（迭代器，值）
(算法函数对象) [编辑]
(C++23)
 以首元素为初值左折叠范围中元素，并返回 pair（迭代器，optional）
(算法函数对象) [编辑]

修改序列的操作

复制操作

在标头 <algorithm> 定义
(C++11)
 复制范围中元素到新位置
(函数模板 & 算法函数对象)[编辑]
(C++20)(C++20)
(C++11)
 复制若干元素到新位置
(函数模板 & 算法函数对象)[编辑]
(C++20)
从后往前复制范围中元素
(函数模板 & 算法函数对象)[编辑]
(C++20)
(C++11)
 将范围中元素移到新位置
(函数模板 & 算法函数对象)[编辑]
(C++20)
(C++11)
 从后往前将范围中元素移到新位置
(函数模板 & 算法函数对象)[编辑]
(C++20)

交换操作

在标头 <algorithm> 定义      (C++11 前)
在标头 <utility> 定义          (C++11 起)
在标头 <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)

移除操作

在标头 <algorithm> 定义
移除满足特定条件的元素
(函数模板 & 算法函数对象)[编辑]
(C++20)(C++20)
复制范围并忽略满足特定条件的元素
(函数模板 & 算法函数对象)[编辑]
(C++20)(C++20)
移除范围中连续重复元素
(函数模板 & 算法函数对象)[编辑]
(C++20)
创建某范围的不含连续重复元素的副本
(函数模板 & 算法函数对象)[编辑]
(C++20)

顺序变更操作

在标头 <algorithm> 定义
逆转范围中的元素顺序
(函数模板 & 算法函数对象)[编辑]
(C++20)
创建范围的逆向副本
(函数模板 & 算法函数对象)[编辑]
(C++20)
旋转范围中的元素顺序
(函数模板 & 算法函数对象)[编辑]
(C++20)
复制并旋转元素范围
(函数模板 & 算法函数对象)[编辑]
(C++20)
(C++20)(C++20)
 迁移范围中元素
(函数模板 & 算法函数对象)[编辑]
(C++23)(C++23)
(C++17 前)(C++11)
 随机重排范围中元素
(函数模板 & 算法函数对象)[编辑]
(C++20)

采样操作

在标头 <algorithm> 定义
(C++17)
 从序列中随机选择 N 个元素
(函数模板 & 算法函数对象)[编辑]
(C++20)

排序和相关操作

要求

部分算法要求由实参表示的序列“已排序”或“已划分”。未满足要求时行为未定义。

序列在满足以下条件时已按比较器 comp 排序：对于指向序列中的每个迭代器 iter 和每个非负整数 n，如果 iter + n[1] 是一个指向序列中的某个元素的有效迭代器，那么 comp(*(iter + n), *iter) == false[1]。

(C++20 前)

序列在满足以下条件时已按比较器 comp 和投影 proj 排序：对于指向序列中的每个迭代器 iter 和每个非负整数 n，如果 iter + n[1] 是一个指向序列中的某个元素的有效迭代器，那么 bool(std::invoke(comp, std::invoke(proj, *(iter + n)),
std::invoke(proj, *iter)))[1] 是 false。

序列在满足以下条件时已按比较器 comp 排序：该序列已按比较器 comp 和投影 std::identity{}（即投影到自身）排序。

(C++20 起)

序列 [start, finish) 在满足以下条件时已按表达式 f(e) 划分：存在一个整数 n，使得对于 [0, std::distance(start, finish)) 中的所有整数 i，f(*(start + i))[1] 当且仅当 i < n 时是 true。

  1. ↑ 1.0 1.1 1.2 1.3 1.4 在这里 iter + n 只表示 “iter 自增 n 次后的结果”，而 iter 本身不需要是随机访问迭代器。

划分操作

在标头 <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)
复制范围中元素并部分排序
(函数模板 & 算法函数对象)[编辑]
(C++20)
(C++11)
 检查范围是否有序
(函数模板 & 算法函数对象)[编辑]
(C++20)
(C++11)
 找出最大的有序子范围
(函数模板 & 算法函数对象)[编辑]
(C++20)
找出范围如果有序时应在第 N 个的元素
(函数模板 & 算法函数对象)[编辑]
(C++20)

二分搜索操作（在已划分范围上）

在标头 <algorithm> 定义
使用二分搜索找出首个不小于给定值的元素
(函数模板 & 算法函数对象)[编辑]
(C++20)
使用二分搜索查找首个大于给定值的元素
(函数模板 & 算法函数对象)[编辑]
(C++20)
使用二分搜索找出匹配给定值的元素范围
(函数模板 & 算法函数对象)[编辑]
(C++20)
使用二分搜索判断元素是否在范围中
(函数模板 & 算法函数对象)[编辑]
(C++20)

集合操作（在已排序范围上）

在标头 <algorithm> 定义
判断一个序列是否为另一个序列的子序列
(函数模板 & 算法函数对象)[编辑]
(C++20)
计算两个集合的并集
(函数模板 & 算法函数对象)[编辑]
(C++20)
计算两个集合的交集
(函数模板 & 算法函数对象)[编辑]
(C++20)
计算两个集合的差集
(函数模板 & 算法函数对象)[编辑]
(C++20)
计算两个集合的对称差
(函数模板 & 算法函数对象)[编辑]
(C++20)

归并操作（在已排序范围上）

在标头 <algorithm> 定义
合并两个有序范围
(函数模板 & 算法函数对象)[编辑]
(C++20)
就地合并两个有序范围
(函数模板 & 算法函数对象)[编辑]
(C++20)

堆操作

随机访问范围 [first, last) 在满足以下条件时是一个关于比较器 comp 的堆：对于 (0, last - first) 中的所有整数 i，bool(comp(first[(i - 1) / 2], first[i])) 都是 false。

(C++20 前)

随机访问范围 [first, last) 在满足以下条件时是一个关于比较器 comp 和投影 proj 的堆：对于 (0, last - first) 中的所有整数 i，bool(std::invoke(comp, std::invoke(proj, first[(i - 1) / 2]),
std::invoke(proj, first[i])) 都是 false。

随机访问范围 [first, last) 在满足以下条件时是一个关于比较器 comp 的堆：该范围是一个关于 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> 定义
以字典序比较两个范围
(函数模板 & 算法函数对象)[编辑]
(C++20)
(C++20)
 三路比较两个范围
(函数模板) [编辑]

排列操作

在标头 <algorithm> 定义
生成元素范围的下一个字典序更大的排列
(函数模板 & 算法函数对象)[编辑]
(C++20)
生成元素范围的下一个字典序更小的排列
(函数模板 & 算法函数对象)[编辑]
(C++20)
(C++11)
 判断一个序列是否为另一个序列的排列
(函数模板 & 算法函数对象)[编辑]
(C++20)

数值运算

在标头 <numeric> 定义
(C++11)
 从初始值开始连续递增填充范围
(函数模板 & 算法函数对象)[编辑]
(C++23)
求和或折叠范围中元素
(函数模板) [编辑]
计算两个范围中元素的内积
(函数模板) [编辑]
计算范围中相邻元素的差
(函数模板) [编辑]
计算范围中元素的部分和
(函数模板) [编辑]
(C++17)
 类似 std::accumulate，但不依序执行
(函数模板) [编辑]
(C++17)
 类似 std::partial_sum，第 i 个和中排除第 i 个输入
(函数模板) [编辑]
(C++17)
 类似 std::partial_sum，第 i 个和中包含第 i 个输入
(函数模板) [编辑]
(C++17)
 应用可调用对象，然后乱序规约
(函数模板) [编辑]
(C++17)
 应用可调用对象，然后计算排除扫描
(函数模板) [编辑]
(C++17)
 应用可调用对象，然后计算包含扫描
(函数模板) [编辑]

<memory> 专门算法

<random> 专门算法 (C++26 起)

在标头 <random> 定义
(C++26)
 用来自均匀随机位发生器的随机数填充范围
(算法函数对象) [编辑]

注解

功能特性测试宏 值 标准 功能特性
__cpp_lib_algorithm_default_value_type 202403L (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) constexpr 算法
202306L (C++26) constexpr 稳定排序
__cpp_lib_execution 201603L (C++17) 执行策略
201902L (C++20) std::execution::unsequenced_policy
__cpp_lib_freestanding_algorithm 202311L (C++26) <algorithm> 中的独立设施
__cpp_lib_parallel_algorithm 201603L (C++17) 并行算法
202506L (C++26) 并行范围算法
__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 文档